71 图的定义和基本术语 71 图的定义和基本术语

第七章图7.1图的定义和基本术语7.2图的存储结构7.2.1数组表示法7.2.2邻接表7.2.3十字链表7.2.4邻接多重表7.3图的遍历7.3.1深度优先搜索7.3.2广度优先搜索7.4图的连通性问题7.4.1无向图的连通分量和生成树7.4.2最小生成树7.5有向无环图及其应用7.5.1拓扑排序7.5.2关键路径7.6最短路径7.6.1从某个源点到其余各顶点的最短路径7.6.2每一对顶点间的最短路径图(Graph)是较线性表和树更为复杂的结构。图中任意数据两个元素之间都可能相关。第七章图G1=(V1,{A1})V1={v1,v2,v3,v4}A1={v1,v2,v1,v3,v3,v4,v4,v1}G2=(V2,{E2})V2={v1,v2,v3,v4,v5}E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}7.1图的定义和基本术语V1V3V4V2有向图G1V1V4V5V2无向图G2V3顶点弧弧尾弧头顶点边7.1图的定义和基本术语(续一)完全图：n个顶点有n(n-1)/2条边的无向图有向完全图：n个顶点有n(n-1)条弧的有向图稀疏图：有很少条边的图（如边数enlogn)稠密图：非稀疏图权：与边或弧相关的数网络：带权的图V1V3V2V1V3V2274子图：G=(V,{E})和G1=(V1,{E1})若V1属于V,E1属于E则G1是G的子图7.1图的定义和基本术语(续二)V1V1V3V4V2V3V1V3V4V1邻接点：无向图中有边相连的两个顶点互为邻接点顶点的度：无向图中和某顶点相连的邻接点数入度：有向图中指向某顶点的弧的数目出度：有向图中从某顶点出发的弧的数目7.1图的定义和基本术语(续三)路径：两个顶点之间的顶点序列，该序列的每个顶点与其前驱是邻接点，每个顶点与其后继也是邻接点回路（环）：第一顶点和最后顶点相同的路径简单路径：顶点不重复的路径连通：两个顶点之间有路径连通图：任意两个顶点之间有路径连通分量：无向图中的极大连通子图。强连通图：任意两个顶点之间有双向路径强连通分量：有向图中的极大强连通子图。连通图的生成树：极小连通子图。不唯一，但n个顶点的生成树有且仅有n-1条边。生成森林：7.2图的存储结构7.2.1数组表示法#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM20typedefenum{DG,DN,AG,AN}GraphKind;typedefstructArcCell{VRTypeadj;InfoType*info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]typedefstruct{VetexTypevexs[MAX_VERTEX_NUM];AdjMatrixarc;intvexnum,arcnum;GraphKindkind;}MGraph;数组表示法(邻接矩阵)无向图、有向图、网均适用易求各顶点的度。例如有向图G1和无向图G2的邻接矩阵为0110000000011000G1.arc=0101010101010111010001100G2.arc=n2的存储量无向图的邻接矩阵总是对称的--可以采用压缩存储网及其邻接矩阵V1V3V4V2V5V65489731565(a)网5748956531(b)邻接矩阵7.2.2邻接表---链式存储结构#defineMAX_VERTEX_NUM20typedefstructArcNode{intadjvex;structArcNode*nextarc;InfoType*info;}ArcNode;typedefstruct{AdjListverteces;intvexnum,arcnum;intkind;}ALGraph;typedefstructVNode{VetexTypedata;ArcNode*firstarc;}Vnode,AdjList[MAX_VERTEX_NUM];datafirstarc头结点Adjvexnextarcinfo表结点邻接表的链式存储结构示意图0123V1V2^V3V40123V1V2V3V401234V1V2V3V4V521^3^3^0^0^2^0^31^20^21^20^431^4G1的邻接表G2的邻接表G1的逆邻接表邻接表：求出度容易，求入度难邻接表：求入度容易，求出度难7.3图的遍历图的遍历：从图的某顶点出发，访问所有顶点，且每个顶点仅被访问一次。两种遍历图的路径：深度优先搜索和广度优先搜索它们对无向图和有向图都适用深度优先搜索类似于树的先根遍历广度优先搜索类似于树的层次遍历7.3.1深度优先搜索V1V2V4V5V8V3V6V7V1V2V4V8V5V3V6V712345678visited11011001遍历顺序：非连通的图重复上述过程,使每个顶点均被访问V1V2stackV4V8V5深度优先搜索算法Booleanvisited[MAX];Status(*VisitFunc)(intv);voidDFSTraverse(GraphG,Status(*visit)(intv)){VisitFunc=visit;for(v=0;vG.vexnum;++v)visited[v]=FALSE;for(v=0;vG.vexnum;++v)if(!visited[v])DFS(G,v);}voidDFS(GraphG,intv){visited[v]=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);}7.3.2广度优先搜索V1V2V4V5V8V3V6V7V1V2V3V4V5V6V7V812345678visited10000000V2V3Queue遍历顺序：非连通的图重复上述过程,使每个顶点均被访问voidBFSTraverse(GraphG,Status(*visit)(intv)){for(v=0;vG.vexnum;++v)visited[v]=FALSE;IntiQueque(Q);for(v=0;vG.vexnum;++v)if(!visited[v]){EnQueue(Q,v);while(!QueueEmpty(Q)){DeQueue(u);visited[u]=TRUE;Visit(u);for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))if(!visited[w]){visited[w]=TRUE;visited(w);EnQueue(G,w);}}}}广度优先搜索算法7.4图的连通性问题7.4.1无向图的连通分量和生成树V1V2V4V5V8V3V6V7深度优先生成树V1V2V4V5V8V3V6V7广度优先生成树7.4.3最小生成树连通网的生成树一棵生成树的代价---树上各边的代价之和最小生成树----一个连通网的所有生成树中代价最小的生成树求最小生成树的Prim算法求最小生成树的Kruskal算法Prim算法示意图V1V2V4V5V3V66555662134V1V2V4V5V3V61V1V2V4V5V3V614V1V2V4V5V3V6142V1V2V4V5V3V61425V1V2V4V5V3V614253Kruskal算法示意图V1V2V4V5V3V66555662134V1V2V4V5V3V61V1V2V4V5V3V612V1V2V4V5V3V6132V1V2V4V5V3V61423V1V2V4V5V3V614253实验与习题理论习题7.1,7.2,7.4,7.57.7实验算法题:7.14