数据结构&算法 深度优先遍历

• 

  深度优先遍历

  深度优先搜索（DFS）算法在深度运动中遍历图形，并在任何迭代出现死角时使用堆栈记住要获取的下一个顶点以开始搜索。

  

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

  • 规则1 - 访问相邻的未访问顶点。将其标记为已访问。显示它。将其推入堆栈。
  • 规则2 - 如果未找到相邻的顶点，则从堆栈中弹出一个顶点。（它将弹出堆栈中没有相邻顶点的所有顶点。）
  • 规则3 - 重复规则1和规则2，直到堆栈为空。

  遍历	描述
  	初始化堆栈。
  	将S标记为已访问，并将其放入堆栈。探索S中所有未访问的相邻节点。我们有三个节点，我们可以选择其中任何一个。对于此示例，我们将按字母顺序选择节点。
  	将A标记为已访问，并将其放入堆栈。探索来自A的任何未访问的相邻节点。S和D都与A相邻，但是我们仅关注未访问的节点。
  	访问D并将其标记为已访问并放入堆栈。在这里，我们有B和C节点，它们与D相邻并且都未访问。但是，我们将再次按字母顺序选择。
  	我们选择B，将其标记为已访问并放入堆栈。在这里B没有任何未访问的相邻节点。因此，我们从堆栈中弹出B。
  	我们检查堆栈顶部是否返回上一个节点，并检查它是否有未访问的节点。在这里，我们发现D在堆栈的顶部。
  	只有未访问的邻接节点是从D是C现在。因此，我们访问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;   
  }
  

  复制

  尝试一下