simplepath_dising.cpp

《数据结构》课程设计的源码

#include<iostream>
using namespace std;

#define MAX_VEX_NUM 20//图中顶点数的最大值
#define NULL 0
#define TRUE 1
#define FALSE 0

typedef struct ArcNode{
	int adjvex;             //该边所指向的顶点的位置
	struct ArcNode *nextarc;//指向下一条边的指针
}ArcNode;

typedef struct VNode{
	char data;              //顶点信息
	ArcNode *firstarc;      //指向第一条依附该结点的边的指针
}VNode,AdjList[MAX_VEX_NUM];

typedef struct ALGraph{
	AdjList vertices;       //表头结点以顺序结构的形式存储
	int vexnum,arcnum;      //图的当前顶点数和边数
}ALGraph;

int LocateVex(ALGraph *G,char ch){//返回图顶点ch在图G中的位置
	int i,k;
	for(i=0;i<G->vexnum;i++){
		if(ch==G->vertices[i].data)
			k=i;
	}
	return k;
}

void CreateUndgraph(ALGraph *G) //创建一个无向图   
{  
	int i,j,m,n;
	char v1,v2;
	cout<<"-----创建一个无向图(用邻接表存储)-----"<<endl;
	cout<<"请输入无向图的顶点数:";
	cin>>G->vexnum;
	cout<<"请输入无向图的边数(各顶点度之和):";
	cin>>G->arcnum;
	cout<<"请输入顶点向量:"; 
	for(i=0;i<G->vexnum;i++)//
	{
		cin>>G->vertices[i].data;
		G->vertices[i].firstarc=NULL;
	}
	for(j=0;j<G->arcnum;j++)
	{
		cout<<"请输入第"<<j+1<<"条边依附的顶点:";
		cin>>v1>>v2;
        m=LocateVex(G,v1);
		n=LocateVex(G,v2);
		ArcNode *p=new ArcNode;  
		p->adjvex=n;
		p->nextarc=G->vertices[m].firstarc;  //将P插入到链表的前面(头插法建立单链表)
		G->vertices[m].firstarc=p;
	}
}

void DispUndGraph(ALGraph *G) //输出一个无向图的邻接表
{
	int i,k;
	cout<<"-----输出一个无向图的邻接表-----"<<endl;
	for(i=0;i<G->vexnum;i++)
	{
		int have=0;
		ArcNode *p=G->vertices[i].firstarc;
		while(p)
		{
			k=p->adjvex;
			cout<<"("<<G->vertices[i].data<<","<<G->vertices[k].data<<")";
			p=p->nextarc;
			have=1;
		}
		if(have==1)
			cout<<endl;
	}
}

int FirstAdjvex(ALGraph *G,char v)//返回图G中顶点v的第一个邻接顶点的位置
{
	int i,w1;
	i=LocateVex(G,v);
	ArcNode *p=G->vertices[i].firstarc;
	if(p!=NULL)
		w1=p->adjvex;
	return w1;
}

/*int NextAdjvex(ALGraph *G,char v,int w1)
{
	int i,w2;
	i=LocateVex(G,v);
	ArcNode *p=G->vertices[i].firstarc;
	while(p!=NULL)
	{
		if(p->nextarc!=NULL)
		{
	 		p=p->nextarc;
			if(p->adjvex!=w1)
				w2=p->adjvex;
		}
		else  p=NULL;
	}
	return w2;
}*/

int NextAdjvex(ALGraph *G,char v,int w1)//返回图G中顶点v的(相对于w1的)下一个邻接顶点的位置
{
	int i,w2;
	i=LocateVex(G,v);
	ArcNode *p=G->vertices[i].firstarc;
	while(p!=NULL)
	{
		if(p->adjvex==w1)
		{
			if(p->nextarc!=NULL)
			{
				w2=p->nextarc->adjvex;
				return w2;
			}
			else
			{
				w2=-1;
				return w2;
			}
		}
		p=p->nextarc;
	}
	if(p==NULL)  w2=-1;
	return w2;
}

bool visited[MAX_VEX_NUM];//引入辅助数组记录顶点是否已被访问过：一旦访问了顶点v，便置visited[i]为真。
char CurrentPath[MAX_VEX_NUM];//引入辅助数组保存搜索到的一条满足条件的简单路径的顶点

void Print_Path(ALGraph *G,char v1,char v2)//输出优先搜索到的顶点v1和顶点v2间的一条简单路径
{
	int i,j,m;
	i=LocateVex(G,v1);
	j=LocateVex(G,v2);
	cout<<"("<<v1<<" ";
	for(m=i;m!=j;m=LocateVex(G,CurrentPath[m]))
		cout<<CurrentPath[m]<<" ";
	cout<<")"<<endl;
}

bool DFSTraverse(ALGraph *G,char v1,char v2,int k)
{
    int i,j,w;
    char temp;
	i=LocateVex(G,v1);
	j=LocateVex(G,v2);
	visited[i]=TRUE;
	for(w=FirstAdjvex(G,v1);w>=0;w=NextAdjvex(G,v1,w))
	{
		if(w==-1)//----------------------------------------------------------
		{
			visited[i]=FALSE;
			break;
		}
		if(!visited[w])
		{		
			if(k==1&&w==j)
			{	
				CurrentPath[i]=v2;
				//cout<<"CurrentPath["<<i<<"]="<<CurrentPath[i]<<endl;
			    cout<<"存在一条符合条件的简单路径!"<<endl;
				//Print_Path(G,v1,v2);
				return 1;
              	
			}
			else if(k==1) continue;
			else if(w==j) continue;	
			else
			{ 
				temp=G->vertices[w].data;
				//cout<<"temp="<<temp<<endl;//----------------------------------跟踪!
			    CurrentPath[i]=temp;
				//cout<<"CurrentPath["<<i<<"]="<<CurrentPath[i]<<endl;//----------------------
			    if(DFSTraverse(G,temp,v2,k-1))
					return 1;
				else
					return 0;
			}			
		}
	}//for
	//cout<<" Not Exist\n";
	return 0;
}

bool Exist_Path_Len(ALGraph *G,char v1,char v2,int k)//判别图G中顶点v1和v2间是否存在长度为k的简单路径
{
	int i;
	bool Dfs;
	for(i=0;i<G->vexnum;++i)
		visited[i]=FALSE; 
	if(!visited[i])
		Dfs=DFSTraverse(G,v1,v2,k);
	if(Dfs)
	{
		cout<<"这条简单路径是:"<<endl;
		Print_Path(G,v1,v2);
	}
	else cout<<"Not Exist!"<<endl;
    return Dfs;
}

void Readme()
{
	cout<<"************************************************************"<<endl;
	cout<<"             武汉理工大学**计算机科学与技术专业             "<<endl;
	cout<<"           郑素芹**0506班**34号**数据结构课程设计           "<<endl;
    cout<<"           题目:图中两个顶点之间的简单路径的判别            "<<endl;
	cout<<"************************************************************"<<endl;
	cout<<endl;
}
    		   		
void main()
{
	Readme();
	ALGraph G;
	CreateUndgraph(&G);
	DispUndGraph(&G);
	char v1,v2;
	int k;	
	int input=0;
	do
	{
		cout<<"请输入无向图中任意两个顶点:";
		cin>>v1>>v2;
		cout<<"请输入长度(K为正整数):K=";
		cin>>k;
		Exist_Path_Len(&G,v1,v2,k);	
        cout<<"Continue?(Yes--1 Or No--0):";
		cin>>input;
	}while(input==1);
}