“This is the 26th day of my participation in the August More Text Challenge.

Follow me for more updates

Data structures and algorithms (I): time complexity and space complexity

Data structure and algorithm (two): stack

Data structures and algorithms (iii): queues

Data structures and algorithms (4): single linked lists

Data structures and algorithms (5): bidirectional linked lists

Data structures and algorithms (6): hash table

Data structures and algorithms (7): trees

Data structure and algorithm (8): sorting algorithm

Data structures and Algorithms (9): Classical algorithms interview questions

Data structures and algorithms (10): recursion

Data structures and Algorithms (xi): graphs

Graph traversal

Graph traversal means that all vertices in the graph are visited once and only once, starting from any vertex in the graph. Graph traversal is similar to tree traversal. Graph traversal is a basic operation of graph, and many other operations of graph are based on the traversal operation. According to different search strategies, graph traversal methods include depth first search method and breadth (width) first search method. Breadth-first search is a layer of traversal, similar to the tree level traversal; Depth-first search, in the vernacular, is a path to black, back up and down. For example, the breadth-first search order below is :1, 2, 3, 4, 5, 6, 7, 8; The depth-first search sequence is 1, 2, 4, 8, 6, 3, 7, and 5. Adjacency matrix or adjacency list can be used to store graphs. This paper will implement depth-first search and breadth-first search respectively for these two storage structures.

A) figure Graph

First, breadth first search

The breadth-first search of graph is the extension of tree traversal by level. The similar idea is adopted in Prim minimum spanning tree algorithm and Dijkstra single source shortest path algorithm. Its basic idea is: first access the initial point v0, and mark it as visited, then access all the unvisited adjacent points of V0 v1,v2… , vi, and all marked as visited, and then according to v1,v2… , the order of vi, all unvisited adjacent points of each vertex are marked as visited, and so on, until all vertices in the graph that have a path in common with the initial point v0 are visited.

Breadth-first search can be implemented by taking advantage of the first-in, first-out characteristics of queues. The specific steps are as follows:

1) Starting with vertex V, mark it as visited and push it into the queue; 2) At this time, the adjacent vertices of vertex S have not been accessed, so v is temporarily in an unexplored state; 3) Access all its neighboring vertices and push them into the queue, after which v’s state becomes explored, it is removed from the queue; The parent vertex of the team vertices is V; 4) Take the top point of the team and repeat the above operations with it as the starting point. Exploration stops when all vertices are explored, i.e. the queue is empty. According to the above analysis, the time complexity of breadth-first search is O(V+E), where V is the number of vertices and E is the number of edges.

1. Adjacency tables store breadth-first searches of graphs

B) Adjacency list storage diagram (child linked list representation)

The pseudo code for the non-recursive (while loop) breadth-first search is as follows:

void BFS(int s){ queue<int> q; q.push(s); // As long as there are elements in the queue, it keeps iterating until it finds the end. while(! Q.mpty ()){fetch the first queue; Visiting team leader; Eject team leader; [Fixed] All elements in the next tier below the first element join the team. }}Copy the code

Code implementation:

Int LocateVex(ALGraph &G, char v) {int I; for (i = 0; i < G.vexnum; i++) if (v == G.vertices[i].data) return i; }Copy the code
Void BFS(ALGraph &G, char v0) {int u,w,v; / / void BFS(ALGraph &G, char v0) {int u,w,v; ArcNode *p; printf("%c ", v0); V = LocateVex(G, v0); // Find the subscript v0 for visited[v] = 1; // vertex v0 is accessed q.ush (v0); // add vertex v0 to queue while (! q.empty()) { u = q.front(); V = LocateVex(G, u); v = LocateVex(G, u); // Get the corresponding subscript of vertex u q.op (); // block the vertex u from the queue. // Block the vertex u from the queue. p; p = p->nextarc) { w = p->adjvex; if (! Printf ("%c ", g.vertices [w].data); P visited[w] = 1; // the vertices are now called. // the vertices are now called. // join vertex p}}}}Copy the code

2. Breadth first search of adjacency matrix store graph

Void BFS(AMGraph &G,char v0) {int u, I,v,w; / / void BFS(AMGraph &G,char v0) {int u, I,v,w; v = LocateVex(G,v0); Printf ("%c ", v0); // Print v0 visited[v] = 1; // vertex v0 is accessed q.ush (v0); // join v0 while (! q.empty()) { u = q.front(); V = LocateVex(G, u); v = LocateVex(G, u); // Get the corresponding subscript of vertex u q.op (); For (I = 0; i < G.vexnum; i++) { w = G.vexs[i]; if (G.arcs[v][i] && ! Printf ("%c ", w); printf("%c ", w); printf("%c ", w); // Print vertex w q.push(w); // visit [I] = 1; // Vertex W has been accessed at}}}}Copy the code

Depth-first search

Depth-first search is an extension of sequential tree traversal. Its basic idea is: start from a vertex v0 of graph G, visit v0, then select an adjacent and unvisited vertex VI to visit v0, and then select an adjacent and unvisited vertex Vj to visit from vi, and continue in sequence. If all adjacent vertices of the currently visited vertices have been visited, go back to w, the last vertex in the visited vertices sequence with adjacent unvisited vertices, and proceed in the same way from W until all vertices in the graph have been visited. Depth-first search is a recursive process, and the code can be implemented recursively

Since graphs can be stored by adjacency matrix or adjacency list, depth-first search is implemented for graphs stored by these two structures

1. Store the adjacency list

① Non-recursive algorithm (while loop)

The pseudocode is as follows:

1. Access vertex VI; visited[vi] = 1; 2. W = the first adjacency of vertex vi; 3. While (w exists) 3.1 If (w is not accessed) The algorithm is recursively executed from vertex W; 3.2w = the next adjacent point of vertex v;Copy the code
void DFS(ALGraph &G, int v)
{
	int w;
	printf("%c ", G.vertices[v].data);
	visited[v] = 1;
	ArcNode *p = new ArcNode;
	p = G.vertices[v].firstarc;
	while (p)
	{
		w = p->adjvex;
		if (!visited[w]) DFS(G, w);
		p = p->nextarc;
	}
}
Copy the code

② Recursive algorithm

Boolean visited[MAXSIZE]; Void DFS(GraphAdjList G, int I) {EdgeNode *p; visited[i] = TRUE; Printf ("%c ",G->adjList[I].data); p = G->adjList[i].firstedge; //3. while (p) { if(! visited[p->adjvex]) DFS(G,p->adjvex); p = p->next; }}Copy the code

2. Adjacency matrix storage diagram

The pseudocode is as follows:

Visited [I] = true; visited[I] = true; 3. If (matrix[I][j]==1 &&! Visted [J]){enter the next recursive; }Copy the code
void DFSM(MGraph *G,int i) { int j; printf("%c/n",G->vexs[i]); // vi visited[I]=TRUE; for(j=0; j<G->n; J ++) if(G->matrix[I][j]==1 &&! visited[j]) DFSM(G,j); }Copy the code

Pay attention to my

If you think I write well, please click a like to pay attention to me, your support is my biggest motivation!