C 语言广度优先遍历

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

C 语言实现

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

#define MAX 5

struct Vertex {
   char label;
   bool visited;
};

//队列变量

int queue[MAX];
int rear = -1;
int front = 0;
int queueItemCount = 0;

//图变量

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

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

//顶点数量
int vertexCount = 0;

//队列函数

void insert(int data) {
   queue[++rear] = data;
   queueItemCount++;
}

int removeData() {
   queueItemCount--;
   return queue[front++]; 
}

bool isQueueEmpty() {
   return queueItemCount == 0;
}

//图函数

//将顶点添加到顶点列表
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 breadthFirstSearch() {
    int i;
    
    //将第一个节点标记为已访问
    lstVertices[0]->visited = true;
    
    //显示顶点
    displayVertex(0);
    
    //将顶点索引插入队列
    insert(0);
    int unvisitedVertex;
    
    while(!isQueueEmpty()) {
      //获取队列最前面的未访问顶点
      int tempVertex = removeData();   

      //未找到相邻顶点
      while((unvisitedVertex = getAdjUnvisitedVertex(tempVertex)) != -1) {    
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         insert(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("
Breadth First Search: ");
   
   breadthFirstSearch();

   return 0;
}

如果我们编译并运行上述程序，它将产生以下结果 −

输出

Breadth First Search: S A B C D

breadth_first_traversal.html