浙江大学：《数据结构与算法》第七章 图

第七章图 7.1图的定义和基本术语 7.2-图的存储结构 7.2.1数组表示法 7.2.2邻接表 7.2.3十字链表 7.2.4邻接多重表 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每一对顶点间的最短路径

第七章 图 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,{A13) V1={ V1, Vo, V2, v A1=(V1,V2>,<V1, V1, V2, V3,VA, V V1, V V2, V

图(Graph)是较线性表和树更为复杂的结构。 图中任意数据两个元素之间都可能相关。 第七章 图 G1 = (V1, { A1}) V1 = {v1,v2,v3,v4} A1 = {,,,} G2 = (V2, { E2}) V2 = {v1,v2,v3,v4,v5} E2 = {(v1,v2),(v1,v4),(v2,v3),(v2,v5) ,(v3,v4),(v3,v5)}

7.1图的定义和基本术语 有向图G 无向图G2 顶点 顶点 弧 边 弧尾 弧头

7.1 图的定义和基本术语 V1 V3 V4 V2 有向图 G1 V1 V4 V5 V2 无向图 G2 V3 顶点 弧 弧尾 弧头 顶点 边

7.1图的定义和基本术语(续 完全图:n个顶点有n(n-1)/2条边的无向图 有向完全图:n个顶点有n(n-1)条弧的有向图 稀疏图:有很少条边的图(如边数e< nlogn) 稠密图:非稀疏图 权 与边或弧相关的数 网络:带权的图

7.1 图的定义和基本术语(续一) 完全图：n个顶点有n(n-1)/2条边的无向图 有向完全图： n个顶点有n(n-1)条弧的有向图 稀疏图：有很少条边的图（如边数e < nlogn) 稠密图：非稀疏图 权： 与边或弧相关的数 网络： 带权的图 V1 V3 V2 V1 V3 V2 2 7 4

7.1图的定义和基本术语(续二 子图:G=(V,E})和G1=(V1,E1}) 若V1属于V,E1属于E则G1是G的子图 邻接点:无向图中有边相连的两个顶点互为邻接点 顶点的度:无向图中和某顶点相连的邻接点数 入度:有向图中指向某顶点的弧的数目 出度:有向图中从某顶点出发的弧的数目

子图： G =(V,{E})和G1 = (V1,{E1}) 若V1属于V, E1属于E 则G1是G的子图 7.1 图的定义和基本术语(续二) V1 V1 V3 V4 V2 V3 V1 V3 V4 V1 邻接点：无向图中有边相连的两个顶点互为邻接点 顶点的度：无向图中和某顶点相连的邻接点数 入度：有向图中指向某顶点的弧的数目 出度：有向图中从某顶点出发的弧的数目

7.1图的定义和基本术语(续三) 路径:两个顶点之间的顶点序列,该序列的每个顶点 与其前驱是邻接点,每个顶点与其后继也是邻接点 回路(环):第一顶点和最后顶点相同的路径 简单路径:顶点不重复的路径 连通 两个顶点之间有路径 连通图:任意两个顶点之间有路径 连通分量:无向图中的极大连通子图。 强连通图:任意两个顶点之间有双向路径 强连通分量:有向图中的极大强连通子图 连通图的生成树:极小连通子图。 不唯一,但n个顶点的生成树 有且仅有n-1条边 生成森林

7.1 图的定义和基本术语(续三) 路径：两个顶点之间的顶点序列，该序列的每个顶点 与其前驱是邻接点，每个顶点与其后继也是邻接点 回路（环）：第一顶点和最后顶点相同的路径 简单路径： 顶点不重复的路径 连通： 两个顶点之间有路径 连通图： 任意两个顶点之间有路径 连通分量： 无向图中的极大连通子图。 强连通图：任意两个顶点之间有双向路径 强连通分量：有向图中的极大强连通子图。 连通图的生成树：极小连通子图。 不唯一，但n个顶点的生成树 有且仅有n-1条边。 生成森林：

7.2图的存储结构 7.2.1数组表示法 #define INFINITY INT MAX #define MAX VERTEX NUM 20 typedef enum(DG, DN, AG, AN GraphKind typedef struct ArcCell VRType ad Info Type *info J ArcCell, AdjMatrix[MAX VERTEX NUM I[MAX VERTEX NUM I typedef struct i VetexType vexs[MAX VERTEX NUM I AdjMatrix arc nt vexnum, arcum GraphKind kind )MGraph

7.2 图的存储结构 7.2.1 数组表示法 #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 typedef enum{DG, DN, AG, AN} GraphKind; typedef struct ArcCell{ VRType adj; InfoType *info; }ArcCell, AdjMatrix[MAX_VERTEX_NUM ][MAX_VERTEX_NUM ] typedef struct { VetexType vexs[MAX_VERTEX_NUM ]; AdjMatrix arc; int vexnum, arcnum; GraphKind kind; }MGraph;

数组表示法(邻接矩阵) 无向图、有向图、网均适用 易求各顶点的度。 例如有向图G1和无向图G2的邻接矩阵为 0110 01010 0000 10101 G1.arc 0001 Go.arc=0101 1000 10100 01100 n2的存储量 无向图的邻接矩阵总是对称的一可以采用压缩存储

数组表示法(邻接矩阵) 无向图、有向图、网均适用 易求各顶点的度。 例如有向图G1和无向图G2的邻接矩阵为 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 G1 .arc = 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 G2 .arc = n 2的存储量 无向图的邻接矩阵总是对称的--可以采用压缩存储

网及其邻接矩阵 5 5∞7 4 4 0∞O 6 (b)邻接矩阵

网及其邻接矩阵 V1 V3 V4 V2 V5 V6 5 4 8 9 7 3 1 5 6 5 (a) 网  5  7     4    8     9   5   6    5   3    1  (b) 邻接矩阵

7.2.2邻接表 链式存储结构 #define mAX VErTEX NUM 20 typedef struct ArcNode& 表结点 int adive Adivex nextarc info struct ArcNode * nextarc Info Type * info BArcOde typedef struct VNode 头结点 data firstarc VetexType data ArcNode *firstarc i Vnode, AdjList [MAX VERTEX NUM I typedef struct i AdjList vertices Int vexnum, arcum, kind JALGraph

7.2.2 邻接表 --- 链式存储结构 #define MAX_VERTEX_NUM 20 typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; InfoType *info; }ArcNode; typedef struct { AdjList verteces; int vexnum, arcnum; int kind; }ALGraph; typedef struct VNode{ VetexType data; ArcNode *firstarc; } Vnode, AdjList [MAX_VERTEX_NUM ]; 头结点 data firstarc Adjvex nextarc info 表结点