資料結構
網路
關係資料庫管理系統(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+ 次瀏覽
廣告