main.cpp

数据结构中图的相关算法的 应用与分析

#define UNVISITED 0
#define VISITED 1
#include <iostream.h>
#include <fstream.h>
#include"graph.cpp"
#include <queue> 
void DFS(Graph& G, int V);
void BFS(Graph& G, int V);
void graph_traverse(Graph& G,bool useDFS);
void main()
{
	char filename[20];		
	int isDirected;                        //标记是否有向图
	int numVertex;                         //图的顶点个数（边数将在setEdge中被自动修改）
	int from,to,weight;                    //读入每条边的起点，终点和权
	ifstream GraphSou;                     //输入文件流
    int choice;
	cout<<"——————第一步：构造图——————"<<endl;
	//获取构图方式
	cout<<endl;
	cout<<"请输入构图文件（例如，输入chen.txt，然后回车。请确保构图文件是正确的格式）:"<<endl;
	cin>>filename;                         //获取文件名
	
	GraphSou.open(filename);
	GraphSou>>isDirected;                  //是否有向
	if(isDirected!=0)
	{
		cout<<"文件格式不正确!"<<endl;
		return;
	}
	GraphSou>>numVertex;                    //顶点
	Graph *myGra=new Graphl(numVertex);     //图本身	
	while(!GraphSou.eof())                  //顺次读取边的信息
	{
		GraphSou>>from>>to>>weight;
		if(from>=0&&to>=0&&weight>0&&from<numVertex&&to<numVertex)
		{
			myGra->setEdge(from,to,weight);
			if(!isDirected)
			{
				myGra->setEdge(to,from,weight);
			}
		}
		else
		{
			cout<<"文件数据非法!"<<endl;
			return;
		}
	}	
	cout<<endl;
	//输出图的构造情况以便用户检查
	cout<<"**********你所构造的图具体情况如下：**********"<<endl;
	cout<<"顶点数——"<<myGra->VerticesNum()<<endl;
	cout<<"存在边如下——"<<endl;
	for(int i=0;i<myGra->VerticesNum();i++)
	{
		for(Edge e=myGra->FirstEdge(i);myGra->IsEdge(e);e=myGra->NextEdge(e))
		{			
			cout<<"始点："<<e.from<<" 终点："<<e.to<<" 权："<<e.weight<<endl;			
		}
		cout<<endl;
	}	
	//依据用户的选择来验证各种算法
	cout<<"——————第二步：验证图的算法——————"<<endl;
	cout<<"请选择要进行的操作:"<<endl;
	cout<<"1_图的深度优先周游"<<endl;
	cout<<"2_图的广度优先周游"<<endl;
	while(1)
	{		
		cout<<"你的选择是：";
		cin>>choice;
		if(choice==1)
		{
			graph_traverse(*myGra,true);
		}
		else if(choice==2)
		{
			graph_traverse(*myGra,false);
		}
		else 
		{
			return;
		}
		cout<<endl;
	}
}
//深度优先周游（从一个点开始周游）：
void DFS(Graph& G, int V)
{
	G.Mark[V]= VISITED;                           //标记该点
	cout<<V<<"\t";								  //打印
	for(Edge e=G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e))  //由该点所连的边进行深度优先周游
	{		
		if(G.Mark[G.ToVertex(e)]==UNVISITED)               //访问V邻接到的未被访问过的顶点，并递归地按照深度优先的方式进行周游
		{
			DFS(G, G.ToVertex(e));	
		}
	}
}
//广度优先周游（从一个点开始周游）：
void BFS(Graph& G, int V)
{
	using std::queue;
	queue<int> Q;                   //初始化广度优先周游要用到的队列
	
	G.Mark[V]= VISITED;             //访问顶点V，并标记其标志位
	cout<<V<<"\t";                  //打印
	Q.push(V);                      //V入队	
	while(!Q.empty())               //如果队列仍然有元素
	{
		int V=Q.front();		    //顶部元素
		Q.pop();                    //出队
		
		for(Edge e=G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e))    //将与该点相邻的每一个未访问点都入队
		{			
			if(G.Mark[G.ToVertex(e)]== UNVISITED)   //访问V邻接到的所有未被访问过的顶点
			{				
				G.Mark[G.ToVertex(e)]= VISITED;     //访问顶点V，并标记其标志位
				cout<<G.ToVertex(e)<<"\t";          //打印
				Q.push(G.ToVertex(e));              //入队				
			}			
		}
	}
}
//图周游：
void graph_traverse(Graph& G,bool useDFS)
{
	for(int i=0;i<G.VerticesNum();i++) 
	{
		//对图所有顶点的标志位进行初始化
		G.Mark[i]=UNVISITED;
	}
	for(i=0;i<G.VerticesNum();i++)      //检查图的所有顶点是否被标记过，如果未被标记，则从该未被标记的顶点开始继续周游
    {
		if(G.Mark[i]== UNVISITED)
		{
			if(useDFS)
			{
				DFS(G,i); 
			}//深度优先搜索
			else
			{
				BFS(G,i);       //广度优先搜索
			}
			
		}
	}
	cout<<endl;
}