第六次课堂

图的定义

图是由顶点的有穷非空集合和顶点之间边的集合组成&＃xff0c;通常表示为&＃xff1a;

G&＃61;(V&＃xff0c;E) (Graph
Vertex Edge)

其中&＃xff1a;G表示一个图&＃xff0c;V是图G中顶点的集合&＃xff0c;E是图G中顶点之间边的集合。

在线性表中&＃xff0c;元素个数可以为零&＃xff0c;称为空表&＃xff1b;在树中&＃xff0c;结点个数可以为零&＃xff0c;称为空树&＃xff1b;在图中&＃xff0c;顶点个数不能为零&＃xff0c;但可以没有边。

若顶点vi和vj之间的边没有方向&＃xff0c;则称这条边为无向边&＃xff0c;表示为(vi,vj)。如果图的任意两个顶点之间的边都是无向边&＃xff0c;则称该图为无向图。

若从顶点vi到vj的边有方向&＃xff0c;则称这条边为有向边&＃xff0c;表示为。

如果图的任意两个顶点之间的边都是有向边&＃xff0c;则称该图为有向图。

图的基本术语

简单图&＃xff1a;在图中&＃xff0c;若不存在顶点到其自身的边&＃xff0c;且同一条边不重复出现。

图的基本术语

无向完全图&＃xff1a;在无向图中&＃xff0c;如果任意两个顶点之间都存在边&＃xff0c;则称该图为无向完全图。

有向完全图&＃xff1a;在有向图中&＃xff0c;如果任意两个顶点之间都存在方向相反的两条弧&＃xff0c;则称该图为有向完全图。

权&＃xff1a;是指对边赋予的有意义的数值量。

网&＃xff1a;边上带权的图&＃xff0c;也称网图。

图的基本术语

路径&＃xff1a;在无向图G&＃61;(V, E)中&＃xff0c;从顶点vp到顶点vq之间的路径是一个顶点序列(vp&＃61;vi0,vi1,vi2, …, vim&＃61;vq)&＃xff0c;其中&＃xff0c; (vij-1,vij)∈E&＃xff08;1≤j≤m&＃xff09;。若G是有向图&＃xff0c;则路径也是有方向的&＃xff0c;顶点序列满足∈E。

V1 到V4的路径&＃xff1a;
V1 V4

V1 V2 V3 V4

V1 V2 V5V3 V4

™一般情况下&＃xff0c;图中的路径不惟一

非带权图——路径上边的个数路径长度&＃xff1a;带权图——路径上各边的权之和

1. 深度优先遍历 (depth-first traverse)
   
   深度优先遍历&＃xff1a;V1⇒ V2 ⇒V4⇒ V8 ⇒V5 ⇒V6⇒V3 ⇒V7
   深度优先遍历&＃xff1a;V1⇒ V2 ⇒V4 ⇒ V8 ⇒V5 ⇒V6 ⇒V3 ⇒V7

广度优先遍历 (breadth-first traverse) 基本思想&＃xff1a;

⑴访问顶点v&＃xff1b;

⑵依次访问v的各个未被访问的邻接点v1, v2, …, vk&＃xff1b;

⑶ 分别从v1&＃xff0c;v2&＃xff0c;…&＃xff0c;vk出发依次访问它们未被访问的邻接点&＃xff0c;并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v
有路径相通的顶点都被访问到。

广度优先遍历&＃xff1a;V1⇒ V2 ⇒V3 ⇒ V4⇒V5 ⇒V6 ⇒V7⇒V8
广度优先遍历&＃xff1a;V1⇒ V2 ⇒V3 ⇒ V4 ⇒V5 ⇒V6 ⇒V7 ⇒V8