数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
服装研究
法律研究使用邻接矩阵实现BFS
广度优先搜索（BFS）是一种简单的图遍历算法，它逐步检查图。它从一个特定顶点（源）开始，以有序的方式检查其所有邻居，然后再转到其他顶点的下一层。在这篇博文中，我们将探讨三种使用 C++ 方法在邻接矩阵中实现 BFS 的不同方法。我们将介绍每种方法使用的算法，提供相关的代码示例，并演示每种方法的独特结果。
使用的方法
迭代式BFS
带层级信息的BFS
BFS 最短路径
迭代式BFS
第一种方法使用邻接矩阵和迭代方法来实现 BFS。它使用一个队列来跟踪需要访问的顶点。
算法
创建一个数组和队列来记录已访问的顶点。
将源顶点入队，并将其标记为已访问。
当队列仍然存在时，执行以下操作：
从队列中出队并显示一个顶点。
将所有未访问的相邻顶点标记为已访问，并将它们全部入队。
示例
#include <iostream>
#include <queue>
using namespace std;
// Function to perform Iterative BFS using adjacency matrix
void BFS(int** adjacencyMatrix, int numVertices, int startVertex) {
// Create a boolean array to track visited vertices
bool* visited = new bool[numVertices];
for (int i = 0; i < numVertices; i++) {
visited[i] = false;
}
// Create a queue for BFS traversal
queue<int> q;
// Enqueue the starting vertex and mark it as visited
q.push(startVertex);
visited[startVertex] = true;
while (!q.empty()) {
// Dequeue a vertex from the queue
int currentVertex = q.front();
q.pop();
// Process the current vertex (e.g., print it)
cout << currentVertex << " ";
// Iterate through all vertices
for (int i = 0; i < numVertices; i++) {
// Check if there is an edge between currentVertex and vertex i
// and if vertex i is not visited
if (adjacencyMatrix[currentVertex][i] == 1 && !visited[i]) {
// Enqueue the vertex i and mark it as visited
q.push(i);
visited[i] = true;
}
}
}
delete[] visited;
}
// Example usage
int main() {
int numVertices = 5;
// Create an adjacency matrix for the graph
int** adjacencyMatrix = new int*[numVertices];
for (int i = 0; i < numVertices; i++) {
adjacencyMatrix[i] = new int[numVertices];
}
// Initialize the adjacency matrix (example graph)
adjacencyMatrix[0][1] = 1;
adjacencyMatrix[0][2] = 1;
adjacencyMatrix[1][3] = 1;
adjacencyMatrix[2][3] = 1;
adjacencyMatrix[3][4] = 1;
int startVertex = 0; // Starting vertex for BFS
// Perform BFS traversal
cout << "BFS traversal starting from vertex " << startVertex << ":" << endl;
BFS(adjacencyMatrix, numVertices, startVertex);
// Clean up
for (int i = 0; i < numVertices; i++) {
delete[] adjacencyMatrix[i];
}
delete[] adjacencyMatrix;
return 0;
}
输出
BFS traversal starting from vertex 0: 0 1 2 3 4
带层级信息的BFS
第三种方法向标准 BFS 执行添加了每个顶点所需的层级信息。当需要每个顶点到起始点的距离时，这将非常有用。
算法
创建一个队列、一个用于标记已访问顶点的数组和一个用于存储每个顶点层级的数组。
将起始顶点的层级设置为 0，将其入队，并将其标记为已访问。
当队列仍然存在时，执行以下操作：
显示一个顶点的层级并将其从队列中出队。
将所有未访问的相邻顶点入队，标记为已访问，并将它们的层级从当前顶点的层级增加 1。
示例
#include <iostream>
#include <queue>
#include <vector>
// Function to perform Breadth First Search (BFS) with level information
void bfsWithLevel(const std::vector<std::vector<int>>& graph, int source) {
int numVertices = graph.size();
// Create visited array to keep track of visited vertices
std::vector<bool> visited(numVertices, false);
// Create level array to store the level of each vertex
std::vector<int> level(numVertices, 0);
// Create a queue for BFS traversal
std::queue<int> q;
// Mark the source vertex as visited and enqueue it
visited[source] = true;
q.push(source);
while (!q.empty()) {
// Dequeue a vertex from the queue
int currentVertex = q.front();
q.pop();
// Process the current vertex
std::cout << "Vertex: " << currentVertex << " Level: " << level[currentVertex] << std::endl;
// Explore all adjacent vertices of the current vertex
for (int adjacentVertex = 0; adjacentVertex < numVertices; ++adjacentVertex) {
// If there is an edge from the current vertex to the adjacent vertex and
// the adjacent vertex is not visited yet
if (graph[currentVertex][adjacentVertex] == 1 && !visited[adjacentVertex]) {
// Mark the adjacent vertex as visited
visited[adjacentVertex] = true;
// Update the level of the adjacent vertex
level[adjacentVertex] = level[currentVertex] + 1;
// Enqueue the adjacent vertex
q.push(adjacentVertex);
}
}
}
}
int main() {
// Example usage
std::vector<std::vector<int>> graph = {
{0, 1, 1, 0},
{1, 0, 0, 1},
{1, 0, 0, 1},
{0, 1, 1, 0}
};
bfsWithLevel(graph, 0);
return 0;
}
输出
Vertex: 0 Level: 0 Vertex: 1 Level: 1 Vertex: 2 Level: 1 Vertex: 3 Level: 2
BFS 最短路径
第四种方法使用 BFS 来查找由邻接矩阵表示的图中起始顶点和目标顶点之间的最短路径。它跟踪每个顶点的父节点以便重建路径。
算法
创建一个队列、一个用于标记已访问顶点的数组、一个用于存储每个顶点父节点的数组和一个用于记录到起始源的距离的数组。
将起始顶点的父节点设置为 -1，距离设置为 0，同时将其标记为已访问并入队。
当队列仍然存在时，执行以下操作：
从队列中出队一个顶点。
如果出队的顶点是目标顶点，则终止 BFS。
将它们的父节点添加到当前顶点，将所有未访问的相邻顶点标记为已访问，将它们入队，并更新它们之间的距离。
如果已到达目标顶点，则使用父节点数组从目标顶点回溯到起始点。
示例
#include <iostream>
#include <queue>
#include <vector>
#include <utility> // for std::pair
using namespace std;
void BFS(vector<pair<int, int>>& edgeList, int numVertices, int source) {
vector<bool> visited(numVertices, false);
vector<int> distance(numVertices, 0);
queue<int> q;
// Mark the source vertex as visited and enqueue it
visited[source] = true;
q.push(source);
while (!q.empty()) {
int currentVertex = q.front();
q.pop();
// Process the current vertex (e.g., print its value)
cout << currentVertex << " ";
// Explore all adjacent vertices of the current vertex
for (const auto& edge : edgeList) {
int u = edge.first;
int v = edge.second;
if (u == currentVertex && !visited[v]) {
visited[v] = true;
distance[v] = distance[currentVertex] + 1;
q.push(v);
} else if (v == currentVertex && !visited[u]) {
visited[u] = true;
distance[u] = distance[currentVertex] + 1;
q.push(u);
}
}
}
}
int main() {
int numVertices = 6;
// Example graph representation (edge list)
vector<pair<int, int>> edgeList = {
{0, 1},
{0, 2},
{1, 3},
{2, 3},
{2, 4},
{3, 4},
{3, 5},
{4, 5},
{1, 0}
};
int source = 0; // Starting vertex for BFS
cout << "BFS Traversal: ";
BFS(edgeList, numVertices, source);
return 0;
}
输出
BFS Traversal: 0 1 2 3 4 5
结论
在这篇文章中，我们探讨了三种在 C++ 算法中使用邻接矩阵实现广度优先搜索 (BFS) 的不同方法。每种方法在逐步遍历图时都提供了多种功能，包括迭代式 BFS、递归式 BFS、带层级信息的 BFS 以及查找最短路径。通过理解和应用这些方法，您可以有效地探索和分析图、执行基于层级的操作以及查找顶点之间的最短路径。选择哪种方法将取决于当前图的具体需求和特性。
更新于：2023年7月14日
4K+ 次浏览
广告