Depth first find all simple paths from vertex u to vertex v in the graph

---

Preface

I have been reviewing the data structure , For the adjacency matrix, there is an algorithm in the book that outputs a simple path between two vertices , This sounds simple , Think about it , This is not the same as outputting the root node to r Is the node path the same , Maintain a stack , find r The pointer pops the stack empty .

Allied , about U and V Vertices are the same , Maintain a stack , Find... In the figure V The vertices , Directly empty the stack . This is easy for a simple path .

But one of the questions after class is output U To V All simple paths to , When it comes to tracing back my elm head, I have a headache , focused , Also maintain a stack ？ But how can we trace back to the last recursive node after bouncing empty ？

Keep thinking , The data structure of gengguohua's teacher gave me a little inspiration , He used a pre Array to record the route , When from a vertex vi Find its adjacent vertex vj When doing an interview , take pre[j] Set as i, So after exiting the search , According to pre Array from vertex v Trace to vertex u, So as to output this message from u To v Simple path of .

Have to say , Teacher gengguohua is a national famous teacher , It's really powerful , But I really can't think of such a clever method .

I learned from teacher gengguohua's Algorithm , According to my own understanding, I wrote a depth that I can understand, and first find the vertex U To the top V All the simple paths to .

---

Steps are as follows

1 For adjacency matrix

---

1.1 Create an adjacency matrix

// Find the vertex position function 
int LocateVertex(AdjMatrix* G, VertexData v) {
    
	int j, k;
	for (k = 0; k < G->vexnum; k++) {
    
		if (G->vertex[k] == v) {
    
			j = k;
			break;
		}
	}
	return j;
}

// Establish adjacency matrix representation of directed net graph 
void CreateAdjMatrix(AdjMatrix* G) {
    
	int i, j, k, weight;
	VertexData v1, v2;

	printf(" Enter the number of vertices and edges \n");
	scanf("%d,%d", &G->vexnum, &G->arcnum);
	// Initialization of side table 
	for (i = 0; i < G->vexnum; i++) {
    
		for (j = 0; j < G->vexnum; j++) {
    
			G->arcs[i][j].adj = ZHENGWUQIONG;// It's just infinite #define ZHENGWUQIONG 65535
		}
	}
	// Vertex table 
	for (i = 0; i < G->vexnum; i++) {
    
		G->vertex[i]='A' + i;
	}
	printf(" Input side table \n");
	for (k = 0; k < G->arcnum; k++) {
    
		scanf(" %c, %c,%d", &v1, &v2, &weight);
		i = LocateVertex(G, v1);
		j = LocateVertex(G, v2);
		G->arcs[i][j].adj = weight;
		// Add the following line to create an undirected graph .
		G->arcs[j][i].adj = G->arcs[i][j].adj;
	}
}

1.2 initialization path Array and find vertices U And vertex V The subscript

The code is as follows ：

LocateVertex function

int LocateVertex(AdjMatrix* G, VertexData v) {
    
	int j, k;
	for (k = 0; k < G->vexnum; k++) {
    
		if (G->vertex[k] == v) {
    
			j = k;
			break;
		}
	}
	return j;
}

initialization path Array and input vi,vj

int* path = (int*)malloc(sizeof(int) * G.vexnum);
	printf(" Enter the two nodes to query , Comma separated \n");
	char ci, cj;
	scanf(" %c, %c", &ci, &cj);
	int vi = LocateVertex(&G, ci);
	int vj = LocateVertex(&G, cj);
	for (int i = 0; i < MAX; i++) {
    
		visited[i] = 0;
	}
	FindPath(G, vi, vj, path, -1);
	free(path);

1.3 FindPath() function

The next step is to enter FindPath Function .

path Arrays are used to store paths , Think of Yu stack ,d Is the path length , For the initial -1, Equivalent to stack top pointer .

take vi Set as accessed ,d++ after , Put it in the path Array , If vi and vj The same description found v, Then we will path Array output , Every time you output d–, Indicates that you have exited , And will visited Array is set to not accessed , Convenient access to the next node , But because of recursion , If you return to the previous node , that path The array will also look like the previous node , This completes the backtracking , It's perfect .

however visited Arrays are global variables , Therefore, before entering the node every time, the current path The elements in the array are set to have been accessed , This avoids nodes from vi=0 Start searching and search back .

The code is as follows ：

