c语言广度优先搜索(Breadth-First Search,BFS)

2023-12-28 13:45:08

广度优先搜索(Breadth-First Search,BFS)是一种用于遍历或搜索树或图的结构的算法。这个算法从图的某一结点开始遍历,然后访问所有相邻的节点。然后对这些相邻节点,再看它们的未被访问过的相邻节点,以此类推。这种方式就是广度优先,也可以理解为先访问完一层再访问下一层。

以下是一个使用广度优先搜索访问图的C语言代码示例。为了简化问题,我们假设图中的节点表示为整数,并使用邻接矩阵来表示图。代码中有详细的注释和解释。

#include <stdio.h>
#define SIZE 40

struct queue {
    int items[SIZE];
    int front;
    int rear;
};

// 创建一个新的队列
struct queue* createQueue() {
    struct queue* q = malloc(sizeof(struct queue));
    q->front = -1;
    q->rear = -1;
    return q;
}

// 向队列中添加元素
void enqueue(struct queue* q, int value) {
    if (q->rear == SIZE - 1)
        printf("\nQueue is Full!!");
    else {
        if (q->front == -1)
            q->front = 0;
        q->rear++;
        q->items[q->rear] = value;
    }
}

// 从队列中移除元素
int dequeue(struct queue* q) {
    int item;
    if (q->front == -1) {
        printf("Queue is empty");
        item = -1;
    } else {
        item = q->items[q->front];
        q->front++;
        if (q->front > q->rear) {
            q->front = q->rear = -1;
        }
    }
    return item;
}

// 检查队列是否为空
int isEmpty(struct queue* q) {
    if (q->rear == -1) 
        return 1;
    else 
        return 0;
}

// 创建一个图
struct Graph {
  int numVertices;
  int** adjMatrix;
};

// 创建一个新的图
struct Graph* createGraph(int vertices) {
  struct Graph* graph = malloc(sizeof(struct Graph));
  graph->numVertices = vertices;

  graph->adjMatrix = malloc(vertices * sizeof(int*));
  for (int i = 0; i < vertices; i++) {
    graph->adjMatrix[i] = malloc(vertices * sizeof(int));
  }

  // 初始化邻接矩阵
  for (int i = 0; i < vertices; i++) {
    for (int j = 0; j < vertices; j++)
      graph->adjMatrix[i][j] = 0;
  }

  return graph;
}

// 添加边
void addEdge(struct Graph* graph, int src, int dest) {
  graph->adjMatrix[src][dest] = 1;
  graph->adjMatrix[dest][src] = 1;
}

// 执行广度优先搜索
void bfs(struct Graph* graph, int startVertex) {
  struct queue* q = createQueue();

  int visited[graph->numVertices];
  for (int i = 0; i < graph->numVertices; i++)
    visited[i] = 0;

  visited[startVertex] = 1;
  enqueue(q, startVertex);

  while (!isEmpty(q)) {
    printQueue(q);
    int currentVertex = dequeue(q);
    printf("Visited %d\n", currentVertex);

    // 遍历当前节点的所有邻居
    for (int i = 0; i < graph->numVertices; i++) {
      if (graph->adjMatrix[currentVertex][i] == 1 && !visited[i]) {
        enqueue(q, i);
        visited[i] = 1;
      }
    }
  }
}

// 主函数
int main() {
    struct Graph* graph = createGraph(6);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 4);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 4);
    addEdge(graph, 3, 4);

    bfs(graph, 0);

    return 0;
}

代码的主要步骤如下:

  1. 创建一个队列:在广度优先搜索中,我们使用队列来存储尚未访问过的节点。在这个示例中,我们使用一个结构体来表示队列,并实现了向队列中添加元素(enqueue)、从队列中移除元素(dequeue)以及检查队列是否为空(isEmpty)的操作。

  2. 创建一个图:我们使用一个结构体来表示图,并实现了创建新图(createGraph)和添加边(addEdge)的操作。在这个示例中,我们假设图是无向的,所以如果存在一条从节点A到节点B的边,那么就存在一条从节点B到节点A的边。

  3. 执行广度优先搜索

    • 首先,我们创建一个数组(visited)来记录哪些节点已经被访问过。然后,我们将起始节点添加到队列中,并标记为已访问。
    • 然后,我们进入一个while循环,直到队列为空为止。在每次循环中,我们都从队列中移除一个节点,并访问这个节点。
    • 对于每个被访问的节点,我们都遍历它的所有相邻节点,并检查它们是否已经被访问过。如果一个相邻节点尚未被访问过,那么就将它添加到队列中,并标记为已访问。
  4. 主函数:在主函数中,我们创建了一个新的图,并添加了一些边。然后,我们从节点0开始执行广度优先搜索。

文章来源:https://blog.csdn.net/weixin_44738632/article/details/135243935
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。