m0_57653878 2021-06-12 23:14 采纳率: 100%

无向图的深度和广度遍历结果

1,从顶点2出发的深度和广度遍历结果；

2,并画出对应的深度和广度生成树

• 写回答

3条回答默认 最新

• 关注
``````#include<bits/stdc++.h>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define GRASIZE 5//定义图的顶点个数为5个节点
struct GraphNode
{
int label;
vector<GraphNode*> neighbors;
GraphNode(int x) :label(x) {};
};

class GraphOrder {
public:
//深度优先遍历
static void DFS_gra(GraphNode* graph[])
{
int visit[GRASIZE] = { 0 };

for (int i = 2; i < GRASIZE; i++)
{
if (visit[i]==0)
{
DFS_i(graph[i],visit);
}
}
}
//广度优先遍历
static void BFS_gra(GraphNode* graph[])
{
int visit[GRASIZE] = { 0 };
for (int i = 2; i < GRASIZE; i++)
{
if (visit[i] == 0)
{
BFS_i(graph[i], visit);
}
}
}
private:
//递归
static void DFS_i(GraphNode* node,int visit[]) {
visit[node->label] = 1;
cout << node->label << " ";
for (int i = 0; i < node->neighbors.size(); i++)
{
if (visit[node->neighbors[i]->label]==0)
{
DFS_i(node->neighbors[i],visit);
}
}
}
//队列实现
static void BFS_i(GraphNode* node, int visit[]) {
queue<GraphNode*> Q;
Q.push(node);
visit[node->label] = 1;
while (!Q.empty()) {
GraphNode* node = Q.front();
Q.pop();
cout << node->label << " ";
for (int i = 0; i < node->neighbors.size(); i++)
{
if (visit[node->neighbors[i]->label]==0)
{
Q.push(node->neighbors[i]);
visit[node->neighbors[i]->label] = 1;
}
}
}
}
};
int main()
{
GraphNode* graph[GRASIZE];
for (int i = 0; i < GRASIZE; i++)
{
graph[i] = new GraphNode(i);
}
graph[0]->neighbors.push_back(graph[1]);
graph[0]->neighbors.push_back(graph[2]);
graph[1]->neighbors.push_back(graph[0]);
graph[1]->neighbors.push_back(graph[3]);
graph[1]->neighbors.push_back(graph[4]);
graph[2]->neighbors.push_back(graph[0]);
graph[2]->neighbors.push_back(graph[3]);
graph[3]->neighbors.push_back(graph[4]);
graph[3]->neighbors.push_back(graph[2]);
graph[3]->neighbors.push_back(graph[1]);
graph[4]->neighbors.push_back(graph[1]);
graph[4]->neighbors.push_back(graph[3]);

cout << "深度优先遍历:";
GraphOrder::DFS_gra(graph);
cout << endl;

cout << "广度优先遍历:";
GraphOrder::BFS_gra(graph);

for (int i = 0; i < GRASIZE; i++)
{
delete graph[i];
}
return 0;
}

``````

码字不易，如果有帮助请点一下我回答右上方的采纳，谢谢！以后有什么问题可以互相交流。

本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论

悬赏问题

• ¥50 深度学习运行代码直接中断
• ¥15 关于#单片机#的问题，请各位专家解答！
• ¥15 关于#单片机#的问题，请各位专家解答！
• ¥20 需要完整的共散射点成像代码
• ¥15 编写vba代码实现数据录入工作
• ¥15 做过TCL海信电视小米电视相关影视会员软件私我
• ¥15 Mapreduce是正常的，在运行其他jar包时并没有任何问题，只是在做LogCount.jar 时出的问题。如图所示
• ¥15 ImportError: DLL load failed while importing _iterative: 找不到指定的模块。
• ¥15 如何通过交互分析得出某高危患者对放疗获益更多
• ¥15 相关性分析中，p<0.05, r=0.29,怎么评价相关性呢