内容提要 第七讲图的基本算法 CRepresentation of graphics E Breadth-first search EDepth-first search 2. Strongly connected components 图的应用背景 Representation of graphs z可以利用图描述的经典问题有 DEfinition of a graph Petri-Net NG=(, E) where V is a set of vertices, E is WOrk Flow another set call Edges is a sub set of ((u, v):u y城市与连接城市的道路 and v is element of VI 隔离区域间的分界线 2. Concepts of graphs 人与人之间的认识关系 DEnse graph: if El is close to V2. 系都可以用图来表示 sParse graph: If it is not dense 基本算法的应用 e。 gure 22.1 Two representations of an undirected graph on of G1 清华大学 宋斌恒 1 第七讲 图的基本算法 清华大学 宋斌恒 清华大学 宋斌恒 2 内容提要 Representation of graphics Breadth-first search Depth-first search Topological sort Strongly connected components 清华大学 宋斌恒 3 图的应用背景 可以利用图描述的经典问题有 Petri－Net Work Flow 城市与连接城市的道路 区域与隔离区域间的分界线 人与人之间的认识关系 任何二元关系都可以用图来表示 基本算法的应用 许多与图有关的算法需要做一种搜索 清华大学 宋斌恒 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 1 2 5 4 3 2 1 2 2 4 5 5 4 5 1 / / 3 3 2 / / 4 / 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 1 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 1 2 5 4 3 2 5 / 6 2 / 4 / 5 / / 4 / 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 1 0 0 6