深度优先遍历(DFS)从某个顶点出发,访问此顶点,然后从v的未被访问的邻接点触发深度优先便利图,直至所有和v有路径相通的顶点都被访问到。
如上面的示例所示,DFS算法首先从S到A到D到G到E到B,然后到F,最后到C,它采用以下规则。
链接:https://www.learnfk.comhttps://www.learnfk.com/data-structures-algorithms/depth-first-traversal.html
来源:LearnFk无涯教程网
规则1 - 访问相邻的未访问顶点,将其标签为已访问,将其推入堆栈。
规则2 - 如果未找到相邻的顶点,请从堆栈中弹出一个顶点。 (它将弹出堆栈中没有相邻顶点的所有顶点。)
规则3 - 重复规则1和规则2,直到堆栈为空。
步骤 | 遍历 | 说明 |
---|---|---|
1 | 初始化堆栈。 | |
2 | 将 S 标签为已访问,并将其放入堆栈。探索 S 中所有未访问的相邻节点。我们有三个节点,我们可以选择其中任何一个。对于此示例,我们将按字母顺序选择节点。 | |
3 | 将 A 标签为已访问并将其放入堆栈。探索A中所有未访问的相邻节点。 S 和 D 都与 A 相邻,但是我们只关注未访问的节点。 | |
4 | 访问 D 并将其标签为已访问并放入堆栈。在这里,我们有 B 和 C 节点,它们与 D 相邻,并且都未访问。但是,我们将再次按字母顺序选择。 | |
5 | 我们选择 B ,将其标签为已访问并放入堆栈。在这里 B 没有任何未访问的相邻节点。因此,我们从堆栈中弹出 B 。 | |
6 | 我们检查堆栈顶部是否返回上一个节点,并检查它是否有未访问的节点。在这里,我们发现 D 在堆栈的顶部。 | |
7 | 现在只有未访问的相邻节点来自 D 是 C 。因此,我们访问 C ,将其标签为已访问并将其放入堆栈。 |
由于 C 没有任何未访问的相邻节点,因此我们不断弹出堆栈,直到找到一个具有未访问的相邻节点的节点为止。在这种情况下,没有任何东西,我们一直弹出直到堆栈为空。
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX 5 struct Vertex { char label; bool visited; }; //stack variables int stack[MAX]; int top = -1; //graph variables //array of vertices struct Vertex* lstVertices[MAX]; //adjacency matrix int adjMatrix[MAX][MAX]; //vertex count int vertexCount = 0; //stack functions void push(int item) { stack[++top] = item; } int pop() { return stack[top--]; } int peek() { return stack[top]; } bool isStackEmpty() { return top == -1; } //graph functions //add vertex to the vertex list void addVertex(char label) { struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex)); vertex->label = label; vertex->visited = false; lstVertices[vertexCount++] = vertex; } //add edge to edge array void addEdge(int start,int end) { adjMatrix[start][end] = 1; adjMatrix[end][start] = 1; } //display the vertex void displayVertex(int vertexIndex) { printf("%c ",lstVertices[vertexIndex]->label); } //get the adjacent unvisited vertex int getAdjUnvisitedVertex(int vertexIndex) { int i; for(i = 0; i < vertexCount; i++) { if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false) { return i; } } return -1; } void depthFirstSearch() { int i; //mark first node as visited lstVertices[0]->visited = true; //display the vertex displayVertex(0); //push vertex index in stack push(0); while(!isStackEmpty()) { //get the unvisited vertex of vertex which is at top of the stack int unvisitedVertex = getAdjUnvisitedVertex(peek()); //no adjacent vertex found if(unvisitedVertex == -1) { pop(); } else { lstVertices[unvisitedVertex]->visited = true; displayVertex(unvisitedVertex); push(unvisitedVertex); } } //stack is empty, search is complete, reset the visited flag for(i = 0;i < vertexCount;i++) { lstVertices[i]->visited = false; } } int main() { int i, j; for(i = 0; i < MAX; i++) // set adjacency { for(j = 0; j < MAX; j++) // matrix to 0 adjMatrix[i][j] = 0; } addVertex('S'); // 0 addVertex('A'); // 1 addVertex('B'); // 2 addVertex('C'); // 3 addVertex('D'); // 4 addEdge(0, 1); // S - A addEdge(0, 2); // S - B addEdge(0, 3); // S - C addEdge(1, 4); // A - D addEdge(2, 4); // B - D addEdge(3, 4); // C - D printf("Depth First Search: ") depthFirstSearch(); return 0; }
Depth First Search: S A D B C
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)