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

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

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

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

 

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • technologist_41
    已采纳
    #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;
    }
    
    

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

    点赞 1 评论
  • technologist_32
    CSDN专家-Time 2021-06-13 06:42

    深搜用栈,广搜用队列。

    把树的模型建好,然后对节点遍历就好啦。

    点赞 评论
  • QA_Assistant
    有问必答小助手 2021-06-15 18:48

    您好,我是有问必答小助手,您的问题已经有小伙伴解答了,您看下是否解决,可以追评进行沟通哦~

    如果有您比较满意的答案 / 帮您提供解决思路的答案,可以点击【采纳】按钮,给回答的小伙伴一些鼓励哦~~

    ps:问答VIP仅需29元,即可享受5次/月 有问必答服务,了解详情>>>https://vip.csdn.net/askvip?utm_source=1146287632

    点赞 评论

相关推荐