第七章图 7.1图的基本概念 7.2图的存储 7.3图的遍历 7.4图的连通性问题 7.5有向无环图及其应用 7.6最短路径 ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 1 中国科学技术大学 第七章 图 7.1图的基本概念 7.2图的存储 7.3图的遍历 7.4图的连通性问题 7.5有向无环图及其应用 7.6最短路径
7.1图的基本概念 图(graph): 一个顶点(vertex)的有穷集V(G)和一个弧(arc)的 集合E(G)组成。记做：G=(V,E)。V是数据结构中 的数据元素，E是集合上的关系 ·弧(arc)、弧头（终点）、孤尾（起点） -表从v到w的弧 。 有向图(digraph)、无向图(undigraph)、边： -(V,w)代表和 ·有向网、无向网： 一带权的有向图和无向图 。 完全图(complete graph):边e为n(n-I)/2 。 有向完全图：弧e为n(n-I) ypb@ustc.edu.cn 2 中国科学技术大学
ypb@ustc.edu.cn 2 中国科学技术大学 7.1图的基本概念 • 图(graph)： – 一个顶点（vertex）的有穷集V(G)和一个弧(arc)的 集合E(G)组成。记做：G＝(V，E)。V是数据结构中 的数据元素，E是集合上的关系 • 弧(arc)、弧头（终点）、弧尾（起点）： – 表从v到w的弧 • 有向图(digraph) 、无向图(undigraph) 、边: – (v,w)代表和 • 有向网、无向网： – 带权的有向图和无向图 • 完全图（complete graph）：边e为n(n-1)/2 • 有向完全图：弧e为n(n-1)
0 Vo) @ (a)有向图G1 (b)无向图G2 10 8 o 15 20 30 20 30 10 15 (a)有向网G3 (b)无向网G4 ypb@ustc.edu.cn 3 中国科学技术大学
ypb@ustc.edu.cn 3 中国科学技术大学
● 稀疏图 （sparse graph):有向图enlogn 子图(subgraph) -G=(V,E),G'=(V,E')如V≤V且E≤E',则称G是G的子图 ·度(degree)、出度(OutDegree)、入度Indegree): 称u邻接到v,或v邻接自u。邻接到某顶点的弧的数目称该顶点的入度 Dy);邻接自某顶点的弧的数目称该顶点的出度OD(u);某顶点的入度、 出度之和为该顶点的度TD(v)】 路径和回路： 一有向路径无向路径，路径长度、回路或环 连通图和连通分量： 连通图（无向），强连通图（有向），连通分量 。 生成树、生成森林： 一连通图的生成树是极小连通子图。 有向图的生成森林由若干有向树组成，含有图中全部顶点和部分足以构成 若干颗不相交有向树的狐。 ypb@ustc.edu.cn 4 中国科学技术大学
ypb@ustc.edu.cn 4 中国科学技术大学 • 稀疏图（sparse graph）：有向图enlogn • 子图（subgraph）: – G=(V,E),G’=(V’,E’),如V’≦V且 E≦E’,则称G’是G的子图 • 度(degree)、出度(OutDegree)、入度(Indegree): – 称u邻接到v，或v邻接自u。邻接到某顶点的弧的数目称该顶点的入度 ID(v)；邻接自某顶点的弧的数目称该顶点的出度OD(u)；某顶点的入度、 出度之和为该顶点的度TD(v) • 路径和回路： – 有向路径/无向路径，路径长度、回路或环 • 连通图和连通分量： – 连通图(无向)，强连通图（有向），连通分量 • 生成树、生成森林： – 连通图的生成树是极小连通子图。 – 有向图的生成森林由若干有向树组成，含有图中全部顶点和部分足以构成 若干颗不相交有向树的狐
ADT Graph{ 数据对象：V是具有相同特性数据元素的集合。 数据关系：R={v,w∈V且P(v,w),其中表示从v 到w的狐，谓词P(v,w)表示狐的信息} 基本操作： 1)CreateGraph(&G,V,E) 2)DestroyGraph(&G) 3)LocateVex(G,u) 4) GetVex(G,v) 5)PutVex(&G,v,value) ypb@ustc.edu.cn 5 中国科学技术大学
ypb@ustc.edu.cn 5 中国科学技术大学 ADT Graph{ 数据对象：V是具有相同特性数据元素的集合。 数据关系：R={|v,w∈V且P(v,w),其中表示从v 到w的狐，谓词P(v,w)表示狐的信息} 基本操作： 1) CreateGraph(&G, V, E) 2) DestroyGraph(&G) 3) LocateVex(G，u) 4) GetVex(G，v) 5) PutVex(&G，v，value)
6)FirstAdiVex(G,v) 7)NextAdjVex(G,v,w) 8)Insert Vex(&G,v) 9)Delete Vex(&G,v) 10)InsertArc(&G,v,w) 11)DeleteArc(&G,v,w) 12)DFSTraverse(G,v,visit() 13)BFSTraverse(G,v,visit()) ADT Graph ypb@ustc.edu.cn 6 中国科学技术大学
ypb@ustc.edu.cn 6 中国科学技术大学 6) FirstAdjVex(G，v) 7) NextAdjVex(G，v，w) 8) InsertVex(&G，v) 9) DeleteVex(&G，v) 10) InsertArc(&G，v，w) 11) DeleteArc(&G，v，w) 12) DFSTraverse(G，v，visit()) 13) BFSTraverse(G，v，visit()) } ADT Graph
S 7.2图的存储 图的数组（邻接矩阵）存储表示 typedef enumDG,DN,AG,AN}GraphKind typedef struct ArcCell VRType adj; InfoType *info, }ArcCell,AdjMatrix[MAX V NUM]MAX V NUM]; typedef struct VertexType vexs[MAX V NUM]: AdjMatrix arcs; int vexnum arcnum; GraphKind kind; MGraph; ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 7 中国科学技术大学 7.2图的存储 • 图的数组（邻接矩阵）存储表示 typedef enum{DG，DN，AG，AN} GraphKind； typedef struct ArcCell{ VRType adj; InfoType *info; }ArcCell,AdjMatrix[MAX_V_NUM][ MAX_V_NUM]； typedef struct{ VertexType vexs[MAX_V_NUM]; AdjMatrix arcs; int vexnum,arcnum; GraphKind kind; }MGraph;
0 1 0 0∞ 8 ∞ 20 o 8 ∞ 15 ∞ 0 0 0 0 30 A1= A2= o∞ 15 ∞ 10 5 0 0 20 0∞ 10 o∞ 0 0 30 5 ∞ (a)G,的邻接矩阵 b)G4的邻接矩阵 20 30 V. ypb@ustc.edu.cn 8 中国科学技术大学
ypb@ustc.edu.cn 8 中国科学技术大学
S 7.2.2图的邻接表存储表示 typedefstruct ArcNode{ int adjvex; struct ArcNode *nextarc; InfoType *info; ArcNode typedefstruct VNode VertetType data; ArcNode *firsrarc, VNode,AdjList[MAX_VERTEX NUM]; typedefstruct{ AdList vertices; int vexnum,arcnum; GraphKind kind; }ALGraph; ypb@ustc.edu.cn 9 中国科学技术大学
ypb@ustc.edu.cn 9 中国科学技术大学 typedefstruct ArcNode{ int adjvex; struct ArcNode *nextarc; InfoType *info; } ArcNode； typedefstruct VNode{ VertetType data; ArcNode *firsrarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedefstruct{ AdList vertices; int vexnum,arcnum; GraphKind kind; }ALGraph; 7.2.2图的邻接表存储表示
V Vo 1 V 0☑ V2 0西 2 20西 o A 0西 2西 a)G1的邻接表 0)G2的邻接表 (⊙)G的逆邻接表 表结点 头结点 adjvex nextarc info data firstarc ypb@ustc.edu.cn 10 中国科学技术大学
ypb@ustc.edu.cn 10 中国科学技术大学