数据结构:图(Graph)【详解】 |
您所在的位置:网站首页 › 节点的概念和操作分别是什么 › 数据结构:图(Graph)【详解】 |
友情链接:数据结构专栏 目录 图【知识框架】 图的基本概念一、图的定义二、图的基本概念和术语1、有向图2、无向图3、简单图4、多重图5、完全图(也称简单完全图)6、子图7、连通、连通图和连通分量8、强连通图、强连通分量9、生成树、生成森林10、顶点的度、入度和出度11、边的权和网12、稠密图、稀疏图13、路径、路径长度和回路14、 简单路径、简单回路15、距离16、有向树 图的存储结构一、邻接矩阵二、邻接表三、十字链表四、邻接多重表五、边集数组 图的遍历一、深度优先遍历1、DFS算法2、DFS算法的性能分析3、深度优先的生成树和生成森林 二、广度优先遍历1、BFS算法2、BFS算法性能分析 三、图的遍历与图的连通性 最小生成树一、普里姆(Prim)算法二、克鲁斯卡尔(Kruskal)算法 最短路径一、迪杰斯特拉( Dijkstra )算法二、弗洛伊德( Floyd )算法 拓扑排序一、定义二、算法 关键路径一、定义二、算法 总结附录上文链接下文链接专栏参考资料 图 【知识框架】在线性表中,数据元素之间是被串起来的,仅有线性关系,每个数据元素只有一个直接前驱和一个直接后继。在树形结构中,数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层中多个元素相关,但只能和上一层中一个元素相关。图是一种较线性表和树更加复杂的数据结构。在图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。 一、图的定义图(Graph)是由顶点的有穷非空集合 V ( G ) V(G) V(G)和顶点之间边的集合 E ( G ) E(G) E(G)组成,通常表示为: G = ( V , E ) G=(V,E) G=(V,E),其中, G G G表示个图, V V V是图 G G G中顶点的集合, E E E是图 G G G中边的集合。若 V = { v 1 , v 2 , . . . , v n } V= \{v_1, v_2,...,v_n\} V={v1,v2,...,vn},则用 ∣ V ∣ |V| ∣V∣表示图 G G G中顶点的个数,也称图 G G G的阶, E = { ( u , v ) ∣ u ∈ V , v ∈ V } E= \{(u, v) |u∈V, v∈V\} E={(u,v)∣u∈V,v∈V},用 ∣ E ∣ |E| ∣E∣表示图 G G G中边的条数。 注意:线性表可以是空表,树可以是空树,但图不可以是空图。就是说,图中不能一个顶点也没有,图的顶点集V一定非空,但边集E可以为空,此时图中只有顶点而没有边。 二、图的基本概念和术语 1、有向图若E是有向边(也称弧)的有限集合时,则图G为有向图。弧是顶点的有序对,记为,其中v,w是顶点,v称为弧尾,w称为弧头,称为从顶点v到顶点w的弧,也称v邻接到w,或w邻接自v。 若E是无向边(简称边)的有限集合时,则图G为无向图。边是顶点的无序对,记为(v, w)或(w,v),因为(v,w)=(w,v), 其中v,w是顶点。可以说顶点w和顶点v互为邻接点。边(v, w)依附于顶点w和v,或者说边(v, w)和顶点v, w相关联。 图(b)所示的无向图G2可表示为 G 2 = ( V 2 , E 2 ) G_2=(V_2,E_2) G2=(V2,E2) V 2 = { 1 , 2 , 3 , 4 } V_2=\{1,2,3,4\} V2={1,2,3,4} E 2 = { ( 1 , 2 ) , ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) } E_2=\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\} E2={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)} 3、简单图一个图 G G G若满足:①不存在重复边;②不存在顶点到自身的边,则称图 G G G为简单图。上图中 G 1 G_1 G1和 G 2 G_2 G2均为简单图。数据结构中仅讨论简单图。 4、多重图若图 G G G中某两个结点之间的边数多于一条,又允许顶点通过同一条边和自己关联,则 G G G为多重图。多重图的定义和简单图是相对的。 5、完全图(也称简单完全图)对于无向图,
∣
E
∣
|E|
∣E∣的取值范围是
0
0
0到
n
(
n
−
1
)
/
2
n(n-1)/2
n(n−1)/2,有
n
(
n
−
1
)
/
2
n(n -1)/2
n(n−1)/2条边的无向图称为完全图,在完全图中任意两个顶点之间都存在边。对于有向图,
∣
E
∣
|E|
∣E∣的取值范围是
0
0
0到
n
(
n
−
1
)
n(n-1)
n(n−1),有
n
(
n
−
1
)
n(n-1)
n(n−1)条弧的有向图称为有向完全图,在有向完全图中任意两个顶点之间都存在方向相反的两条弧。上图中
G
2
G_2
G2为无向完全图,而
G
3
G_3
G3为有向完全图。 设有两个图 G = ( V , E ) G=(V, E) G=(V,E)和 G ′ = ( V ′ , E ′ ) G'=(V', E') G′=(V′,E′), 若 V ′ V' V′是 V V V的子集,且 E ′ E' E′是 E E E的子集,则称 G ′ G' G′是 G G G的子图。若有满足 V ( G ′ ) = V ( G ) V(G')= V(G) V(G′)=V(G)的子图 G ′ G' G′,则称其为 G G G的生成子图。上图中 G 3 G_3 G3为 G 1 G_1 G1的子图。 注意:并非V和E的任何子集都能构成G的子图,因为这样的子集可能不是图,即E的子集中的某些边关联的顶点可能不在这个V的子集中。 7、连通、连通图和连通分量在无向图中,若从顶点
v
v
v到顶点
w
w
w有路径存在,则称
v
v
v和
w
w
w是连通的。若图
G
G
G中任意两个顶点都是连通的,则称图
G
G
G为连通图,否则称为非连通图。无向图中的极大连通子图称为连通分量。若一个图有
n
n
n个顶点,并且边数小于
n
−
1
n-1
n−1,则此图必是非连通图。如下图(a)所示, 图
G
4
G_4
G4有3个连通分量,如图(b)所示。 注意:弄清连通、连通图、连通分量的概念非常重要。首先要区分极大连通子图和极小连通子图,极大连通子图是无向图的连通分量,极大即要求该连通子图包含其所有的边;极小连通子图是既要保持图连通又要使得边数最少的子图。 8、强连通图、强连通分量在有向图中,若从顶点
v
v
v到顶点
w
w
w和从顶点
w
w
w到项点
v
v
v之间都有路径,则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的,则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量,图
G
1
G_1
G1的强连通分量如下图所示。 注意:强连通图、强连通分量只是针对有向图而言的。一般在无向图中讨论连通性,在有向图中考虑强连通性。 9、生成树、生成森林连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为
n
n
n,则它的生成树含有
n
−
1
n-1
n−1条边。对生成树而言,若砍去它的一条边,则会变成非连通图,若加上一条边则会形成一个回路。在非连通图中,连通分量的生成树构成了非连通图的生成森林。图
G
2
G_2
G2的一个生成树如下图所示。 注意:包含无向图中全部顶点的极小连通子图,只有生成树满足条件,因为砍去生成树的任一条边,图将不再连通。 10、顶点的度、入度和出度图中每个顶点的度定义为以该项点为一个端点的边的数目。 对于无向图,顶点v的度是指依附于该顶点的边的条数,记为 T D ( v ) TD(v) TD(v)。 在具有 n n n个顶点、 e e e条边的无向图中, ∑ i = 1 n T D ( v i ) = 2 e \displaystyle\sum_{i=1}^{n}TD(v_i)= 2e i=1∑nTD(vi)=2e,即无向图的全部顶点的度的和等于边数的2倍,因为每条边和两个顶点相关联。 对于有向图,顶点 v v v的度分为入度和出度,入度是以顶点 v v v为终点的有向边的数目,记为 I D ( v ) ID(v) ID(v); 而出度是以顶点 v v v为起点的有向边的数目,记为 O D ( v ) OD(v) OD(v)。顶点 v v v的度等于其入度和出度之和,即 T D ( v ) = I D ( v ) + O D ( v ) 。 TD(v) = ID(v) + OD(v)。 TD(v)=ID(v)+OD(v)。 在具有 n n n个顶点、 e e e条边的有向图中, ∑ i = 1 n I D ( v i ) = ∑ i = 1 n O D ( v i ) = e \displaystyle\sum_{i=1}^{n}ID(v_i)=\displaystyle\sum_{i=1}^{n}OD(v_i)=e i=1∑nID(vi)=i=1∑nOD(vi)=e,即有向图的全部顶点的入度之和与出度之和相等,并且等于边数。这是因为每条有向边都有一个起点和终点。 11、边的权和网在一个图中,每条边都可以标上具有某种含义的数值,该数值称为该边的权值。这种边上带有权值的图称为带权图,也称网。 12、稠密图、稀疏图边数很少的图称为稀疏图,反之称为稠密图。稀疏和稠密本身是模糊的概念,稀疏图和稠密图常常是相对而言的。一般当图G满足 ∣ E ∣ < ∣ V ∣ l o g ∣ V ∣ |E| < |V|log|V| ∣E∣ int adjvex; //该弧所指向的顶点的下标或者位置 EdgeType weight; //权值,对于非网图可以不需要 struct EdgeNode *next; //指向下一个邻接点 }EdgeNode; /*顶点表结点*/ typedef struct VertexNode{ Vertex data; //顶点域,存储顶点信息 EdgeNode *firstedge //边表头指针 }VertexNode, AdjList[MAXVEX]; /*邻接表*/ typedef struct{ AdjList adjList; int numVertexes, numEdges; //图中当前顶点数和边数 } 图的邻接表存储方法具有以下特点 若 G G G为无向图,则所需的存储空间为 O ( ∣ V ∣ + 2 ∣ E ∣ ) O(|V|+2|E|) O(∣V∣+2∣E∣);若 G G G为有向图,则所需的存储空间为 O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|) O(∣V∣+∣E∣)。前者的倍数2是由于无向图中,每条边在邻接表中出现了两次对于稀疏图,采用邻接表表示将极大地节省存储空间。在邻接表中,给定一顶点,能很容易地找出它的所有邻边,因为只需要读取它的邻接表。在邻接矩阵中,相同的操作则需要扫描一行,花费的时间为 O ( n ) O(n) O(n)。但是,若要确定给定的两个顶点间是否存在边,则在邻接矩阵中可以立刻查到,而在邻接表中则需要在相应结点对应的边表中查找另一结点,效率较低。在有向图的邻接表表示中,求一个给定顶点的出度只需计算其邻接表中的结点个数;但求其顶点的入度则需要遍历全部的邻接表。因此,也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。当然,这实际上与邻接表存储方式是类似的。图的邻接表表示并不唯一,因为在每个顶点对应的单链表中,各边结点的链接次序可以是任意的,它取决于建立邻接表的算法及边的输入次序。 三、十字链表十字链表是有向图的一种链式存储结构。 对于有向图来说,邻接表是有缺陷的。关心了出度问题,想了解入度就必须要遍历整个图才能知道,反之,逆邻接表解决了入度却不了解出度的情况。有没有可能把邻接表与逆邻接表结合起来呢?答案是肯定的,就是把它们整合在一起。这就是我们现在要介绍的有向图的一种存储方法:十字链表(Orthogonal List)。 我们重新定义顶点表结点结构如下表所示。 接下来通过一个例子详细介绍十字链表的结构。 如下图所示,顶点依然是存入一个一维数组
{
V
0
,
V
1
,
V
2
,
V
3
}
\{V_0,V_1,V_2,V_3\}
{V0,V1,V2,V3},实线箭头指针的图示完全与的邻接表的结构相同。就以顶点
V
0
V_0
V0来说,firstout 指向的是出边表中的第一个结点
V
3
V_3
V3。所以
V
0
V_0
V0边表结点的
h
e
a
d
v
e
x
=
3
headvex=3
headvex=3,而tailvex就是当前顶点
V
0
V_0
V0的下标0,由于
V
0
V_0
V0只有一个出边顶点,所以headlink和taillink都是空。 十字链表的好处就是因为把邻接表和逆邻接表整合在了一起, 这样既容易找到以 V 1 V_1 V1为尾的弧,也容易找到以 V 1 V_1 V1为头的弧,因而容易求得顶点的出度和入度。而且它除了结构复杂一点外,其实创建图算法的时间复杂度是和邻接表相同的,因此,在有向图的应用中,十字链表是非常好的数据结构模型。 四、邻接多重表邻接多重表是无向图的另一种链式存储结构。 在邻接表中,容易求得顶点和边的各种信息,但在邻接表中求两个顶点之间是否存在边而对边执行删除等操作时,需要分别在两个顶点的边表中遍历,效率较低。比如下图中,若要删除左图的
(
V
0
,
V
2
)
(V_0,V_2)
(V0,V2) 这条边,需要对邻接表结构中右边表的阴影两个结点进行删除操作,显然这是比较烦琐的。 每个顶点也用一一个结点表示,它由如下所示的两个域组成。 我们来看结构示意图的绘制过程,理解了它是如何连线的,也就理解邻接多重表构造原理了。如下图7所示,左图告诉我们它有4个顶点和5条边,显然,我们就应该先将4个顶点和5条边的边表结点画出来。 到这里,可以明显的看出,邻接多重表与邻接表的差别,仅仅是在于同一条边在邻接表中用两个结点表示,而在邻接多重表中只有一个结点。 这样对边的操作就方便多了,若要删除左图的 ( V 0 , V 2 ) (V_0,V_2) (V0,V2) 这条边,只需要将右图的⑥⑨的链接指向改为NULL即可。 五、边集数组边集数组是由两个一维数组构成。一个是存储顶点的信息;另一个是存储边的信息,这个边数组每个数据元素由一条边的起点下标(begin)、 终点下标(end)和权(weight)组成,如下图所示。显然边集数组关注的是边的集合,在边集数组中要查找一个顶点的度需要扫描整个边数组,效率并不高。因此它更适合对边依次进行处理的操作,而不适合对顶点相关的操作。 图的遍历是和树的遍历类似,我们希望从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次, 这一过程就叫做图的遍历(Traversing Graph)。 对于图的遍历来,通常有两种遍历次序方案:它们是深度优先遍历和广度优先遍历。 一、深度优先遍历深度优先遍历(Depth First Search),也有称为深度优先搜索,简称为DFS。 1、DFS算法深度优先搜索类似于树的先序遍历。如其名称中所暗含的意思一样,这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想如下:首先访问图中某一起始顶点v,然后由v出发,访问与v邻接且未被访问的任一顶点 w 1 w_1 w1,再访问与 w 1 w_1 w1邻接且未被访问的任一顶点…重复上述过程。当不能再继续向下访问时,依次退回到最近被访问的顶点,若它还有邻接顶点未被访问过,则从该点开始继续上述搜索过程,直至图中所有顶点均被访问过为止。 般情况下,其递归形式的算法十分简洁,算法过程如下: bool visited[MAX_VERTEX_NUM]; //访问标记数组 /*从顶点出发,深度优先遍历图G*/ void DFS(Graph G, int v){ int w; visit(v); //访问顶点 visited[v] = TRUE; //设已访问标记 //FirstNeighbor(G,v):求图G中顶点v的第一个邻接点,若有则返回顶点号,否则返回-1。 //NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点,返回除w外顶点v for(w = FirstNeighbor(G, v); w>=0; w=NextNeighor(G, v, w)){ if(!visited[w]){ //w为u的尚未访问的邻接顶点 DFS(G, w); } } } /*对图进行深度优先遍历*/ void DFSTraverse(MGraph G){ int v; for(v=0; v //从v=0开始遍历 if(!visited[v]){ DFS(G, v); } } }以下面这个无向图为例 DFS算法是一个递归算法,需要借助一个递归工作栈,故其空间复杂度为 O ( V ) O(V) O(V)。 对于n个顶点e条边的图来说,邻接矩阵由于是二维数组,要查找每个顶点的邻接点需要访问矩阵中的所有元素,因此都需要 O ( V 2 ) O(V^2) O(V2)的时间。而邻接表做存储结构时,找邻接点所需的时间取决于顶点和边的数量,所以是 O ( V + E ) O(V+E) O(V+E)。 显然对于点多边少的稀疏图来说,邻接表结构使得算法在时间效率上大大提高。 对于有向图而言,由于它只是对通道存在可行或不可行,算法上没有变化,是完全可以通用的。 3、深度优先的生成树和生成森林深度优先搜索会产生一棵深度优先生成树。 当然,这是有条件的,即对连通图调用DFS才能产生深度优先生成树,否则产生的将是深度优先生成森林,如下图所示。基于邻接表存储的深度优先生成树是不唯一的 。 广度优先遍历(Breadth First Search),又称为广度优先搜索,简称BFS。 1、BFS算法如果说图的深度优先遍历类似树的前序遍历,那么图的广度优先遍历就类似于树的层序遍历了。 广度优先搜索是一种分层的查找过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况,因此它不是一个递归的算法。为了实现逐层的访问,算法必须借助一个辅助队列,以记忆正在访问的顶点的下一层顶点。 以下是广度优先遍历的代码: /*邻接矩阵的广度遍历算法*/ void BFSTraverse(MGraph G){ int i, j; Queue Q; for(i = 0; i //若是未访问过就处理 if(!visited[i]){ vivited[i] = TRUE; //设置当前访问过 visit(i); //访问顶点 EnQueue(&Q, i); //将此顶点入队列 //若当前队列不为空 while(!QueueEmpty(Q)){ DeQueue(&Q, &i); //顶点i出队列 //FirstNeighbor(G,v):求图G中顶点v的第一个邻接点,若有则返回顶点号,否则返回-1。 //NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点,返回除w外顶点v for(j=FirstNeighbor(G, i); j>=0; j=NextNeighbor(G, i, j)){ //检验i的所有邻接点 if(!visited[j]){ visit(j); //访问顶点j visited[j] = TRUE; //访问标记 EnQueue(Q, j); //顶点j入队列 } } } } } }以下面这个无向图为例 无论是邻接表还是邻接矩阵的存储方式,BFS 算法都需要借助一个辅助队列Q, n个顶点均需入队一次,在最坏的情况下,空间复杂度为 O ( V ) O(V) O(V)。 采用邻接表存储方式时,每个顶点均需搜索一次(或入队一次), 在搜索任一顶点的邻接点时,每条边至少访问一次,算法总的时间复杂度为 O ( V + E ) O(V + E) O(V+E)。采用邻接矩阵存储方式时,查找每个顶点的邻接点所需的时间为 O ( V ) O(V) O(V),故算法总的时间复杂度为 O ( V 2 ) O(V^2) O(V2)。 注意:图的邻接矩阵表示是唯一的,但对于邻接表来说,若边的输入次序不同,生成的邻接表也不同。因此,对于同样一个图,基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的,基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的。 三、图的遍历与图的连通性图的遍历算法可以用来判断图的连通性。 对于无向图来说,若无向图是连通的,则从任一结点出发, 仅需一次遍历就能够访问图中的所有顶点;若无向图是非连通的,则从某一个顶点出发,一次遍历只能访问到该顶点所在连通分量的所有顶点,而对于图中其他连通分量的顶点,则无法通过这次遍历访问。对于有向图来说,若从初始点到图中的每个顶点都有路径,则能够访问到图中的所有顶点,否则不能访问到所有顶点。 故在BFSTraverse ()或DFSTraverse ()中添加了第二个for循环,再选取初始点,继续进行遍历,以防止一次无法遍历图的所有顶点。对于无向图,上述两个函数调用BFS (G,i)或DFS(G,i)的次数等于该图的连通分量数;而对于有向图则不是这样,因为一个连通的有向图分为强连通的和非强连通的,它的连通子图也分为强连通分量和非强连通分量,非强连通分量一次调用BFS (G, i)或DFS (G, i)无法访问到该连通分量的所有顶点。 如下图所示为有向图的非强连通分量。 一个连通图的生成树是一个极小的连通子图,它含有图中全部的顶点,但只有足以构成一棵树的 n − 1 n-1 n−1条边,若砍去它的一条边,则会使生成树变成非连通图;若给它增加一条边,则会形成图中的一条回路。对于一个带权连通无向图 G = ( V , E ) G=(V, E) G=(V,E),生成树不同,其中边的权值之和最小的那棵生成树(构造连通网的最小代价生成树),称为G的最小生成树(Minimum-Spanning-Tree, MST)。 构造最小生成树有多种算法,但大多数算法都利用了最小生成树的下列性质:假设 G = ( V , E ) G=(V, E) G=(V,E)是一个带权连通无向图, U U U是顶点集 V V V的一个非空子集。若 ( u , v ) (u,v) (u,v)是一条具有最小权值的边,其中 u ∈ U , v ∈ V − U u∈U,v∈V-U u∈U,v∈V−U,则必存在一棵包含边 ( u , v ) (u, v) (u,v)的最小生成树。 基于该性质的最小生成树算法主要有Prim算法和Kruskal算法,它们都基于贪心算法的策略。 下面介绍一个通用的最小生成树算法: GENERIC_MST(G){ T=NULL; while T 未形成一棵生成树; do 找到一条最小代价边(u, v)并且加入T后不会产生回路; T=T U (u, v); }通用算法每次加入一条边以逐渐形成一棵生成树,下面介绍两种实现上述通用算法的途径。 一、普里姆(Prim)算法Prim算法构造最小生成树的过程如下图所示。初始时从图中任取一顶点(如顶点加入树T,此时树中只含有一个顶点,之后选择一个与当前T中顶点集合距离最近的顶点,并将该顶点和相应的边加入T,每次操作后T中的顶点数和边数都增1。以此类推,直至图中所有的顶点都并入T,得到的T就是最小生成树。此时T中必然有n-1条边。 通俗点说就是:从一个顶点出发,在保证不形成回路的前提下,每找到并添加一条最短的边,就把当前形成的连通分量当做一个整体或者一个点看待,然后重复“找最短的边并添加”的操作。 额,不得不说这样理解起来有点抽象,为了能描述这个算法,我们先构造一个邻接矩阵,如下图的右图所示。 于是普里姆(Prim) 算法代码如下,左侧数字为行号。其中INFINITY为权值极大值,不妨设65535,MAXVEX 为顶点个数最大值,此处大于等于9即可。 /*Prim算法生成最小生成树*/ void MiniSpanTree_Prim(G){ int min, i, j, k; int adjvex[MAXVEX]; //保存相关顶点下标 int lowcost[MAXVEX]; //保存相关顶点间边的权值 lowcost[0] = 0; //初始化第一个权值为0,即v0加入生成树 //lowcost的值为0,在这里就是此下标的顶点已经加入生成树 adjvex[0] = 0; //初始化第一个顶点下标为0 for(i=1; i min = INFINITY; //初始化最下权值为∞,通常设置一个不可能的很大的数字 j = 1; k = 0; //循环全部顶点 while(j min = lowcost[j]; //则让当前权值成为最小值 k = j; //将当前最小值的下标存入k } j++; } print("(%d, %d)", adjvex[k], k); //打印当前顶点边中权值的最小边 for(j=1; j lowcost[j] = G.arc[k][j]; //将较小权值存入lowcost adjvex[j] = k; //将下标为k的顶点存入adjvex } } } }由算法代码中的循环嵌套可得知此算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。 二、克鲁斯卡尔(Kruskal)算法与Prim算法从顶点开始扩展最小生成树不同,Kruskal 算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。 Kruskal算法构造最小生成树的过程如下图所示。初始时为只有n个顶点而无边的非连通图
T
=
V
,
T= {V, {}}
T=V,,每个顶点自成一个连通分量,然后按照边的权值由小到大的顺序,不断选取当前未被选取过且权值最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入
T
T
T,否则舍弃此边而选择下一条权值最小的边。以此类推,直至
T
T
T中所有顶点都在一个连通分量上。 我们将下面左图的邻接矩阵通过程序转化为右图的边集数组,并且对它们按权值从小到大排序。 此算法的Find函数由边数e决定,时间复杂度为 O ( l o g e ) O(loge) O(loge),而外面有一个for循环e次。所以克鲁斯卡尔算法的时间复杂度为 O ( e l o g e ) O(eloge) O(eloge)。 对比两个算法,克鲁斯卡尔算法主要是针对边来展开,边数少时效率会非常高,所以对于稀疏图有很大的优势;而普里姆算法对于稠密图,即边数非常多的情况会更好一些。 最短路径在网图和非网图中,最短路径的含义是不同的。由于非网图它没有边上的权值,所谓的最短路径,其实就是指两顶点之间经过的边数最少的路径;而对于网图来说,最短路径,是指两顶点之间经过的边上权值之和最少的路径,并且我们称路径上的第一个顶点是源点,最后一个顶点是终点。 一、迪杰斯特拉( Dijkstra )算法Dijkstra算法用于构建单源点的最短路径—,即图中某个点到任何其他点的距离都是最短的。例如,构建地图应用时查找自己的坐标离某个地标的最短距离。可以用于有向图,但是不能存在负权值。 我们以上图为例,通俗点说,这个迪杰斯特拉(Dijkstra) 算法,它并不是一下子求出了 v 0 v_0 v0到 v 8 v_8 v8的最短路径,而是一步步求出它们之间顶点的最短路径,过程中都是基于已经求出的最短路径的基础上,求得更远顶点的最短路径,最终得到你要的结果。 Dijkstra算法设置一个集合S记录已求得的最短路径的顶点。 在构造的过程中还设置了个辅助数组: dist[]:记录从源点
v
0
v_0
v0到其他各顶点当前的最短路径长度,它的初态为:若从
v
0
v_0
v0到
v
i
v_i
vi;有弧,则dist[i]为弧上的权值;否则置dist[i]为
∞
∞
∞。 显然,Dijkstra 算法也是基于贪心策略的。使用邻接矩阵或者带权的邻接表表示时,时间复杂度为 O ( V 2 ) O(V^2) O(V2)。 人们可能只希望找到从源点到某个特定顶点的最短路径,但这个问题和求解源点到其他所有顶点的最短路径一样复杂,时间复杂度也为 O ( V 2 ) O(V^2) O(V2)。 二、弗洛伊德( Floyd )算法定义一个n阶方阵序列
A
(
−
1
)
,
A
(
0
)
,
.
.
.
,
A
(
n
−
1
)
A^{(-1)},A^{(0)},...,A^{(n-1)}
A(−1),A(0),...,A(n−1),其中,
A
(
−
1
)
[
i
]
[
j
]
=
a
r
c
s
[
i
]
[
j
]
A^{(-1)}[i][j] = arcs[i][j]
A(−1)[i][j]=arcs[i][j]
A
(
k
)
[
i
]
[
j
]
=
M
i
n
{
A
(
k
−
1
)
[
i
]
[
j
]
,
A
(
k
−
1
)
[
i
]
[
k
]
+
A
(
k
−
1
)
[
k
]
[
j
]
,
k
=
0
,
1
,
.
.
.
,
n
−
1
}
A^{(k)}[i][j] = Min\{A^{(k-1)}[i][j],A^{(k-1)}[i][k]+A^{(k-1)}[k][j],k=0,1,...,n-1\}
A(k)[i][j]=Min{A(k−1)[i][j],A(k−1)[i][k]+A(k−1)[k][j],k=0,1,...,n−1}式中,
A
(
0
)
[
i
]
[
j
]
A^{(0)}[i][j]
A(0)[i][j]是从顶点
v
i
v_i
vi到
v
j
v_j
vj、中间顶点的序号不大于k的最短路径的长度。Floyd算法是一个迭代的过程,每迭代一次,在从
v
i
v_i
vi到
v
j
v_j
vj的最短路径上就多考虑了一个顶点;经过
n
n
n次迭代后,所得到的
A
(
n
−
1
)
[
i
]
[
j
]
A^{(n-1)}[i][j]
A(n−1)[i][j]就是
v
i
v_i
vi到
v
j
v_j
vj的最短路径长度,即方阵
A
(
n
−
1
)
A^{(n-1)}
A(n−1)中就保存了任意一对顶点之间的最短路径长度。 应用Floyd算法求所有顶点之间的最短路径长度的过程如下表所示。 Floyd算法的时间复杂度为 O ( V 3 ) O(V^3) O(V3)。不过由于其代码很紧凑,且并不包含 其他复杂的数据结构,因此隐含的常数系数是很小的,即使对于中等规模的输入来说,它仍然是相当有效的。 Floyd算法允许图中有带负权值的边,但不允许有包含带负权值的边组成的回路。Floyd 算法同样适用于带权无向图,因为带权无向图可视为权值相同往返二重边的有向图。 也可以用单源最短路径算法来解决每对顶点之间的最短路径问题。轮流将每个顶点作为源点,并且在所有边权值均非负时,运行一次 Dijkstra算法,其时间复杂度为 O ( V 3 ) ∗ V = O ( V 3 ) O(V^3)*V = O(V^3) O(V3)∗V=O(V3)。 在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称为AOV网( Activity On VertexNetwork)。 若用DAG图(有向无环图)表示一个工程,其顶点表示活动,用有向边 < V i , V j > 表示活动 V i V_i Vi必须先于活动 V j V_j Vj进行的这样一种关系。在AOV网中,活动 V i V_i Vi是活动 V j V_j Vj的直接前驱,活动 V j V_j Vj是活动 V i V_i Vi的直接后继,这种前驱和后继关系具有传递性,且任何活动 V i V_i Vi不能以它自己作为自己的前驱或后继。 设 G = ( V , E ) G=(V,E) G=(V,E)是一个具有n个顶点的有向图, V V V中的顶点序列 V 1 , V 2 , . . . V n V_1, V_2, ... V_n V1,V2,...Vn,满足若从顶点 V i V_i Vi到 V j V_j Vj有一条路径,则在顶点序列中顶点 V i V_i Vi必在顶点 V j V_j Vj之前。则我们称这样的顶点序列为一个拓扑序列。 所谓拓扑排序,其实就是对一个有向图构造拓扑序列的过程。每个AOV网都有一个或多个拓扑排序序列。 二、算法对一个AOV网进行拓扑排序的算法有很多,下面介绍比较常用的一种方法的步骤: ①从AOV网中选择一个没有前驱的顶点并输出。②从网中删除该顶点和所有以它为起点的有向边。③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。如果输出顶点数少了,哪怕是少了一个,也说明这个网存在环(回路),不是AOV网。
由于输出每个顶点的同时还要删除以它为起点的边,故拓扑排序的时间复杂度为 O ( V + E ) O(V+E) O(V+E)。 此外,利用深度优先遍历也可实现拓扑排序。 用拓扑排序算法处理AOV网时,应注意以下问题: ①入度为零的顶点,即没有前驱活动的或前驱活动都已经完成的顶点,工程可以从这个顶点所代表的活动开始或继续。 ②若一个顶点有多个直接后继,则拓扑排序的结果通常不唯一;但若各个顶点已经排在一个线性有序的序列中,每个顶点有唯一的前驱后继关系,则拓扑排序的结果是唯一的。 ③由于AOV网中各顶点的地位平等,每个顶点编号是人为的,因此可以按拓扑排序的结果重新编号,生成AOV网的新的邻接存储矩阵,这种邻接矩阵可以是三角矩阵;但对于一般的图来说,若其邻接矩阵是三角矩阵,则存在拓扑序列;反之则不一定成立。 关键路径 一、定义拓扑排序主要是为解决一个工程能否顺序进行的问题,但有时我们还需要解决工程完成需要的最短时间问题。 在带权有向图中,以顶点表示事件,以有向边表示活动,以边上的权值表示完成该活动的开销(如完成活动所需的时间),称之为用边表示活动的网络,简称AOE网。AOE网和AOV网都是有向无环图,不同之处在于它们的边和顶点所代表的含义是不同的,AOE网中的边有权值;而AOV网中的边无权值,仅表示顶点之间的前后关系。 AOE网具有以下两个性质: ①只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始;②只有在进入某顶点的各有向边所代表的活动都已结束时,该顶点所代表的事件才能发生。
在分析算法之前,需要了解几个重要的参数: 1.事件的最早发生时间 v e ve ve:即顶点 V k V_k Vk的最早发生时期。 2.事件的最晚发生时间 v l vl vl:即顶点 V k V_k Vk的最晚发生时间,也就是每个顶点对应的事件最晚需要开始的时间,超出此时间将会延误整个工期。 3.活动的最早开始时间 e e e:即弧 a i a_i ai的最早发生时间。 4.活动的最晚开始时间 l l l:即弧 a i a_i ai的最晚发生时间,也就是不推迟工期的最晚开工时间。 5.一个活动 a i a_i ai的最迟开始时间 l ( i ) l(i) l(i)和其最早开始时间 e ( i ) e(i) e(i)的差额 d ( i ) = l ( i ) − e ( i ) d(i) =l(i)- e(i) d(i)=l(i)−e(i):它是指该活动完成的时间余量,即在不增加完成整个工程所需总时间的情况下,活动 a i a_i ai可以拖延的时间。若一个活动的时间余量为零,则说明该活动必须要如期完成,否则就会拖延整个工程的进度,所以称 l ( i ) − e ( i ) = 0 l(i)- e(i) = 0 l(i)−e(i)=0即 l ( i ) = e ( i ) l(i)=e(i) l(i)=e(i)的活动 a i a_i ai是关键活动。 求关键路径的算法步骤如下: 从源点出发,令 v e ( 源 点 ) = 0 ve(源点)=0 ve(源点)=0, 按拓扑排序求其余顶点的最早发生时间 v e ( ) ve() ve()。从汇点出发,令 v l ( 汇 点 ) = v e ( 汇 点 ) vl(汇点)= ve(汇点) vl(汇点)=ve(汇点),按逆拓扑排序求其余顶点的最迟发生时间 v l ( ) vl() vl()。根据各顶点的 v e ( ) ve() ve()值求所有弧的最早开始时间 e ( ) e() e()。根据各顶点的 v l ( ) vl() vl()值求所有弧的最迟开始时间 l ( ) l() l()。求AOE网中所有活动的差额 d ( ) d() d(), 找出所有 d ( ) = 0 d()=0 d()=0的活动构成关键路径。
对于关键路径,需要注意以下几点: ①关键路径上的所有活动都是关键活动,它是决定整个工程的关键因素,因此可通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动,因为一旦缩短到一定的程度,该关键活动就可能会变成非关键活动。 ②网中的关键路径并不唯一, 且对于有几条关键路径的网,只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期,只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。 总结图是计算机科学中非常常用的一类数据结构,同时也是最复杂的数据结构了,对它的学习,涉及到顺序表、链表、栈、队列、树等之前学的几乎所有数据结构,所以学习图之前要对这几种数据结构都要有所了解才行。 附录 上文链接数据结构:树 下文链接数据结构:查找 专栏数据结构专栏 参考资料1、严蔚敏、吴伟民:《数据结构(C语言版)》 2、程杰:《大话数据结构》 3、王道论坛:《数据结构考研复习指导》 4、托马斯·科尔曼等人:《算法导论》 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |