1 00:00:00,000 --> 00:00:06,000 大家好。 2 00:00:06,000 --> 00:00:12,000 数据结构与算法这一讲的内容,我们开始第7章,图的学习。 3 00:00:12,000 --> 00:00:19,970 首先,我们介绍一下图的相关的定义和术语。然后我们介绍它的抽象数据类型。 4 00:00:19,970 --> 00:00:26,110 图,它表示的是顶点和边的 5 00:00:26,110 --> 00:00:32,250 这样的集合。那如果在这个图里面,两两的顶点之间 6 00:00:32,250 --> 00:00:37,020 都有边相关联。那就是形成完全图。 7 00:00:37,020 --> 00:00:42,415 相应于完全图,我们有一种稀疏图。 8 00:00:42,415 --> 00:00:47,810 它很多顶点之间都没有边关联。 9 00:00:47,810 --> 00:00:56,110 那如果是边的条数小于这个完全图的百分之5,我们可以看作它是一种稀疏图。 10 00:00:56,110 --> 00:01:02,010 那还有一种图,它并不是完全图。它也相当的 11 00:01:02,010 --> 00:01:07,910 密集,也就是说它的边的条数,接近于完全图了。那我们 12 00:01:07,910 --> 00:01:11,985 称为密集图。 13 00:01:11,985 --> 00:01:16,060 有一种图它的顶点之间, 14 00:01:16,060 --> 00:01:21,350 的这些边的关联,我们可以看作是无序对。 15 00:01:21,350 --> 00:01:27,330 那也就是说,从v1到v2和从v2到v1,我们没有关系。 16 00:01:27,330 --> 00:01:32,790 那其实它是双向的,也就是说从v1到v2, 17 00:01:32,790 --> 00:01:39,940 有一条边其实隐含着从v2到v1也是相通的,所以我们不画 18 00:01:39,940 --> 00:01:44,550 这个箭头了,就直接画成这样的无向边。那就是无向图。 19 00:01:44,550 --> 00:01:51,075 那有向图,它的这些顶点之间的关联关系的偶对 20 00:01:51,075 --> 00:01:57,600 是有序的。也就是我们从v1到v4有边,但是从 21 00:01:57,600 --> 00:02:02,200 v4到v1不是直接关联的。 22 00:02:02,200 --> 00:02:06,945 那有些情况下,我们这些顶点, 23 00:02:06,945 --> 00:02:11,690 我给它标上号。那在后面,我们引用的时候 24 00:02:11,690 --> 00:02:18,260 就可以引用这个标号来指代相应的这样的结点。在 25 00:02:18,260 --> 00:02:25,855 一些情况下,我们的边它是有权重的。这权重可以代表 26 00:02:25,855 --> 00:02:33,450 从一个结点到另外一个结点,它的开销,例如时间,还是价格等等这些开销。 27 00:02:33,450 --> 00:02:37,685 在图里面, 28 00:02:37,685 --> 00:02:41,920 度是非常重要的一个概念。 29 00:02:41,920 --> 00:02:49,270 那所谓度,就是跟顶点相关联的边的数目。 30 00:02:49,270 --> 00:02:55,990 因为在这样的有向图里面,我们这个关联它是有向的。 31 00:02:55,990 --> 00:03:03,170 那,我们就能看到,从一个顶点出发,它可能发出几条边。那这就是 32 00:03:03,170 --> 00:03:07,380 它的出度。那也可能从一个顶点出发呢, 33 00:03:07,380 --> 00:03:11,590 会有几个边是 34 00:03:11,590 --> 00:03:17,780 指向它自己的。那我们可以看到是它的入度。 35 00:03:17,780 --> 00:03:24,640 还有另一个概念是子图。那对于左边的这样一个图, 36 00:03:24,640 --> 00:03:31,500 我们可以看到,右边就是这个蓝色部分把它提溜出来的 37 00:03:31,500 --> 00:03:36,585 这样的子图。那它的子图里面的所有的顶点, 38 00:03:36,585 --> 00:03:41,670 还有相关的这些边呢,都在原来的图里面要出现。 39 00:03:41,670 --> 00:03:46,885 路径是 40 00:03:46,885 --> 00:03:52,100 图里面一个顶点到另外一个顶点 41 00:03:52,100 --> 00:03:59,030 的这么一些有序的结点边组成的这么一个序链。 42 00:03:59,030 --> 00:04:05,180 在数据结构里面,我们一般讨论的是简单路径, 43 00:04:05,180 --> 00:04:09,485 也就是说在这个序列里面,我们 44 00:04:09,485 --> 00:04:13,790 不允许这些点出现两次。 45 00:04:13,790 --> 00:04:18,910 那,有一个特例就是起点和终点可以重复出现。 46 00:04:18,910 --> 00:04:24,850 那我们看到刚才这样的一个路径, 47 00:04:24,850 --> 00:04:29,385 这些相应的点,我们可以看到, 48 00:04:29,385 --> 00:04:33,920 这两个点,它分别出现了两次。然后这中间,也是 49 00:04:33,920 --> 00:04:40,370 这些点呢,有两次的出现。那这就不是我们的简单路径。 50 00:04:40,370 --> 00:04:46,930 那我们从刚才vp到vq的这个路径的过程中, 51 00:04:46,930 --> 00:04:54,480 它是一个简单路径。那我们看到从刚才从vp到vq的这一条简单路径中, 52 00:04:54,480 --> 00:04:59,520 那它的边的条数就是它的路径长度。 53 00:04:59,520 --> 00:05:05,860 如果这个简单路径中, 54 00:05:05,860 --> 00:05:13,050 它的起始点和终结点是同一个,那就构成了回路。 55 00:05:13,050 --> 00:05:18,540 那如果是一个图,它没有 56 00:05:18,540 --> 00:05:22,560 这样的回路,我们就把它称为无环图。 57 00:05:22,560 --> 00:05:30,490 那有一种特别的,这样的环图,就是有向无环图。我们也称为DAG图。 58 00:05:30,490 --> 00:05:36,165 树和森林,是DAG图的一种特例。 59 00:05:36,165 --> 00:05:41,840 当然还有其它的DAG图。它一般DAG图, 60 00:05:41,840 --> 00:05:47,175 它只要求有向和无环。但是一个顶点,它有 61 00:05:47,175 --> 00:05:52,510 几个这个,指向它的这些边是没关系的,也就是说 62 00:05:52,510 --> 00:05:57,575 这些顶点是可以重入的。而树和森林,我们每一个顶点 63 00:05:57,575 --> 00:06:05,080 它只有一个父结点,也就是说只有一个指向它的边,那就是不允许重入。 64 00:06:05,080 --> 00:06:12,280 我们来观察一下这些回路的情况。那对于3个顶点 65 00:06:12,280 --> 00:06:19,480 这样构成的回路,显然是正确的。那对于两个顶点的情况, 66 00:06:19,480 --> 00:06:24,880 那我们看无向图,这样的两个顶点的情况,我们不认为 67 00:06:24,880 --> 00:06:30,280 它构成了环。实际上,我们对于这种无向图, 68 00:06:30,280 --> 00:06:35,130 它两个顶点之间,我们可以看作它发出了 69 00:06:35,130 --> 00:06:39,980 两条这样的边,是不允许的。这样的在我们数据结构里面 70 00:06:39,980 --> 00:06:48,680 不讨论这样的结构,也就是说在整个数据结构里面,我们都不存在这样的一种图的结构。 71 00:06:48,680 --> 00:06:53,675 在有向图的情况下,这个是一个环。 72 00:06:53,675 --> 00:06:58,670 就是说两个顶点,这两条边,我们是可以构成环的。 73 00:06:58,670 --> 00:07:05,080 还有一种图是有根图,也就是在这个图里面, 74 00:07:05,080 --> 00:07:14,640 有一个顶点,它可以到达其图里面所有的顶点。那这个特殊的顶点就叫做根。 75 00:07:14,640 --> 00:07:21,280 树就是这么一个有根图的情况。那森林呢, 76 00:07:21,280 --> 00:07:27,920 因为它是有若干棵树组成的,所以我们可以说它是有若干棵这样的有根图 77 00:07:27,920 --> 00:07:31,520 组成的,这么一个特殊的图。 78 00:07:31,520 --> 00:07:38,485 如果在无向图里面, 79 00:07:38,485 --> 00:07:45,450 我们从一个点v1到v2有一条路径,那同时,从v2到v1也是 80 00:07:45,450 --> 00:07:52,520 一定有一条路径的。那我们称v1和v2是连通的。 81 00:07:52,520 --> 00:07:57,925 那我们对于无向图的这样的 82 00:07:57,925 --> 00:08:03,330 连通的子图,我们就叫它连通分量。 83 00:08:03,330 --> 00:08:08,885 可以看到这两个子图组成的这个大图,那在左边这个连通分量 84 00:08:08,885 --> 00:08:14,440 里面,它的所有的结点之间,它都是连通的。 85 00:08:14,440 --> 00:08:20,140 那右边这个子图,它们的这个子结点,也是连通的。 86 00:08:20,140 --> 00:08:24,320 那对于有向图,它的 87 00:08:24,320 --> 00:08:28,500 要求就更严格的一些。因为我们从vi到vj 88 00:08:28,500 --> 00:08:36,480 有这样的一个路径的话,也不一定从vj到vi也同样有一条路径。 89 00:08:36,480 --> 00:08:43,075 那如果是这个情况成立,也就是说vi到vj是有路径的,而且 90 00:08:43,075 --> 00:08:48,120 Vj到Vi有路径的,那就称这两个顶点,它是 91 00:08:48,120 --> 00:08:55,110 强连通的。那对于有向图,我们这些 92 00:08:55,110 --> 00:09:01,760 如果是一个子图,它结点内部,它是强连通的。 93 00:09:01,760 --> 00:09:07,360 那我们找出这样的极大的强连通的子图。 94 00:09:07,360 --> 00:09:12,625 那就形成了若干个强连通的分量。 95 00:09:12,625 --> 00:09:17,890 例如我们对于这个大图来说,我们分成了4组 96 00:09:17,890 --> 00:09:23,780 强连通分量。在每一个分量里面,它的 97 00:09:23,780 --> 00:09:29,670 这个结点之间是相通的,但是,分量和分量之间, 98 00:09:29,670 --> 00:09:34,640 它是不构成这样的一个强连通的一个关系。 99 00:09:34,640 --> 00:09:42,330 带权的连通图称为网络。那网络在有些应用里面 100 00:09:42,330 --> 00:09:48,520 也有一些作用。好,那我们看一下图的抽象数据类型。 101 00:09:48,520 --> 00:09:54,710 对于一个数据结构来说,我们最重要的,就是描述它的顶点 102 00:09:54,710 --> 00:10:01,665 以及边的性质。那图的抽象数据类型,我们首先就是要 103 00:10:01,665 --> 00:10:06,300 知道顶点的个数还有边的个数。 104 00:10:06,300 --> 00:10:14,070 另外,因为我们考虑的对于这个图里面每一个顶点。 105 00:10:14,070 --> 00:10:21,840 那它关联到其它的邻居点是什么?那这都是通过边去关联的。那 106 00:10:21,840 --> 00:10:24,890 因此,我们就需要知道有哪一些边。 107 00:10:24,890 --> 00:10:32,005 那为了方便处理,那我们会对这些边来进行这样的标记。 108 00:10:32,005 --> 00:10:39,120 也就是说,我从这个顶点出发,哪一条边是我看到的第一条边,以及下一条边。 109 00:10:39,120 --> 00:10:45,770 那这些边之间,就根据它们出现的先后顺序,那就作为这个发出的 110 00:10:45,770 --> 00:10:52,420 顶点的第一条边以及它们互相知道下一条边是谁。 111 00:10:52,420 --> 00:10:57,435 那这样的话呢,我们就把这一个结点,它的 112 00:10:57,435 --> 00:11:02,450 相应的所有的边都组织起来了。就是我第一条边是谁, 113 00:11:02,450 --> 00:11:06,520 然后下一条边是谁,下一条边的下一条边是谁。 114 00:11:06,520 --> 00:11:14,270 那我们就形成这么一个组织的结构。那在后面呢,我们的存储实现里面可以看到 115 00:11:14,270 --> 00:11:22,020 这样的一个图的,它的发出的边以及这些边之间相应的组织。 116 00:11:22,020 --> 00:11:27,170 另外,对于这么一条边,我需要知道 117 00:11:27,170 --> 00:11:31,660 它的起始点是哪一个,以及它的终止点 118 00:11:31,660 --> 00:11:36,150 是哪一个。还有就是这个边,它的权重是什么。 119 00:11:36,150 --> 00:11:41,660 最后给大家留两个思考。首先呢,就是 120 00:11:41,660 --> 00:11:50,000 对于一个顶点,它是有,我们有从自己 121 00:11:50,000 --> 00:11:55,460 指向自己的一条边,那就是形成一个自环的一个这么一个结构。 122 00:11:55,460 --> 00:12:00,865 另外呢,在两个顶点之间,我们有没有可能 123 00:12:00,865 --> 00:12:06,270 有两条边都是从这个顶点指向另外一个顶点的? 124 00:12:06,270 --> 00:12:11,220 那其实这个现象,在我们的网页里面 125 00:12:11,220 --> 00:12:16,170 是经常出现的。也就是说在一个网页里面, 126 00:12:16,170 --> 00:12:22,280 我可能在某一个点,我会连接到另外一个点。还有就是 127 00:12:22,280 --> 00:12:28,390 两个网页之间,我可能一个网页指向另外一个网页的时候, 128 00:12:28,390 --> 00:12:36,505 它可能有不同的连接入口。但是在数据结构里面,我们只讨论简单的结构, 129 00:12:36,505 --> 00:12:44,980 对着一些复杂的现象,我们会不予考虑。如果你要实现的时候,你可以做些特别的处理。 130 00:12:44,980 --> 00:12:51,840 谢谢大家。