Graph Traversal

admin2024-05-15  0

Depth-First Search

Idea

         Let G = (V,E) be a directed or undirected graph. A depth-first search traversal of G works as follows. First, all vertices are marked unvisited. Next, a starting vertex is selected, say v V , and marked visited. Let w be any vertex that is adjacent to v. We mark w as visited and advance to another vertex, say x, that is adjacent to w and is marked unvisited. Again, we mark x as visited and advance to another vertex that is adjacent to x and is marked unvisited. This process of selecting an unvisited vertex adjacent to the current vertex  continues as deep as possible until we find a vertex y whose adjacent vertices have all been marked visited. At this point, we back up to the most recently visited vertex, say z, and visit an unvisited vertex that is adjacent to z, if any. Continuing this way, we finally return back to the starting vertex v. This method of traversal has been given the name depthfirst search, as it continues the search in the forward (deeper) direction.

Graph Traversal,第1张

Algorithm 8.1 DFS
  The case of undirected graphs

---- Tree edges

     Edges in the depth-first search tree. An edge (v,w) is a tree edge if w was first visited when exploring the edge (v,w).

---- Back edges

     All other edges

---- Example 8.1

Example 8.1 Figure 8.1(b) illustrates the action of depth-first search traversal on the undirected graph shown in Fig. 8.1(a). Vertex a has been selected as the start vertex. The depth-first search tree is shown in Fig. 8.1(b) with solid lines. Dotted lines represent back edges. Each vertex in the depth-first search tree is labeled with two numbers: predfn and postdfn. Note that since vertex e has postdfn = 1, it is the first vertex whose depth-first search is complete. Note also that since the graph is connected, the start vertex is labeled with predfn = 1 and postdfn = 10, the number of vertices in the graph.

Graph Traversal,第2张无向图
前序根节点为1
每往下一次加1
到底后倒序 底部后序为1退到再次有分叉的地方 注意当节点相邻节点有未访问时 后序还未开始计算 到最后回到根节点时 没有访问过的边也要让两节点相连 不过以虚线相连

Algorithm 8.1 DFS
  The case of directed graphs

---- Tree edges, Back edges, Forward edges, Cross edges

  Tree edges: edges in the depth-first search tree. An edge (v,w) is a tree edge if                     w was first visited when exploring the edge (v,w).

  Back edges: edges of the form (v,w) such that w is an ancestor of v in the depth-first          search tree (constructed so far) and vertex w was marked visited when (v,w)          was explored.

  Forward edges: edges of the form (v,w) such that w is a descendant of v in the depth-first   search tree (constructed so far) and vertex w was marked visited when   (v,w) was explored.

---- Cross edges:  All other edges

---- Example 8.2

Example 8.2 Figure 8.2(b) illustrates the action of depth-first search traversal on the directed graph shown in Fig. 8.2(a). The other result of the depth-first search traversal is shown in Fig. 8.2(c).

Graph Traversal,第3张

Graph Traversal,第4张有向图
根据方向进行访问 其余与无向图相同
但是 当访问回根节点时 还没有访问完所有节点 此时挑选剩余节点中能往下走的起点开始 其先序为前面先序max加1 到底后(根据原有规则 先序一直加1)后序为根节点后序加1
方向为祖先指向子代的为forward edge
子代指向祖先的为back edge 直接祖先?直接看画出的序列图 通过实线直接或间接连接 就存在直接?祖先子代关系
其余的为cross edge 

Time complexity of depth-first search
• Θ ( m + n )  ( adjacency list )   Θ ( n** 2 )  ( an adjacency matrix )

Applications of Depth-First Search 

Finding articulation points in a graph

       A vertex v in an undirected graph G with more than two vertices is called an articulation point if there exist two vertices u and w different from v such that any path between u and w must pass through v. Thus, if G is connected, the removal of v and its incident edges will result in a disconnected subgraph of G. A graph is called biconnected if it is connected and has no articulation points. To find the set of articulation points, we perform a depth-first search traversal on G. During the traversal, we maintain two labels with each vertex v ∈ V : α[v] and β[v]. α[v] is simply predfn in the depth-first search algorithm, which is incremented at each call to the depth-first search procedure. β[v] is initialized to α[v], but may change later on during the traversal. For each vertex v visited, we let β[v] be the minimum of the following:

α[v] = predfn.

  • α[u]  for each vertex u such that (v, u) is a back edge.

  • β[w] for each edge (v,w) in the depth-first search tree.

  i.e.

    b[v]=min{a[v], min{b[w]|w is  a son of v},

                                      min{a[u]|(v,u) is a back edge}  } ;

n The articulation points are determined as follows:

  •The root is an articulation point if and only if it has two or more children      in the depth-first search tree.

  • A vertex v other than the root is an articulation point if and only if v has a       child w with β[w] ≥ α[v].

