用C++完成图的深度优先遍历算法、广度优先遍历算法。其中,邻接表的创建相当于创建多个单链表。图内的节点由字母构成
时间: 2024-03-10 22:46:15 浏览: 62
好的,我理解了您的问题。以下是使用C++实现图的深度优先遍历算法和广度优先遍历算法,其中节点由字母构成,邻接表使用单链表实现。
```c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 定义图的节点结构体
struct GraphNode {
char label; // 节点的字符标签
vector<GraphNode*> neighbors; // 存储与该节点相邻的所有节点指针
GraphNode(char x) : label(x) {}; // 构造函数
};
// 深度优先遍历算法
void dfs(GraphNode* node, vector<bool>& visited) {
visited[node->label - 'a'] = true; // 标记该节点已被访问
cout << node->label << " "; // 输出该节点的标签
// 遍历该节点的所有相邻节点,若未被访问,则递归访问该节点
for (int i = 0; i < node->neighbors.size(); i++) {
GraphNode* neighbor = node->neighbors[i];
if (!visited[neighbor->label - 'a']) {
dfs(neighbor, visited);
}
}
}
// 广度优先遍历算法
void bfs(GraphNode* node, vector<bool>& visited) {
queue<GraphNode*> q; // 定义队列存储待访问的节点
q.push(node); // 将起始节点加入队列
visited[node->label - 'a'] = true; // 标记该节点已被访问
while (!q.empty()) {
GraphNode* cur = q.front(); // 取出队首节点
q.pop();
cout << cur->label << " "; // 输出该节点的标签
// 遍历该节点的所有相邻节点,若未被访问,则加入队列
for (int i = 0; i < cur->neighbors.size(); i++) {
GraphNode* neighbor = cur->neighbors[i];
if (!visited[neighbor->label - 'a']) {
visited[neighbor->label - 'a'] = true;
q.push(neighbor);
}
}
}
}
int main() {
// 创建图的邻接表,其中节点由字母构成
GraphNode* a = new GraphNode('a');
GraphNode* b = new GraphNode('b');
GraphNode* c = new GraphNode('c');
GraphNode* d = new GraphNode('d');
GraphNode* e = new GraphNode('e');
a->neighbors.push_back(b);
a->neighbors.push_back(d);
b->neighbors.push_back(a);
b->neighbors.push_back(c);
b->neighbors.push_back(e);
c->neighbors.push_back(b);
c->neighbors.push_back(e);
d->neighbors.push_back(a);
d->neighbors.push_back(e);
e->neighbors.push_back(b);
e->neighbors.push_back(c);
e->neighbors.push_back(d);
// 调用深度优先遍历算法
vector<bool> visited1(5, false);
dfs(a, visited1);
cout << endl;
// 调用广度优先遍历算法
vector<bool> visited2(5, false);
bfs(a, visited2);
cout << endl;
return 0;
}
```
希望这个实现对您有所帮助!
阅读全文