C 语言深度优先遍历

我们不会在 C 语言中看到深度优先遍历（或深度优先搜索）的实现。为了方便参考，我们将遵循示例，并以此作为我们的图模型 −

C 语言实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 5

struct Vertex {
   char label;
   bool visited;
};

//堆栈变量

int stack[MAX];
int top = -1;

//图变量

//顶点数组
struct Vertex* lstVertices[MAX];

//邻接矩阵
int adjMatrix[MAX][MAX];

//顶点数量
int vertexCount = 0;

//堆栈函数

void push(int item) { 
   stack[++top] = item; 
} 

int pop() { 
   return stack[top--]; 
} 

int peek() {
   return stack[top];
}

bool isStackEmpty() {
   return top == -1;
}

//图函数

//将顶点添加到顶点列表
void addVertex(char label) {
    struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));
    vertex->label = label;
    vertex->visited = false;
    lstVertices[vertexCount++] = vertex;
}

//将边添加到边数组
void addEdge(int start,int end) {
    adjMatrix[start][end] = 1;
    adjMatrix[end][start] = 1;
}

//显示顶点
void displayVertex(int vertexIndex) {
    printf("%c ",lstVertices[vertexIndex]->label);
}

//获取相邻的未访问顶点
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;
    
    //将第一个节点标记为已访问
    lstVertices[0]->visited = true;
    
    //显示顶点
    displayVertex(0);
    
    //将顶点索引压入堆栈
    push(0);

   while(!isStackEmpty()) {
      //获取栈顶顶点的未访问顶点
      int unvisitedVertex = getAdjUnvisitedVertex(peek());

      //未找到相邻顶点
      if(unvisitedVertex == -1) {
         pop();
      } else {
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         push(unvisitedVertex);
      }
   }

   //堆栈为空，搜索完成，重置访问标志
   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

depth_first_traversal.html