《数据结构、代码》第5章 图

第5章图张成文北京邮电大学计算机学院编辑ppt第5章图第5章图5.1图的基本概念

非线性结构，数据元素之间呈多对多的关系。5.1.1图的定义Graph=(V,VR)V：顶点(数据元素)的有穷非空集合。

VR：弧(关系)的有穷集合。2编辑ppt第5章图例1：G1=(V1,VR1)V1={A,B,C,D,E}VR1={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}EACBD例2：G2=(V2,VR2)V2={A,B,C,D,E,F}VR2={(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)}BCAFED3编辑ppt第5章图5.1.2图的相关术语顶点数据元素所构成的结点。有向图弧的顶点偶对是有序的。对弧<vi,vj>而言，

vi是弧尾/初始点；vj是弧头/终端点。无向图弧的顶点偶对是无序的。

(vi,vj)和(vj,vi)代表同一条边(ij)。(无向)完全图每个顶点与其余顶点都有边的无向图。顶点数为n时，边数e=n(n-1)/2有向完全图每个顶点与其余顶点都有弧的有向图。顶点数为n时，弧数e=n(n-1)稀疏图有很少边或弧的图。（e<nlogn）稠密图有较多边或弧的图。vivjvivj4编辑ppt第5章图权图中的边或弧具有一定的大小的概念。网边/弧带权的图。邻接有边/弧相连的两个顶点之间的关系。存在(vi,vj)，则称vi和vj互为邻接点；存在<vi,vj>，则称vi邻接到vj，vj邻接于vi

关联(依附)边/弧与顶点之间的关系。存在(vi,vj)/<vi,vj>，则称该边/弧关联于vi和vj顶点的度与该顶点相关联的边的数目，记为D(v)。

入度ID(v)：有向图中，以该顶点为弧头的弧数目。

出度OD(v)：有向图中，以该顶点为弧尾的弧数目。vivjvivjABEC辑ppt第5章图路径

接续的边构成的顶点序列。

路径长度路径上边或弧的数目/权值之和。

回路(环)第一个顶点和最后一个顶点相同的路径。

简单路径序列中顶点均不相同的路径。

简单回路(简单环)除路径起点和终点相同外，其余顶点均不相同的路径。从A到F长度为3的路径

{A,B,C,F}ABECF6编辑ppt第5章图连通图无向图中，任何一对顶点间都存在路径。

连通分量无向图中的极大连通子图。强连通图有向图中，任何一对顶点间都存在路径。

强连通分量有向图中的极大连通子图。7编辑ppt第5章图生成有向树生成森林子图对于图G=(V,E)和G’=(V’,E’)，如果V’V，E’E，且E’关联的顶点都在V’中，则称G’是G的子图。生成子图由图的全部顶点和部分边组成的子图称为原图的生成子图。生成树包含图中全部顶点的极小连通子图。有向树图中恰有一个顶点入度为0，其余顶点入度均为1。生成森林有向图中，包含所有顶点的若干棵有向树构成的子图。e=n-18编辑ppt第5章图5.2图的存储结构5.2.1数组/邻接矩阵表示法(顺序存储方式)[例1]无向图

顶点数组vexs

邻接矩阵(边表)arcs0A01101B10112C11013D01100AB12CD3G1无向图的邻接矩阵具有对称性[例2]有向网顶点数组vexs

邻接矩阵(边表)arcs0A0321B042C503D2032542G20AB12CD39编辑ppt第5章图5.2.2邻接表顺序存储+链式存储

顶点顺序表邻接顶点的单链表(边表)G1:0A12^1B023^2C013^3D12^G2:0A1322^1B34^2C15^3D22^

出边表(逆邻接表时用入边表)nextarcadjvexnextarcweightadjvex无向图有向网0AB12CD30AB12CD332542datafirstarcvertices10编辑ppt第5章图5.3图的遍历深度优先遍历(树的先根遍历的推广)广度优先遍历(树的按层次遍历的推广)[例]v1v2v3v4v5v6v7v8深度：v1v2v4v8v5v6v3v7广度：v1v2v3v4v5v6v7v8设从v1出发遍历数据结构：主——图的存储结构辅——数组visited[0..n-1]11编辑ppt第5章图5.3.1深度优先搜索递归的算法思想

(1)访问顶点v，并记录v已被访问

(2)依次从v的未访问的邻接点出发，深度优先搜索图G。算法描述typedefenum{FALSE,TRUE}Boolean;//FALSE为0，TRUE为1Booleanvisited[MAX_VERTEX_NUM];//辅助访问标志向量voidDFSTraverse(GraphG){for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//标志向量初始化

for(v=0;v<G.vexnum;++v)

if(!visited[v])DFS(G,v);}//DFSTraverse0123412编辑ppt第5章图voidDFS(GraphG,intv){visit(v);visited[v]=TRUE;//访问顶点v，并标记

for(w=FirstAdjVex(G,v);w>-1;w=NextAdjVex(G,v,w))

if(!visited[w])DFS(G,w);}//DFSvoidDFS(MGraphG,intv)//深度优先遍历邻接矩阵表示的图{visit(G.vexs[v]);visited[v]=TRUE;for(j=0;j<G.vexnum;++j)

if(G.arcs[v][j]!=0&&!visited[j])DFS(G,j);}//DFSvoidDFS(ALGraphG,intv)//深度优先遍历邻接表表示的图{visit(G.vertices[v].data);visited[v]=TRUE;p=G.vertices[v].firstarc;//取v边表的头指针

while(p){

if(!visited[p->adjvex])DFS(G,p->adjvex);p=p->nextarc;}}//DFS例13编辑ppt第5章图abchdekfg812345670FFFFFFFFF012345678TTTTTTTTTachdkfebgachkfedbg访问标志:访问次序:例achdkfe14编辑ppt第5章图5.3.2广度(宽度)优先遍历[算法思想](1)访问顶点v，并记录它已被访问；顶点v入队列；

(2)如果队列空，则退出；否则，从队中取出一顶点；

(3)求该顶点的一个邻接点；如果此邻接点未被访问，则访问它，并记录它已被访问，将其入队列；

(4)如果该顶点还有下一个邻接点，则转(3)；否则，转(2)12345615编辑ppt第5章图算法描述voidBFSTraverse(GraphG){for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//标志向量初始化

InitQueue(Q);//辅助队列初始化

for(v=0;v<G.vexnum;++v)

if(!visited[v]){

visit(v);visited[v]=TRUE;EnQueue(Q,v);while(!QueueEmpty(Q)){DeQueue(Q,u);

for(w=FirstAdjVex(G,u);w>-1;w=NextAdjVex(G,u,w))if(!visited[w]){

visited[w]=TRUE;visit(w);EnQueue(Q,w);}}}}//BFSTraverse16编辑ppt第5章图[算法时间复杂度分析]

与深度优先遍历过程相同5.3.3图的遍历小结深度优先遍历算法借助于栈结构实现；广度优先遍历算法借助于队列结构实现图的遍历序列与算法和存储方式有关17编辑ppt第5章图5.3.4图的遍历应用举