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.

---- 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.

无向图

前序根节点为1

每往下一次加1

到底后倒序 底部后序为1退到再次有分叉的地方 注意当节点相邻节点有未访问时 后序还未开始计算 到最后回到根节点时 没有访问过的边也要让两节点相连 不过以虚线相连

---- 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).

有向图

根据方向进行访问 其余与无向图相同

但是 当访问回根节点时 还没有访问完所有节点 此时挑选剩余节点中能往下走的起点开始 其先序为前面先序max加1 到底后（根据原有规则 先序一直加1）后序为根节点后序加1

方向为祖先指向子代的为forward edge

子代指向祖先的为back edge 直接祖先？直接看画出的序列图 通过实线直接或间接连接 就存在直接？祖先子代关系

其余的为cross edge

• Θ
**(**
*m*
**+**
*n*
**)**
**(**
**adjacency list**
**) Θ**
**(**
*n***
*2*
**)**
**(**
an adjacency matrix
**)**

**Applications of Depth-First Search**

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*].

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.

**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.

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.**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).

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.

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.

**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*.

无向图

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

有向图

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

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**

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*.)

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.

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

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

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