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

Question

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

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

 

Answer 1

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

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