如何学习深度优先遍历？

学习深度优先遍历建议从基础概念开始，逐步深入。本教程提供了完整的深度优先遍历入门指南，包含理论讲解和实践代码示例。建议按照教程顺序学习，并通过实际操作加深理解。

深度优先遍历有什么实际应用？

深度优先遍历在实际开发中有广泛应用。掌握深度优先遍历可以帮助您更好地完成结构和算法相关的开发任务，提升编程技能和工作效率。

深度优先遍历

大厂广告产品心法

分布式技术原理与算法解析

玩转Spring全家桶

深度优先遍历(DFS)从某个顶点出发，访问此顶点，然后从v的未被访问的邻接点触发深度优先便利图，直至所有和v有路径相通的顶点都被访问到。

如上面的示例所示，DFS算法首先从S到A到D到G到E到B，然后到F，最后到C，它采用以下规则。

规则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 没有任何未访问的相邻节点，因此我们不断弹出堆栈，直到找到一个具有未访问的相邻节点的节点为止。在这种情况下，没有任何东西，我们一直弹出直到堆栈为空。

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;   
}