赞
踩
广度优先搜索(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; }
代码的主要步骤如下:
创建一个队列:在广度优先搜索中,我们使用队列来存储尚未访问过的节点。在这个示例中,我们使用一个结构体来表示队列,并实现了向队列中添加元素(enqueue)、从队列中移除元素(dequeue)以及检查队列是否为空(isEmpty)的操作。
创建一个图:我们使用一个结构体来表示图,并实现了创建新图(createGraph)和添加边(addEdge)的操作。在这个示例中,我们假设图是无向的,所以如果存在一条从节点A到节点B的边,那么就存在一条从节点B到节点A的边。
执行广度优先搜索:
主函数:在主函数中,我们创建了一个新的图,并添加了一些边。然后,我们从节点0开始执行广度优先搜索。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。