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条)

报告相同问题?

悬赏问题

  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗
  • ¥15 钢筋实图交点识别,机器视觉代码
  • ¥15 如何在Linux系统中,但是在window系统上idea里面可以正常运行?(相关搜索:jar包)
  • ¥50 400g qsfp 光模块iphy方案
  • ¥15 两块ADC0804用proteus仿真时,出现异常
  • ¥15 关于风控系统,如何去选择
  • ¥15 这款软件是什么?需要能满足我的需求
  • ¥15 SpringSecurityOauth2登陆前后request不一致