北京理工大学数据结构图课件

1、第7章 图第7章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的最小生成树7.1 图的定义与术语一、图的定义1、图(Graph)图G是由两个集合V(G)和E(G)组成的,记为G=(V,E) 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对。图的分类 有向图 无向图37.1 图的定义与术语2、有向图有向图G是由两个集合V(G)和E(G)组成的。 其中：V(G)是顶点的非空有限集。 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v,w是顶点，v为弧尾，w为弧头。47.1 图的定义与术语例如： G1 = V1 = A

2、, B, C, D, E E1 = , , , , , , EACBD57.1 图的定义与术语3、无向图无向图G是由两个集合V(G)和E(G)组成的。 其中：V(G)是顶点的非空有限集。 E(G)是边的有限集合，边是顶点的无序对，记为 (v,w) 或 (w,v)，并且(v,w)=(w,v)。67.1 图的定义与术语例如： G2 = V2 = v0 ,v1,v2,v3,v4 E2 = (v0,v1), (v0,v3), (v1,v2), (v1,v4), (v2,v3), (v2,v4) V0V4V3V1V277.1 图的定义与术语例如： G2 = V2 = v0，v1，v2，v3 E2 = ,

3、 , , V0 V1 V2 V3 例245136G1V(G1) = 1 , 2 , 3 , 4 , 5, 6 E(G1) = , , , , , , 87.1 图的定义与术语图的应用举例例1、交通图（公路、铁路） 顶点：地点边：连接地点的路例2、电路图 顶点：元件边：连接元件之间的线路例3、通讯线路图 顶点：地点边：地点间的连线例4、各种流程图如产品的生产流程图。 顶点：工序边：各道工序之间的顺序关系97.1 图的定义与术语二、图的基本术语1、邻接点及关联边 邻接点：边的两个顶点 关联边：若边e= (v, u), 则称顶点v、u 关联边e2、顶点的度、入度、出度 顶点V的度 = 与V相关联的边

4、的数目 在有向图中： 顶点V的出度 = 以V为起点有向边数 顶点V的入度 = 以V为终点有向边数 顶点V的度 = V的出度+V的入度 设图G 的顶点数为 n，边数为 e 图的所有顶点的度数和 = 2*e （每条边对图的所有顶点的度数和“贡献”2度） V0 V4 V3 V1 V2eV0V1V2V3107.1 图的定义与术语3、路径、回路 无向图 G =（V，E）中的顶点序列v1, v2, , vk，若 (vi, vi+1)E ( i=1, 2, , k-1)，v=v1, u=vk，则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路。无向图G1 V0 V4 V3 V1 V2路径：V0,

5、 V1, V2, V3回路：V0, V1, V2, V3, V0 117.1 图的定义与术语3、路径、回路 有向图 D =（V，E）中的顶点序列 v1, v2, , vk，若 E (i=1, 2, , k-1)，v=v1，u=vk，则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路。有向图G2V0V1V2V3路径：V0, V2, V3回路：V0, V2, V3, V0 127.1 图的定义与术语4、连通图（强连通图） 在无（有）向图 G= 中，若对任何两个顶点 v、u 都存在从 v 到 u 的路径，则称G是连通图（强连通图） 非连通图 连通图 强连通图 非强连通图 V0 V1 V2

6、 V3 V0 V2 V3 V1 V5 V4 V0 V4 V3 V1 V2 V0 V1 V2 V3137.1 图的定义与术语5、子图 设有两个图 G=（V，E），G1=（V1，E1），若V1 V，E1 E，而且E1关联的顶点都在 V1 中，则称 G1 是 G 的子图；(b)、(c) 都是 (a) 的子图(d) V4 V1 V2(c) V0 V4 V3 V1 V2(a) V0 V4 V3 V1 V2(b) V0 V4 V3 V1 V2147.1 图的定义与术语6、连通分量（强连通分量）：无（有）向图的极大（强）连通子图。极大（强）连通子图：该子图是（强）连通子图，若再将G的任何不在该子图中的顶点加

7、入，子图就不再（强）连通。非连通图 V0 V2 V3 V1 V5 V4连通分量157.1 图的定义与术语强连通分量 V0 V1 V2 V3非连通图 V0 V2 V3 V1167.1 图的定义与术语7、生成树 包含无向图 G 所有顶点的极小连通子图称为G生成树。 极小连通子图意思是：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通。G1的生成树 V0 V4 V3 V1 V2章连通图G1 V0 V4 V3 V1 V2 连通 所有顶点 无回路17 V0 V1 V2 V37.2 图的存储结构一、数组表示法（邻接矩阵表示）邻接矩阵：G的邻接矩阵是满足如下条件的n阶矩阵：Aij=1 若(vi,

8、vj)E 或 E0 否则0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0在数组表示法中，用邻接矩阵表示顶点间的关系 V0 V4 V3 V1 V20 1 1 00 0 0 00 0 0 11 0 0 0187.2 图的存储结构二、邻接表：图的链式存储结构1、无向图的邻接表 顶点：通常按编号顺序将顶点数据存储在一维数组中； 关联同一顶点的边：用线性链表存储。 V0 V4 V3 V1 V2 0 1 2 3 4m-1V0V1V2V3V413212013420419typedef struct tnode /表头结点 int vexdata; ArcNode *

