1 00:00:00,000 --> 00:00:06,620 大家好。 2 00:00:06,620 --> 00:00:16,540 数据结构与算法,这一讲的内容,我们继续第七章图的学习。我们学习图的存储结构。 3 00:00:16,540 --> 00:00:23,640 图,它表达的是节点和节点之间的两两的边的信息。 4 00:00:23,640 --> 00:00:29,090 那因此呢,我们可以很自然地用一个矩阵来表示。 5 00:00:29,090 --> 00:00:34,900 那这个矩阵里面呢,它相应的这个i, j之间的元素 6 00:00:34,900 --> 00:00:40,710 的信息呢就是表示的是这个边是否存在。如果存在呢, 7 00:00:40,710 --> 00:00:46,810 我就把它设为1,不存在就设为0。因此,这个图 8 00:00:46,810 --> 00:00:52,910 的相邻矩阵表达,它所占用的空间呢是0(n²)的, 9 00:00:52,910 --> 00:00:57,360 跟边没有关系。不管它是完全图, 10 00:00:57,360 --> 00:01:01,810 还是稀疏图,都需要花这么多的存储的空间。 11 00:01:01,810 --> 00:01:08,290 那我们来看有向图的这样的一个相邻矩阵的表达。 12 00:01:08,290 --> 00:01:15,420 对应的某一个位置,比如说我们在这个位置,它表达的就是 13 00:01:15,420 --> 00:01:20,980 V3指向V0的这么一个边的信息。 14 00:01:20,980 --> 00:01:26,230 那我们再来看一个带权的无向图。 15 00:01:26,230 --> 00:01:32,970 那对于这样的一个图呢,原来的这样的0,1的有无的信息,我们就 16 00:01:32,970 --> 00:01:39,710 可以把这个1呢这个存在呢,我们表示为它相应的权的值。 17 00:01:39,710 --> 00:01:46,050 那因为它是一个无向图,所以我们从对角线划分开。 18 00:01:46,050 --> 00:01:49,700 那它是一个对称的一个矩阵。 19 00:01:49,700 --> 00:01:55,785 相邻矩阵的实现呢,我们主要是 20 00:01:55,785 --> 00:02:01,870 依赖于一个二维的数组。然后,大家特别要注意一下, 21 00:02:01,870 --> 00:02:06,690 这个边的信息,每一个二维数组里面的 22 00:02:06,690 --> 00:02:11,510 一个元素呢,它代表的是一条边。然后它相应的有 23 00:02:11,510 --> 00:02:19,100 这个边它的起始点、它的终止点,以及权重的信息。 24 00:02:20,700 --> 00:02:29,050 对于稀疏图的情况,这样的一个 相邻矩阵有大量的零元存在。 25 00:02:29,050 --> 00:02:34,075 那我们要找里面的非零元的元素,也就是相应的有效边的时候呢, 26 00:02:34,075 --> 00:02:39,100 我需要逐个的去挨个找。 27 00:02:39,100 --> 00:02:45,050 那是一个这样的双重循环。那会有大量的这样的时间的浪费。 28 00:02:45,050 --> 00:02:52,070 那因为稀疏矩阵它的非零元是很少的,那如果我们能够把这些有效边 29 00:02:52,070 --> 00:03:01,370 给组织起来呢,可能我们的运算也会节省很多。当然它的存储也是 要有很多的节省的。 30 00:03:01,370 --> 00:03:09,070 那我们来看一下我们的一个实现,也就是邻接表的形式。 31 00:03:09,070 --> 00:03:13,660 那邻接表的形式呢,我们是把这个节点组织起来, 32 00:03:13,660 --> 00:03:18,250 然后呢,边呢就跟它关联的这些节点。 33 00:03:18,250 --> 00:03:26,275 我们把这些有效边呢给它串起来。那形成这么一个结构。它同时节省了 34 00:03:26,275 --> 00:03:30,570 空间,而且呢能够提高时间的效率。 35 00:03:30,570 --> 00:03:35,510 那我们看这样的邻接表的信息表达。 36 00:03:35,510 --> 00:03:40,450 那对于节点来说呢,就是这个节点它本身有哪些数据, 37 00:03:40,450 --> 00:03:49,550 还有它所发出来的第一条边的信息。那它的其他的关联边的信息呢,就通过 38 00:03:49,550 --> 00:03:55,050 边的节点,里面它们互相之间指向我的下一个这个 39 00:03:55,050 --> 00:04:00,550 邻接边是什么。当然它们都共有这样的一个起始点的信息。 40 00:04:00,550 --> 00:04:05,410 那我们来看无向图的这样一个邻接表的实现。 41 00:04:05,410 --> 00:04:11,765 那对于这样的一个无向图,它有五条边。那每一条边呢, 42 00:04:11,765 --> 00:04:18,120 它跟两个节点都相关。那会在这个两个节点的 43 00:04:18,120 --> 00:04:26,715 这个边表里面呢出现。那对于这种情况呢,我们特别要注意,尤其是有些运算里面当我 44 00:04:26,715 --> 00:04:32,560 修改一条边的信息的时候,那在无向图的邻接表的实现里面, 45 00:04:32,560 --> 00:04:38,455 我们会要在两个这样的是相应的 46 00:04:38,455 --> 00:04:44,350 边节点里面进行修改。当然这两个边节点,其实它表达的是同一个。因此,我们要 47 00:04:44,350 --> 00:04:48,050 注意信息的一致性。 48 00:04:48,050 --> 00:04:54,070 我们再来看这样一个带权的一个图。 49 00:04:54,070 --> 00:04:59,600 那我们就可以直接地把权重呢作为一个信息域, 50 00:04:59,600 --> 00:05:04,270 放到这个边表里面的这个边节点里面。 51 00:05:04,270 --> 00:05:10,880 对于有向图来说, 52 00:05:10,880 --> 00:05:16,670 我们的邻接表呢常用的就是一个出边表的信息。 53 00:05:16,670 --> 00:05:22,460 也就是说,我从任何一个节点出发,如果我能够 54 00:05:22,460 --> 00:05:26,945 把自己相关联的这些边的信息,也就是说这些边 55 00:05:26,945 --> 00:05:31,430 所涉及到的这些节点的信息,我都能够到的话呢, 56 00:05:31,430 --> 00:05:39,820 那这个信息就是完备的。但是有的时候, 我为了运算操作的方便,我还希望能够表达 57 00:05:39,820 --> 00:05:44,205 这个每一个节点它的入边的信息, 58 00:05:44,205 --> 00:05:49,700 那这样的话呢就是一个逆邻接表,我们也俗称为 入边表。 59 00:05:49,700 --> 00:05:55,585 那图的邻接表的表示呢,它的空间代价 60 00:05:55,585 --> 00:06:01,470 跟节点个数n还有边的个数e是相关的。 61 00:06:01,470 --> 00:06:05,570 对于无向图来说呢,每一条边都被 62 00:06:05,570 --> 00:06:09,670 表达了两次,因此呢是n+2e。 63 00:06:09,670 --> 00:06:15,730 那对于有向图呢,是n+e。当我们这个图很稀疏的时候, 64 00:06:15,730 --> 00:06:20,615 也就是说e呢它会是小于小于n²的。 65 00:06:20,615 --> 00:06:25,500 那我们这样的存储的空间呢是非常节省的,而且呢, 66 00:06:25,500 --> 00:06:30,030 带来了相应的运算的一些效率的提高。 67 00:06:30,030 --> 00:06:36,250 如果我们的出边表 68 00:06:36,250 --> 00:06:42,470 和入边表我们经常会要使用而且经常在一起联合着使用, 69 00:06:42,470 --> 00:06:47,970 那我们就有这么一个十字链的结钩。那可以说是 70 00:06:47,970 --> 00:06:53,470 邻接表和逆邻接表,也就是出边表和入边表的结合。 71 00:06:53,470 --> 00:06:58,510 那我们每一个表目呢,它都会是 72 00:06:58,510 --> 00:07:03,550 有几个域,那也就是它的数据域。 73 00:07:03,550 --> 00:07:10,730 以及它的一个起始点的信息。它的一个终止点的信息。 74 00:07:10,730 --> 00:07:17,910 以及在它的一个出边表里面,它的下一条邻居的信息。 75 00:07:17,910 --> 00:07:25,680 和入边表里面,下一条的邻居的信息。那我们来看,对于这样一个 76 00:07:25,680 --> 00:07:29,980 二维矩阵所表达的一个图的结构。 77 00:07:29,980 --> 00:07:36,290 那我们得到这样的一个出边表的信息,还有 78 00:07:36,290 --> 00:07:41,215 相应的一组这个入边表的信息。那我们可以看到 79 00:07:41,215 --> 00:07:46,140 每一个这样的节点呢,它是由5个域组成的。 80 00:07:46,140 --> 00:07:53,020 也就是说,它的起始点、终结点,它相应的权重,还有 81 00:07:53,020 --> 00:07:58,075 同行的这个下一条边的链,也就是出边链, 82 00:07:58,075 --> 00:08:03,130 然后呢,同一列的下一条边的一个链接, 83 00:08:03,130 --> 00:08:10,145 那也就是入边的这个链接。那数独等等应用里面呢, 84 00:08:10,145 --> 00:08:14,380 我们可以用十字链表来辅助实现。 85 00:08:14,380 --> 00:08:20,000 最后给大家留一下思考题。 86 00:08:20,000 --> 00:08:26,490 对于这种自环的、以及重复边的复杂图结构, 87 00:08:26,490 --> 00:08:33,544 那我们前面介绍的存储结构需要做什么样的修改呢?谢谢大家!