
第七章图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)代表和·有向网、无向网:一带权的有向图和无向图完全图(completegraph):边e为n(n-1)/2有向完全图:弧e为n(n-1)2ypb@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)

(b)无向图G2(a)有向图 Gi108VoV.153020302010V4115(a)有向网G3(b)无向网G4中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 3 中国科学技术大学

稀疏图(sparsegraph):有向图enlogn子图(subgraph):-G-(VE),G=(V,E),如V’≤V且E≤E,则称G是G的子图度(degree)、出度(OutDegree)、入度(Indegree):称u邻接到v,或v邻接自u。邻接到某顶点的弧的数目称该顶点的入度ID(v);邻接自某顶点的弧的数目称该顶点的出度OD(u);某顶点的入度、出度之和为该顶点的度TD(v)路径和回路:一有向路径/无向路径,路径长度、回路或环连通图和连通分量:一连通图(无向),强连通图(有向),连通分量生成树、生成森林:连通图的成树是极小连通子图有向图的生成森林由若有向树组成,含有图中全部顶点和部分足以构成若干颗不相交有向树的狐,中国科学技术大学ypb@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 Graph(数据对象:V是具有相同特性数据元素的集合。数据关系:R=[lv,wEV且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)5中国科学技术大学ypb@ustc.edu.cn
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)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, visitO)13) BFSTraverse(G, V, visitO)1 ADT Graph6中国科学技术大学ypb@ustc.edu.cn
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

7.2图的存储图的数组(邻接矩阵))存储表示typedef enum(DG , DN , AG , AN) GraphKind ;typedef struct ArcCell(adj;VRType*info;InfoType↑ArcCell,AdjMatrix[MAX V NUMII MAX V NUMl ;typedef struct[VertexTypevexs[MAX V NUM]AdjMatrixarcs,intvexnum,arcnum;kind;GraphKind 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;

8200110888153088800005815108A2=00012010888000305888(b)G4的邻接矩阵(a)G,的邻接矩阵302010?8中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 8 中国科学技术大学

7.2.2图的邻接表存储表示typedef struct ArcNode:intadjvex;*nextarc;struct ArcNode*info;InfoType ArcNode ;typedef struct VNodedata,VertetType*firsrarc;ArcNode↓VNode,AdjList[MAX VERTEX NUM];typedefstruct!AdListvertices;intvexnum,arcnum,kind;GraphKind}ALGraph;9ypb@ustc.edu.cn中国科学技术大学
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图的邻接表存储表示

V0V.00V.420-VViV,A2-0V自2V2V22V当3V.V3宫3十-V4(a)G,的邻接表(b)G2的邻接表(c)G,的逆邻接表表结点头结点infoadjvexdatafirstarcnextarc10中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 10 中国科学技术大学