用devc++实现图的遍历
时间: 2024-01-14 12:21:10 浏览: 30
图的遍历是指按照一定的规则访问图中的所有节点。常见的图遍历算法有深度优先搜索(DFS)和广度优先搜索(BFS)。下面是使用DevC++实现图的遍历的示例代码:
```c++
#include <iostream>
#include <list>
#include <queue>
using namespace std;
class Graph {
int numVertices;
list<int> *adjLists;
public:
Graph(int vertices) {
numVertices = vertices;
adjLists = new list<int>[vertices];
}
void addEdge(int src, int dest) {
adjLists[src].push_back(dest);
}
void DFS(int vertex, bool visited[]) {
visited[vertex] = true;
cout << vertex << " ";
list<int>::iterator i;
for (i = adjLists[vertex].begin(); i != adjLists[vertex].end(); ++i) {
if (!visited[*i]) {
DFS(*i, visited);
}
}
}
void BFS(int startVertex) {
bool *visited = new bool[numVertices];
for (int i = 0; i < numVertices; i++) {
visited[i] = false;
}
queue<int> queue;
visited[startVertex] = true;
queue.push(startVertex);
while (!queue.empty()) {
int currentVertex = queue.front();
cout << currentVertex << " ";
queue.pop();
list<int>::iterator i;
for (i = adjLists[currentVertex].begin(); i != adjLists[currentVertex].end(); ++i) {
int adjVertex = *i;
if (!visited[adjVertex]) {
visited[adjVertex] = true;
queue.push(adjVertex);
}
}
}
}
};
int main() {
Graph g(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(2, 5);
cout << "Depth First Traversal (DFS): ";
bool *visited = new bool[6];
for (int i = 0; i < 6; i++) {
visited[i] = false;
}
g.DFS(0, visited);
cout << endl;
cout << "Breadth First Traversal (BFS): ";
g.BFS(0);
return 0;
}
```
这段代码创建了一个图对象,添加了一些边,并实现了深度优先搜索(DFS)和广度优先搜索(BFS)两种遍历算法。在主函数中,我们创建了一个图对象,添加了一些边,并调用了DFS和BFS函数进行遍历。