Graph Traversal,第5张Graph Traversal,第6张First, the algorithm performs the necessary initializations. In particular, count is the number of articulation points, and rootdegree is the degree of the root of the depth-first search tree. This is needed to decide later whether the root is an articulation point as mentioned above. Next the depth-first search commences starting at the root. For each vertex v visited, α[v] and β[v] are initialized to predfn. When the search backs up from some vertex w to v, two actions take place. First, β[v] is set to β[w] if β[w] is found to be smaller then β[v]. Second, if β[w] ≥ α[v], then this is an indication that v is an articulation point.

This is because any path from w to an ancestor of v must pass through v. This is illustrated in Fig. 8.4 in which any path from the subtree rooted at w to u must include v, and hence v is an articulation point. The subtree rooted at w contains one or more connected components. In this figure, the root u is an articulation point since its degree is greater than 1.

Graph Traversal,第7张Example 8.3 We illustrate the action of Algorithm ARTICPOINTS by finding the articulation points of the graph shown in Fig. 8.1(a). See Fig. 8.5. Each vertex v in the depth-first search tree is labeled with α[v] and β[v]. So vertices b, c, g and h are articulation points.Graph Traversal,第8张

Strongly connected components

       Given a directed graph G = (V,E), a strongly connected component in G is a maximal set of vertices in which there is a path between each pair of vertices. Algorithm STRONGCONNECTCOMP uses depth-first search in order to identify all the strongly connected components in a directed graph.Graph Traversal,第9张Example 8.4  Consider the directed graph G shown in Fig. 8.2(a). Applying depth-first search on this directed graph results in the forest shown in Fig. 8.2(b).  Also shown in the figure is the postordering of the vertices, which is e, f, b, a, d, c. If we reverse the direction of the edges in G, we obtain G, which is shown in Fig. 8.6(a).

Graph Traversal,第10张Graph Traversal,第11张Starting from vertex c in G, a depth-first search traversal yields the tree consisting of vertex c only. Similarly, applying depth-first search on the remaining vertices starting at vertex d results in the tree consisting of only vertex d. Finally, applying depth-first search on the remaining vertices starting at vertex a yields the tree whose vertices are a, b, e, and f. The resulting forest is shown in Fig. 8.6(b). Each tree in the forest corresponds to a strongly connected component. Thus, G contains three strongly connected components.

Breadth-First Search

Idea

         Unlike depth-first search, in breadth-first search when we visit a vertex v, we next visit all vertices adjacent to v. The resulting tree is called a breadthfirst search tree. This method of traversal can be implemented by a queue to store unexamined vertices. Algorithm BFS for breadth-first search can be applied to directed and undirected graphs. Initially, all vertices are marked unvisited. The counter bfn, which is initialized to zero, represents the order in which the vertices are removed from the queue. In the case of undirected graphs, an edge is either a tree edge or a cross edge. If the graph is directed, an edge is either a tree edge, a back edge, or a cross edge; there are no forward edges.

Graph Traversal,第12张Graph Traversal,第13张Example 8.5 Figure 8.7 illustrates the action of breadth-first search traversal when applied on the graph shown in Fig. 8.1(a) starting from vertex a.Graph Traversal,第14张Graph Traversal,第15张

无向图

从根节点开始,访问相邻的边的节点,标记为遍历,根据这些节点继续往下访问未被标记的相邻节点,注意最后要把为经过遍历的边两端节点以虚线相连,遍历顺序从左到右,从上到下依次增加

有向图

从根节点开始,按照箭头方向访问相邻的边的节点,标记为遍历,根据这些节点继续往下访问未被标记的相邻节点,注意最后要把为经过遍历的边两端节点以虚线相连,遍历顺序从左到右,从上到下依次增加。最后如果有节点未访问,如同DFS一样将其重画一条树,遍历顺序从第一条树的最后开始加1 没有forward edge因为BFS逐层遍历 别的边如DFS一样标注

Time complexity

        The time complexity of breadth-first search when applied to a graph (directed or undirected) with n vertices and m edges is the same as that of depth-first search, i.e., Θ(n + m). If the graph is connected or m ≥ n, then the time complexity is simply Θ(m).

Applications of Breadth-First Search

Problem

        Let G = (V,E) be a connected undirected graph and s a vertex in V. Find the distance from s to any other vertex. (where the distance from s to a vertex v is defined to be the least number of edges in any path from s to v.)

 Solution

       This can easily be done by labeling each vertex with its distance prior to pushing it into the queue. Thus, the start vertex will be labeled 0, its adjacent vertices with 1, and so on. Clearly, the label of each vertex is its shortest distance from the start vertex. For instance, in Fig. 8.7, vertex a will be labeled 0, vertices b and g will be labeled 1, vertices c, f, and h will be labeled 2, and finally vertices d, e, i, and j will be labeled 3.

注意进行BFS和DFS遍历的时候寻找分叉时从后往前走

Graph Traversal,第16张

如该图进行DFS时。D节点应该在F后面连接即F是D的父节点,而非在B后面连接

即前面讲解“DFS中底部后序为1退到再次有分叉的地方”

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!