Definition of graph traversal and depth first search and breadth first search (I)

Graph traversal

Definition

Traversal of a graph is a process of accessing each vertex in the graph only once starting from a vertex in the graph . The traversal algorithm of graph is the basis of algorithms such as topological sorting and critical path solving the connectivity problem of graph .

The traversal of a graph is different from that of a tree in that there is no loop in the tree, and the same vertex along the branch cannot be accessed many times . But in the diagram, there is a loop , So the same vertex may be accessed many times .

To avoid this , In the process of traversing the graph , The flag that can judge whether the vertex has been accessed must be set. Generally, an array is set  visited [0 ... n-1] The initial values are all ' false ’, Once the vertex is accessed  v  It will be visited [vi]  Set up ' really ’.

• Two ways of traversal : Depth-first search   Breadth first search

Depth-first search

• 
  
  Depth first search is similar to the first root traversal of the tree

The graph is stored in the form of adjacency table , Unlike other adjacency tables, there is a visited flag bit in the overhead point , Its initial value is “ false ”. The process of depth first search : Select any vertex in the graph as the starting vertex V0, visit V0 after , Successively V0 Start from the uncharted adjacency point of to conduct depth first search . Until with V0 All connected vertices are accessed . If , At this time, there are still vertices in the graph that have not been accessed , Then select another vertex from the remaining vertices as the starting vertex V0, Repeat the process , Until all vertices in the graph are accessed . As shown in the following figure, the traversal sequence is (v1,v2,v4,v8,v5,v3,v6,v7)

This is the graph to traverse ：

This is the adjacency table

• 
  
  Design and analysis of depth first search algorithm （ recursive ）

Boolean visited[MAX];( Access flag array ) 

Status(*VisitFunc)(int v);( The function variables )

Void DFSTraverse(Graph G, Status(*visit)(int v)) { ( Depth traversal )

 for (v = 0;v<G.vexnum;++v). visited[v] = FALSE;( Initial false value ) 

for (v = 0;v <G.VEXNUM; ++v)

if(!visited[v]) DFS(G,v);( Call the vertex that has not been accessed DFS)

}

Void DFS(Graph G,int v){( From v Starting from vertices, recursive depth first ) 

visited[v] =TRUE;

VisitFunc(v);( Access No. v vertices )

for(w =FirstAdjVex(G,V);W>=0;w =NextAdjVex(G,v,w))

 if(!visited[w])DFS(G,w);

} 

• 
  
  Algorithm flowchart （ recursive ）