内容提要 第七讲图的基本算法 Representation of graphics Breadth-first search 清华大学 Depth-first search 宋斌恒 Topological sort Strongly ponents 清华大学宋斌恒 1 清华大学宋斌恒 2 图的应用背景 Representation of graphs 可以利用图描述的经典问题有 Definition of a graph: G = (V, E) where V is a set of vertices, E is Work Flow 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 基本算法的应用 许多与图有关的算法需要做一种搜索 清华大学宋斌恒 3 清华大学宋斌恒 4 2 4 / 1 2 2 5 / 2 3 0 1 0 0 1 1 0 1 0 1 0 0 1 5 3 4 / 5 / 1 0 1 1 1 0 0 0 0 1 0 6 5 3 2 4 / 0 1 0 1 0 / 0 0 0 0 1 1 2 5 3 / 0 1 1 0 1 2 / 0 1 0 0 0 0 1 1 0 1 0 5 4 4 1 2 / 5 4 6 4 / 0 0 0 1 0 0 / 0 0 0 0 0 0 Figure 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. 清华大学宋斌恒 5 清华大学宋斌恒 6 1 Data structure of Adjacency-list Adjacency-list representation representation Let G be a graph, for any u ∈ V, we A set of vertex objects denote Adj[u] = { v: (u,v) ∈ E}, call the list Vertex object contains one vertex u, and a of all adjacency vertices of u. set of vertices Adj[u], which contains all its In general element in Adj[u] is unordered adjacency vertices of u. In an undirected graph ? Using what data structure to represent a Sum(Adj[u], for all u ∈ V) = 2 |E| set for the vertex objects But in a directed graph ? Using what data structure to represent a Sum(Adj[u], for all u ∈ V) = 1 |E| set for Adj[u] 清华大学宋斌恒 7 清华大学宋斌恒 8 Adjacency-list representation for Weighted Graph Weighted Graphics We can assign value to the edges of a We reconstruct the set Adj[u] as graph, then we call such a graph is a Adj[u]={(v,r): v ∈ V, r ∈ R} where R is the weighted graph. space of real number or generally any object Classi
