1
1
1
清华大学
清华大学
宋斌恒
宋斌恒
第七讲
第七讲
图的基本算法
图的基本算法
清华大学
清华大学
宋斌恒
宋斌恒
清华大学
清华大学
宋斌恒
宋斌恒
2
2
内容提要
内容提要
Representation of graphics
Breadth-first search
Depth-first search
Topological sort
Strongly connected components
清华大学
清华大学
宋斌恒
宋斌恒
3
3
图的应用背景
图的应用背景
可以利用图描述的经典问题有
Petri-Net
Work Flow
城市与连接城市的道路
区域与隔离区域间的分界线
人与人之间的认识关系
任何二元关系都可以用图来表示
基本算法的应用
许多与图有关的算法需要做一种搜索
清华大学
清华大学
宋斌恒
宋斌恒
4
4
Representation of graphs
Representation of graphs
Definition of a graph:
G = (V, E) where V is a set of vertices, E is
another set call Edges is a sub set of {(u,v): u
and v is element of V}
Concepts of graphs:
Dense graph: if |E| is close to |V|
2
.
Sparse graph: If it is not dense
清华大学
清华大学
宋斌恒
宋斌恒
5
5
1 2
5 4
3
2
1
2
2
4
5
5
4
5
1
/
/
3
3
2
/
/
4
/
01011
10110
01010
11101
10010
Figure 22.1 Two representations of an undirected graph.
(a) An undirected graph G having five vertices and seven edges.
(b) An adjacency-list representation of G.
(c) The adjacency-matrix representation of G.
清华大学
清华大学
宋斌恒
宋斌恒
6
6
1
2
5
4
3
2
5
/
6
2
/
4
/
5
/
/
4
/
000000
001000
000010
110000
010000
001010
6