This is the 23rd day of my participation in the August More Text Challenge.More challenges in August

Graph traversal

1. Breadth-first traversal (BFS)

The basic idea is to start at 𝑉0, visit 𝑉0, then visit adjacent unvisited vertices at 𝑉0, and continue to visit adjacent unvisited vertices from these vertices, and so on, until all vertices are accessed.

💻 breadth-first traversal (BFS) code

bool visited[Max_Vex];             // Access the tag array
void BFSTraverse(Graph G){
for(i=0; i<G.vexnum; ++i) visited[i]=false;        // Initializes the tag array
InitQueue(Q); 
for(v=0; v<G.vexnum; ++v)if(! visited[v])// If v is not accessed, start breadth-first traversal from v
BFS(G,v);
}
void BFS(Graph G,int v){
visit(v); visited[v]=true; Enqueue(Q,v); // Access nodes and enqueue them
while(! isEmpty(Q)){ DeQueue(Q,v);for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w))if(! visited[w]){ visit(w); visited[w]=true; EnQueue(Q,w)
}
}
}
Copy the code

💻 Performance analysis

  • When figure using adjacency table stores, each vertex must search a once (or team), the corresponding operation time complexity is O (| V |), in the search to a vertex need access to each adjacent to this edge, this operation need to traverse the adjacency list all side table in the node, So the time complexity is O (| E |), so the total time complexity is O (+ | | V | E |)
  • When using adjacency matrix storage, search for each vertex adjacency point need to traverse a line, the operation for a corresponding time complexity is O (| | V), and all vertices need to perform a search, so the total time complexity is O (| 𝑉 | ^ 2)
  • Need to introduce queue space aspect, all vertices are team, when the worst space complexity is O (| V |)

💻 breadth-first spanning tree

In the process of breadth-first traversal, we can get a traversal tree, which is called breadth-first spanning tree

Note:

  • If the graph is unconnected, a breadth-first forest is generated
  • The adjacency matrix representation of the graph is unique, so is the breadth-first spanning tree

2. Depth-first Traversal (DFS)

Basic idea: Start from a vertex of the graph 𝑉0, visit 𝑉0, then visit the unvisited vertex 𝑉1 adjacent to 𝑉0, and continue to visit the unvisited vertex 𝑉2 adjacent to 𝑉0, and so on. If no further access is possible, roll back the last accessed vertex successively. Each time you go back to check if there are any unvisited adjacent vertices at the current vertex, and if so, check until all vertices are accessed.

bool visited[Max_Vex];             // Access the tag array
void DFSTraverse(Graph G){
for(i=0; i<G.vexnum; ++i) visited[i]=false;        // Initializes the tag array
for(v=0; v<G.vexnum; ++v)if(! visited[v])// If v is not accessed, start depth-first traversal from v
DFS(G,v);
}
void DFS(Graph G,int v){
visit(v); visited[v]=true;   // Access the node and change the tag
for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w))if(!visited[w]){ 
DFS(G,w);
}
}
Copy the code

💻 Performance analysis

  • When figure using adjacency table stores, each vertex must search a once (or stack), the corresponding operation time complexity is O (| V |), in the search to a vertex need access to each adjacent to this edge, this operation need to traverse the adjacency list all side table in the node, So the time complexity is O (| E |), so the total time complexity is O (+ | | V | E |)
  • When using adjacency matrix storage, search for each vertex adjacency point need to traverse a line, the operation for a corresponding time complexity is O (| | V), and all vertices need to perform a search, so the total time complexity is O (| 𝑉 | ^ 2)
  • Work need to introduce recursive stack space, but the most bad all vertices into the stack and space complexity is O (| V |)

Depth-first spanning tree

In the depth-first traversal process, we can obtain a traversal tree, which is called depth-first spanning tree

Note:

  • If the graph is unconnected, a depth-first generation forest is generated
  • The adjacency matrix representation of the graph is unique, so is the depth-first spanning tree