m0_57653878 2021-06-12 23:14 采纳率: 100%
浏览 61
已采纳

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

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;
    }
    
    

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

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

悬赏问题

  • ¥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,怎么评价相关性呢