第七章图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>表从v到w的弧·有向图(digraph)、无向图(undigraph)、边：- (v,w)代表<v,w>和<w,v>·有向网、无向网：一带权的有向图和无向图完全图（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>表从v到w的弧 • 有向图(digraph) 、无向图(undigraph) 、边: – (v,w)代表<v,w>和<w,v> • 有向网、无向网： – 带权的有向图和无向图 • 完全图（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）：有向图e<nlogn稠密图（densegraph）：有向图e>nlogn子图（subgraph）：-G-(VE),G=(V,E),如V’≤V且E≤E,则称G是G的子图度(degree)、出度(OutDegree)、入度(Indegree):<u.v>称u邻接到v，或v邻接自u。邻接到某顶点的弧的数目称该顶点的入度ID(v）；邻接自某顶点的弧的数目称该顶点的出度OD(u）；某顶点的入度、出度之和为该顶点的度TD(v)路径和回路：一有向路径/无向路径，路径长度、回路或环连通图和连通分量：一连通图（无向），强连通图（有向），连通分量生成树、生成森林：连通图的成树是极小连通子图有向图的生成森林由若有向树组成，含有图中全部顶点和部分足以构成若干颗不相交有向树的狐，中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 4 中国科学技术大学 • 稀疏图（sparse graph）：有向图e<nlogn • 稠密图（dense graph）：有向图e>nlogn • 子图（subgraph）: – G=(V,E),G’=(V’,E’),如V’≦V且 E≦E’,则称G’是G的子图 • 度(degree)、出度(OutDegree)、入度(Indegree): – <u,v>称u邻接到v，或v邻接自u。邻接到某顶点的弧的数目称该顶点的入度 ID(v)；邻接自某顶点的弧的数目称该顶点的出度OD(u)；某顶点的入度、 出度之和为该顶点的度TD(v) • 路径和回路： – 有向路径/无向路径，路径长度、回路或环 • 连通图和连通分量： – 连通图(无向)，强连通图（有向），连通分量 • 生成树、生成森林： – 连通图的生成树是极小连通子图。 – 有向图的生成森林由若干有向树组成，含有图中全部顶点和部分足以构成 若干颗不相交有向树的狐
ADT Graph(数据对象：V是具有相同特性数据元素的集合。数据关系：R=[<v,w>lv,wEV且P(v,w)，其中<v,w>表示从v到w的狐，谓词P(v,w）表示狐<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,w∈V且P(v,w),其中<v,w>表示从v 到w的狐，谓词P(v,w)表示狐<v,w>的信息} 基本操作： 1) CreateGraph(&G, V, E) 2) DestroyGraph(&G) 3) LocateVex(G，u) 4) GetVex(G，v) 5) PutVex(&G，v，value)