文档介绍：第七章图
图的定义
图的存储表示
图的遍历
第七章 图
最小生成树
最短路径问题
拓扑排序
第七章 图
比较
在线性表中,一个元素只能和其直接前驱或直接后继相关;
在树中,一个结点可以和其下一层的多个孩子结点相关,以及上一层的双亲结点相关,但不能和其他的任何结点直接相关;
图(Graph)是一种较线性结构和树更为复杂的数据结构。而对于图来说,图中任意两个结点之间都可以直接相关,因此图形结构非常复杂
图是由一个顶点集 V 和一个弧集 E构成的数据结构。
Graph = (V, E )
顶点:图中的数据元素。设它的集合用V(Vertex)表示。
图的结构定义:
图的结构定义:
弧:设两个顶点之间的关系的集合用E(edge) 来表示,且v1,v2V,若<v1,v2> E,则<v1,v2>表示从v1 到v2的一条弧(Arc)。且称v1为弧尾(Tail)(始点、尾顶点) ,v2为弧头(Head)(终点、头顶点) ,此时的图称为有向图(Digraph)。
无向图:若<v1,v2> E必能推导出<v2,v1> E,即E是对称的,则用无序对(v1,v2)代替有序对,表示v1和v2之间的一条边(Edge)。此时的图称为无向图(Undigraph)。
E
A
C
B
D
例如:
G1 = (V1, E)
其中
V1={A, B, C, D, E}
V1E={<A,B>, <A,E>,
<B,C>, <C,D>, <D,B>,
<D,A>, <E,C> }
名词和术语--有向图
由于“弧”是有方向的,因此称由顶点集和弧集构成的图为有向图。
B
C
A
F
E
D
例如: G2=(V2,E)
V2={A, B, C, D, E, F}
V2E={(A, B), (A, E),
(B, E), (C, D), (D, F),
(B, F), (C, F) }
名词和术语--无向图
由顶点集和边集构成的图称作无向图。
假设图中有 n 个顶点,e 条边,则
含有 e=n(n-1)/2 条边的无向图称作完全图;
含有 e=n(n-1) 条弧的有向图称作有向完全图;
设图G=(V,{VE}) 和图 G=(V,{VE}),
且 VV, VEVE,
则称 G为 G 的子图。
A
B
E
C
F
15
9
7
21
11
3
2
弧或边带权的图分别称作有向网或无向网。
A
E
F
B
B
C