中国科学技术大学：《数据结构及其算法》课程电子教案（PPT课件讲稿）第七章 图

③第七章图 7.1图的基本概念 7.2图的存储 7.3图的遍历 74最小生成树 7.5拓扑排序 7.6关键路径 77最短路径 pb(@ustc.edu.cn 中国科学技术大学

ypb@ustc.edu.cn 1 中国科学技术大学 第七章 图 7.1图的基本概念 7.2图的存储 7.3图的遍历 7.4最小生成树 7.5拓扑排序 7.6关键路径 7.7最短路径

71图的基本概念 图 graph 个顶点( vertex)的有穷集V(G)和一个弧(arc)的 集合E(G)组成。记做:G=(V,E)。V是数据结构中 的数据元素,E是集合上的关系 弧(ar)、弧头(终点)、弧尾(起点): 表从v到w的弧 有向图 digraph)、无向图 undigraph)、边: (v,w)代表和 有向网、无向网 带权的有向图和无向图 全图( complete graph):边e为n(n-1)2 有向完全图:弧e为.n(n-1) pb(@ustc.edu.cn 中国科学技术大学

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)

Q (a)有向图G1 (b)无向图G2 20 30 30 15 (a)有向网G3 pb@ustc.edu.cn (b)无向网G、学技术大学

ypb@ustc.edu.cn 3 中国科学技术大学

稀疏图( sparse graph):有向图 e nlogn 子图( subgraph): G=(VE)G2=(V,E),如V≤V且EE,则称G是G的子图 度( degree)、出度( OutDegree)、入度( Indegree) 称u邻接到v,或v邻接自u。邻接到某顶点的弧的数目称该顶 点的入度ID(v);邻接自某顶点的弧的数目称该顶点的出度ODu) 某顶点的入度、出度之和为该顶点的度TD(v) 路径和回路: 有向路径/无向路径,路径长度、回路或环 ·连通图和连通分量: 连通图(无向),强连通图(有向),连通分量 ·生成树和生成森林(所有顶点/连通图/无回路) pb(@ustc.edu.cn 中国科学技术大学

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描述 ADT Graph 数据对象V: V是同类型数据元素的非空有限集,称为顶点集 数据关系R: R={vi,vj>lvi,vj∈V且Path(vi,vj), 表示从vi到vj的弧,谓词Path(vi,vj)定义了弧 vi,vj>的意义和信息} 基本操作 1)Create Graph(&G,v,e) 2) Destroy Graph(&g) pb(@ustc.edu.cn 中国科学技术大学

ypb@ustc.edu.cn 5 中国科学技术大学 图的ADT描述 ADT Graph{ 数据对象V： V是同类型数据元素的非空有限集，称为顶点集。 数据关系R： R={|vi,vj∈V且Path(vi,vj)， 表示从vi到vj的弧，谓词Path(vi,vj)定义了弧 的意义和信息} 基本操作: 1) CreateGraph(&G, V, E) 2) DestroyGraph(&G)

3)Locate Vex(G, u) 4) Get Vex(G, v) 5)Put Vex(&G, v, value 6) FarstAdⅤex(G,v) 7 NextAdjVex(G, v, w) 8) Vex(&G, v) 9)Delete Vex(&G, v) 10)InsertArc(&G, v, w) 11) DeleteArc(&G, v, w) 12)DFSTraverse(G, v, visito 13)BFSTraverse(G, V, visito) 3 end AT Graph pb(@ustc.edu.cn 中国科学技术大学

ypb@ustc.edu.cn 6 中国科学技术大学 3) LocateVex(G，u) 4) GetVex(G，v) 5) PutVex(&G，v，value) 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()) } end ADT Graph

③72图的存储 ·图的数组(邻接矩阵)存储表示 typedef enum DG, dN, AG, AN GraphKind typedef int Arc Type; typedef struct( Vertextype veXs MAX V NUMI ArcType arcs MAX V NUMJL MAX V NUM] int Ⅴ enum. archon GraphKind kind )MGraph pb(@ustc.edu.cn 中国科学技术大学

ypb@ustc.edu.cn 7 中国科学技术大学 7.2图的存储 • 图的数组（邻接矩阵）存储表示 typedef enum{DG，DN，AG，AN} GraphKind； typedef int ArcType； typedef struct{ VertexType vexs[MAX_V_NUM]; ArcType arcs [MAX_V_NUM][ MAX_V_NUM]; int vexnum,arcnum; GraphKind kind; }MGraph;

01 8∞20 15 0000 8 30 A 5 0001 20∞10∞ 1000 305 (a)G1的邻接矩阵 (b)G4的邻接矩阵 pb(@ustc.edu.cn 8 中国科学技术大学

ypb@ustc.edu.cn 8 中国科学技术大学

③B部分操作的实现 void Create Graph(MGraph &g) int Locate Vex(MGraph G, vertexType v) void InsertArc(MGraph &G, vertexType vi VertexType int FirstAdjvex(mgraph g, int v) int NextAdj vex(MGraph G, int v, int w) pb(@ustc.edu.cn 中国科学技术大学

ypb@ustc.edu.cn 9 中国科学技术大学 部分操作的实现 • void CreateGraph(MGraph &G) • int LocateVex(MGraph G, VertexType v) • void InsertArc(MGraph &G, VertexType vi, VertexType vj) • int FirstAdjVex(MGraph G, int v) • int NextAdjVex(MGraph G, int v, int w)

void Create Graph(MGraph &Gr ∥从人键盘输入图顶点和边集,创建用邻接矩阵表示的图G cin>>G. vexnum>>G arcum>>G kind for(i=0;i G vex];∥输入顶点集 for(i=0; iv>>v;∥输入弧 f( G kind=2) G. arcs]=1;∥无向图,置对称弧 }∥ Create Graph

void CreateGraph(MGraph &G){ //从键盘输入图顶点和边集，创建用邻接矩阵表示的图G cin>>G.vexnum>>G.arcnum>>G.kind; for(i=0;i>G.vexs[i]; //输入顶点集 for(i=0;i>vi>>vj; //输入弧 i=LocateVex(G,vi); //求顶点vi的存储位置下标 j=LocateVex(G,vj); //求顶点vj的存储位置下标 G.arcs[i][j]=1; //置弧 if(G.kind==2) G.arcs[j][i]=1; //无向图,置对称弧 } } //CreateGraph