void FindPath(AdjMatrix g, int vi, int vj, int* path, int d) {
    //d Subscript the element at the top of the stack. The initial subscript is -1;
	int i;
	++d;
	// hold vi Put it in path Array 
	path[d] = vi;
	// Set up vi For visited 
	visited[vi] = 1;
	// If you find vj
	if (vi == vj) {
    
		int len = d;
		// Bomb empty path Array 
		for (int j = 0; j <= len; j++) {
    
			printf("%c ", g.vertex[path[j]]);
			// Backstack 
			d--;
			// Do not set the root node as not accessed , It's easy to form a dead cycle .
			if (j != 0) {
    
				visited[path[j]] = 0;
			}
		}
		printf("\n");
		return;
	}
	for (i = 0; i < g.vexnum; i++) {
    
	// Before entering the node , To put path The elements in the array are set to have been accessed , Avoid the last output path An array of zero visited Circular access caused by array .
		for (int len = d; len >= 0; len--) {
    
			visited[path[len]] = 1;
		}
		if (!visited[i] && g.arcs[vi][i].adj != ZHENGWUQIONG) {
    
			FindPath(g, i, vj, path, d);
		}
	}
	// If you haven't found it after the loop is over, you can withdraw from the stack and set it to be unreachable . It's like walking down a dead end and exiting .
	if (i == g.vexnum) {
    
		visited[path[d]] = 0;
		d--;
	}
}

1.4 test result

The test results are as follows , I found a rather complicated picture .



Find the most complicated A,D

wuhu , It's perfect ！

---

2 For adjacency tables

---

2.1 Create adjacency list

The side table established by the tail interpolation method here .

// Find the vertex position function 
int LocateVertex(AdjList* G, VertexData v) {
    
	int j, k;
	for (k = 0; k < G->vexnum; k++) {
    
		if (G->vertexlist[k].data == v) {
    
			j = k;
			break;
		}
	}
	return j;
}
// Create adjacency table 
void CreateAdjList(AdjList* adjlist) {
    
	int i, j, k, weight;
	char vi, vj;
	printf(" Please enter the number of vertices and edges ：\n");
	scanf("%d,%d", &adjlist->vexnum, &adjlist->arcnum);
	for (i = 0; i < adjlist->vexnum; i++) {
    
		adjlist->vertexlist[i].data = 'A' + i;
		adjlist->vertexlist[i].firstarc = NULL;
	}
	printf(" Please enter the starting point of the arc , End point and weight ：\n");
	for (k = 0; k < adjlist->arcnum; k++) {
    
		scanf(" %c ,%c,%d", &vi, &vj, &weight);
		ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex = LocateVertex(adjlist, vj);
		ArcNode* tmp = adjlist->vertexlist[LocateVertex(adjlist, vi)].firstarc;
		if (tmp == NULL) {
    
			p->nextarc = adjlist->vertexlist[LocateVertex(adjlist, vi)].firstarc;
			adjlist->vertexlist[LocateVertex(adjlist, vi)].firstarc = p;
		}
		else {
    
			while (tmp->nextarc != NULL) {
    
				tmp = tmp->nextarc;
			}
			p->nextarc = tmp->nextarc;
			tmp->nextarc = p;
		}

		// An undirected graph has 
		ArcNode* s = (ArcNode*)malloc(sizeof(ArcNode));
		s->adjvex = LocateVertex(adjlist, vi);
		ArcNode* tmp2 = adjlist->vertexlist[LocateVertex(adjlist, vj)].firstarc;
		if (tmp2 == NULL) {
    
			s->nextarc = adjlist->vertexlist[LocateVertex(adjlist, vj)].firstarc;
			adjlist->vertexlist[LocateVertex(adjlist, vj)].firstarc = s;
		}
		else {
    
			while (tmp2->nextarc != NULL) {
    
				tmp2 = tmp2->nextarc;
			}
			s->nextarc = tmp2->nextarc;
			tmp2->nextarc = s;
		}
	}
}

2.2 initialization path Array and find vertices U And vertex V The subscript

Almost and 1.2 As like as two peas

int* path = (int*)malloc(sizeof(int) * G.vexnum);
	printf(" Enter the two nodes to query , Comma separated \n");
	char ci, cj;
	scanf(" %c, %c", &ci, &cj);
	int vi = LocateVertex(&G, ci);
	int vj = LocateVertex(&G, cj);
	for (int i = 0; i < MAX; i++) {
    
		visited[i] = 0;
	}
	FindPath(G, vi, vj, path, -1);
	free(path);

2.3 FindPath() function

And the method of adjacency matrix is also similar

// Depth first find the vertex u And vertex v Simple path of 
void FindPath(AdjList g, int vi, int vj, int* path, int d) {
    
	visited[vi] = 1;
	d++;
	path[d] = vi;
	if (vi == vj) {
    
		int i;
		for (i = 0; i <= d; i++) {
    
			printf("%c ", g.vertexlist[path[i]].data);
			if (i != 0) {
    
				visited[path[i]] = 0;
			}
		}
		printf("\n");
		return;
	}
	ArcNode* p = g.vertexlist[vi].firstarc;
	while (p != NULL) {
    
		for (int len = d; len >= 0; len--) {
    
			visited[path[len]] = 1;
		}
		if (!visited[p->adjvex]) {
    
			FindPath(g, p->adjvex, vj, path, d);
		}
		p = p->nextarc;
	}
	if (p == NULL) {
    
		visited[path[d]] = 0;
		d--;
	}
}

2.4 test result

Or this picture


There must be no problem .

perfect！

---

summary

Although this algorithm is a little stupid , But my elm head can understand , I feel very successful ！