9、 firstarc; VNode, AdjList MAX_VERTEX_NUM ;7.2 图的存储结构typedef struct ArcNode/链表结点 int adjvex; struct ArcNode *next; ArcNode;adjvex nextvexdata firstarctypedef struct/图 AdjList vertices; int vexnum, arcnum; / 顶点数和弧数int kind; / 图的种类ALGraph;207.2 图的存储结构无向图的邻接表的特点 1）在G邻接表中，同一条边对应两个结点； 2）顶点v的度：等于v对应线性链表的长度

10、； 3）判定两顶点v ，u是否邻接：要看v对应线性链表中有无对应的结点。 4）在G中增减边：要在两个单链表插入、删除结点； 5）设存储顶点的一维数组大小为 m（m图的顶点数n），图的边数为 e，G占用存储空间为：m+2*e。G占用存储空间与G的顶点数、边数均有关；适用于边稀疏的图。217.2 图的存储结构2、有向图的邻接表顶点：用一维数组存储（按编号顺序）以同一顶点为起点的弧：用线性链表存储0123v0v2v3v1vexdatafirstarc 2 1 3 0adjvexnext类似于无向图的邻接表，所不同的是：以同一顶点为起点的弧：用线性链表存储。V0V1V2V3227.2 图的存储结构3、

11、有向图的逆邻接表顶点：用一维数组存储（按编号顺序）以同一顶点为终点的弧：用线性链表存储。0123v0v2v3v1vexdatafirstarc 3 0 0 2类似于有向图的邻接表，所不同的是：以同一顶点为终点弧：用线性链表存储V0V1V2V3章237.3 图的遍历连通图的深度遍历（DFS）从图中某顶点v出发： 1）访问顶点v； 2）对v的每个未被访问的邻接点wj，从wj出发，继续对图进行深度优先遍历。深度遍历： V1,V2,V4,V5,V8,V3,V6,V7 例 V1 V8 V7 V6 V5 V4 V3 V2V1V2V4V3V8V7V6 V5深度遍历： V1,V3,V6,V7,V2,V5,V8

12、,V4247.3 图的遍历图的深度遍历（DFS）Vw1SG1SG2SG3w2w3w2 W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。访问顶点 V ：for (W1、W2、W3 ) 若该邻接点W未被访问， 则从它出发进行深度优先搜索遍历。257.3 图的遍历图的深度遍历（DFS）Vw1SG1SG2SG3w2w3w2从图解可见：1. 从深度优先搜索遍历连通图的过程类似于树的先根遍历；解决的办法是：为每个顶点设立一个 “访问标志 visitedw”。2. 如何判别V的邻接点是否被访问？267.3 图的遍历Boolean visitedMAX;

13、 / 访问标志数组Status (*VisitFunc)(int v); / 访问函数void DFS ( Graph G, int v) / 从顶点v出发，深度优先搜索遍历连通图 G visitedv = TRUE; VisitFunc(v); for ( w=FirstAdjVex(G, v);w=0; w=NextAdjVex(G,v,w) ) if ( !visitedw ) DFS(G, w); / 对v的尚未访问的邻接顶点w / 递归调用DFS / DFS277.3 图的遍历非连通图的深度优先搜索遍历 首先将图中每个顶点的访问标志设为 FALSE，之后搜索图中每个顶点，如果未被访问

14、，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。287.3 图的遍历void DFSTraverse ( Graph G, Status (*Visit) (int v) / 对图 G 作深度优先遍历。 VisitFunc = Visit; for ( v=0; vG.vexnum; +v ) visitedv = FALSE; / 访问标志数组初始化 for ( v=0; vG.vexnum; +v ) if (!visitedv) DFS(G, v); / 对尚未访问的顶点调用DFS297.3 图的遍历例如：abchdekfgF F F F F F F F FTTTTTT

15、TTTachdkfe bgachkfedbg访问标志:访问次序: a b c d e f g h k 0 1 2 3 4 5 6 7 8307.3 图的遍历图的深度遍历（DFS）V1V2V4V5V3V7V6V8例12341342vexdatafirstarc 2 7 8 3adjvexnext55 6 4 8 2678678 7深度遍历：V1V3 V7 V6 V2 V4 V8 V5317.3 图的遍历图的广度遍历（BFS） 从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被

16、访问到。 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。327.3 图的遍历图的广度遍历（BFS）从图中某顶点v出发：1) 访问顶点v2) 访问v的所有未被访问的邻接点w1,w2,wk3) 依次从这些邻接点出发，访问它们的所有未被访问的邻接点，直到图中所有访问过的顶点的邻接点都被访问到。V1V8V7V6V5V4V3V2V1 V2 V4 V3 V8 V7 V6 V5V1,V2,V3,V4,V8,V5,V6,V7V1,V3,V2,V6,V7,V4,V5,V8337.3 图的遍历void BFSTraverse ( Graph G,

17、 Status (*Visit) (int v) ) for ( v=0; vG.vexnum; +v ) visitedv = FALSE; / 初始化访问标志 InitQueue(Q); / 置空的辅助队列Q for ( v=0; v=0; w=NextAdjVex(G,u,w) ) if ( ! visitedw ) visitedw=TRUE; Visit(w); EnQueue(Q, w); / 访问的顶点w入队列 / if / while357.3 图的遍历图的广度遍历（BFS）（请对照教材第170页）例1423512341342vexdatafirstarc 5 5 4 3adjvexnext55 1 5 1 1 4 3 2 20 1 2 3 4 51fr遍历序列：10 1 2 3 4 54fr遍历序列：1 40 1 2 3 4 54 3fr遍历序列：1 4 3367.3 图的遍历图的广度遍历（BFS）例142350 1 2 3 4 54 3 2fr遍历序列：1 4 3 20 1 2 3 4 5 3 2fr遍历序