在C++中實現圖的遍歷算法通常使用深度優先搜索(DFS)和廣度優先搜索(BFS)兩種方法。
以下是一個使用鄰接表表示圖并實現DFS和BFS算法的示例代碼:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Graph {
private:
int V;
vector<vector<int>> adj;
public:
Graph(int vertices) {
V = vertices;
adj.resize(V);
}
void addEdge(int u, int v) {
adj[u].push_back(v);
}
void DFSUtil(int v, vector<bool>& visited) {
visited[v] = true;
cout << v << " ";
for (int u : adj[v]) {
if (!visited[u]) {
DFSUtil(u, visited);
}
}
}
void DFS(int start) {
vector<bool> visited(V, false);
DFSUtil(start, visited);
}
void BFS(int start) {
vector<bool> visited(V, false);
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int v = q.front();
q.pop();
cout << v << " ";
for (int u : adj[v]) {
if (!visited[u]) {
visited[u] = true;
q.push(u);
}
}
}
}
};
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "DFS traversal starting from vertex 2: ";
g.DFS(2);
cout << endl;
cout << "BFS traversal starting from vertex 2: ";
g.BFS(2);
cout << endl;
return 0;
}
在這個示例代碼中,我們首先定義了一個Graph
類來表示圖,并實現了addEdge
、DFS
和BFS
方法來添加邊、進行深度優先搜索和廣度優先搜索。在主函數中,我們創建了一個包含4個頂點的圖,添加了邊,然后分別從頂點2開始進行DFS和BFS遍歷。