#include <fstream>
#include<iostream>
#include<stdlib.h> 
#include <stdio.h>
using namespace std;

#define MAXV 100
#define MAX 10 
#define INF 32767
#define MaxSize 100
int visited[MAX]={0};
typedef int ElemType;
typedef struct 
{	
	ElemType data[MaxSize];
	int front,rear;		//队首和队尾指针
} SqQueue;
void InitQueue(SqQueue *&q)
{	q=(SqQueue *)malloc (sizeof(SqQueue));
	q->front=q->rear=0;
}
void DestroyQueue(SqQueue *&q)
{
	free(q);
}
bool QueueEmpty(SqQueue *q)
{
	return(q->front==q->rear);
}
bool enQueue(SqQueue *&q,ElemType e)
{	if ((q->rear+1)%MaxSize==q->front)	//队满上溢出
		return false;
	q->rear=(q->rear+1)%MaxSize;
	q->data[q->rear]=e;
	return true;
}
bool deQueue(SqQueue *&q,ElemType &e)
{	if (q->front==q->rear)				//队空下溢出
		return false;
	q->front=(q->front+1)%MaxSize;
	e=q->data[q->front];
	return true;
}
typedef int InfoType;
typedef struct ANode{ 	
	int adjvex;    //该边的邻接点编号
   	struct ANode *nextarc;    //指向下一条边的指针
   	int weight;   	                    //该边的相关信息
}ArcNode;  
	      
 //边结点类型
typedef struct Vnode{
	
	InfoType info; 	       //顶点信息
    ArcNode *firstarc;           //指向第一个边结点
}VNode;                //邻接表头结点类型

typedef struct{
	VNode adjlist[MAXV];   //邻接表头结点数组
      int n,e;                              //图中顶点数n和边数e
}AdjGraph;        //图邻接表类


void CreateAdj(AdjGraph *&G,int A[5][5],int n,int e)
{
	//创建图的邻接表
	int i, j; 
	ArcNode *p;
	G=(AdjGraph *)malloc(sizeof(AdjGraph));
	for(i=0;i<n;i++)
	//给邻接表中所有头结点的指针域置初值
	G->adjlist[i].firstarc=NULL;
	//指定第一个头节点的next域为空 
	for(i=0;i<n;i++)	 
	//检查邻接矩阵中每个元素
	for(j=n-1;j>=0;j--)
	if(A[i][j]!=0 && A[i][j]!=INF)
	{     //存在一条边
	       p=(ArcNode *)malloc(sizeof(ArcNode));	//创建一个结点p
	       p->adjvex=j;		 //存放邻接点
	       p->weight=A[i][j];		 //存放权
	       p->nextarc=G->adjlist[i].firstarc;     //插入结点p
	       G->adjlist[i].firstarc=p;
    }
      G->n=n;
	  G->e=e;
}


void DispAdj(AdjGraph *G){ 	
//输出邻接表G
      int i; 
	  ArcNode *p;
      for(i=0;i<G->n;i++)
	  {
           p=G->adjlist[i].firstarc;
           printf("%3d: ",i);
         //  cout<<i;
    while(p!=NULL)
	{
	  printf("%3d[%d]→",p->adjvex,p->weight);
	  
	  //形成 p->
	  //  cout<<p->adjvex>>"->">>p->weight;
	  //cout<<p->adjvex<<" "; 
	  p=p->nextarc;
	  
    }
         printf("∧\n");
         //cout<<"^"<<endl;
      }
}
int dushu(int A[5][5],int n)
{
	int k;
	k=0;
	for(int j=0;j<5;j++)
	{
		if(A[n][j]==1)
		{
		k=k+1;
		}	
	}
	return (k);
}

void panduan(int A[5][5],int a,int b)
{
	if(A[a][b]==1)
	cout<<"该点之间有连接"<<endl;
	else
	cout<<"无连接"<<endl;
}

//深度优先算法 
void DFS(AdjGraph *G,int v)  
{
	ArcNode *p;
	visited[v]=1;                   //置已访问标记
	printf("%d  ",v); 				//输出被访问顶点的编号
	p=G->adjlist[v].firstarc;      	//p指向顶点v的第一条弧的弧头结点
	while (p!=NULL) 
	{
		if (visited[p->adjvex]==0)	//若p->adjvex顶点未访问,递归访问它
			DFS(G,p->adjvex);    
		p=p->nextarc;              	//p指向顶点v的下一条弧的弧头结点
	}
}


//广度优先算法
void BFS(AdjGraph *G,int v)
{
	int w,i;ArcNode *p; 
	SqQueue *qu;//初始化环形队列指针
	InitQueue(qu);//初始化队列
	int visited[MAXV];//定义标记访问数组
	for(i=0;i<G->n;i++)
	visited[i]=0;//访问标记数组初始化
	cout<<v<<" ";
	visited[v]=1;//给已经访问过结点做标记
	enQueue(qu,v);
	while(!QueueEmpty(qu))   //当队不空时进行循环 
	{
		deQueue(qu,w);//顶点w出队
		p=G->adjlist[w].firstarc;//指向w的第一个邻接点
		while(p!=NULL)///查找w的所有的邻接点 
		{
		if(visited[p->adjvex]==0)//判断当前结点是否未被访问
		{
		cout<<p->adjvex<<" ";//输出该邻接点
		visited[p->adjvex]=1;//给已经邻接点赋值1，作为已经访问的标记
		enQueue(qu,p->adjvex);//该顶点进队 
		
		}	
		p=p->nextarc;//p指向下一个邻接点	
		} 		
	 }
 } 
 
 //图是否连通
  bool Connect(AdjGraph *G)	//判断无向图G的连通性
{	int i;
	bool flag=true;
	for (i=0;i<G->n;i++)	//visited数组置初值
		visited[i]=0;
	DFS(G,0);				//调用前面的中DSF算法,从顶点0开始深度优先遍历
	for (i=0;i<G->n;i++)
		if (visited[i]==0)
		{	flag=false;
			break;
		}
	return flag;
}
void PathAll(AdjGraph *G,int u,int v,int l,int path[],int d)
{	//d表示path中的路径长度，初始为-1
	int w,i; 	ArcNode *p;
	visited[u]=1;
	d++; path[d]=u;				//路径长度d增1，顶点u加入到路径中
	if (u==v && d==l)			//输出一条路径
	{	printf("  ");
		for (i=0;i<=d;i++)
			printf("%d ",path[i]);
		printf("\n");
	}
	p=G->adjlist[u].firstarc;	//p指向顶点u的第一个邻接点
	while (p!=NULL)
	{	w=p->adjvex;			//w为u的邻接点
		if (visited[w]==0)		//若该顶点未标记访问,则递归访问之
			PathAll(G,w,v,l,path,d);
		p=p->nextarc;			//p指向顶点u的下一个邻接点
	}
	visited[u]=0;				//恢复环境：使该顶点可重新使用
}


int main()
{
	  system("color 00a");
	  int path[100];//简单路径使用path 
	  int d=-1;//简单路径的长度，初始化为-1 
	  AdjGraph *G;
	  int k;
	  int v,u,l;//u定义深度优先遍历的开始结点
	  //int A[5][5]={{0,1,0,1,0},{1,0,1,0,1},{0,1,0,1,1},{1,0,1,0,0},{0,1,1,0,0}};
	
	  
	 ifstream fileinput;
	 fileinput.open("E:\\input1.txt");
	 char h[4];
	int A[5][5];
	for (long i=0;i<=4;i++)
	{
	fileinput>>h;
	for (int j=0;j<=4;j++)
		{
	fileinput>>A[i][j];
		}
	}
	fileinput.close(); 
//	for(int s=0;s<=)
	  int n,e;
	  cout<<"输入顶点个数"<<endl;
	  cin>>n;
	  cout<<"输入边数"<<endl;
	  cin>>e;
	  cout<<"创建图"<<endl;
//	  cout<<"输入邻接矩阵数组A"<<endl;
//	  for(int i=0;i<n;i++)
//	  for(int j=0;j<n;j++)
//	  {
//	  	cin>>A[i][j];
//	  }
//	  
	  CreateAdj(G,A,n,e);
	  
	  while(1)
	  	{
	  		cout<<"按【0】退出本程序"<<endl;
	  		cout<<"按【1】输出图"<<endl;
	  		cout<<"按【2】计算度数"<<endl;
	  		cout<<"按【3】判断是否有连接"<<endl;
	  		cout<<"按【4】深度优先遍历"<<endl;
	  		cout<<"按【5】广度优先遍历"<<endl;
	  		cout<<"按【6】判断该图是否连通"<<endl;
	  		cout<<"按【7】输出简单路径"<<endl;
	  		cout<<"输入你的操作"<<endl;
	  		cin>>k;
			if(k==0)
			{
				cout<<"程序退出"<<endl;
				exit(0); 
			 } 
	  		if(k==1)
	  	{
	  		cout<<"输出图"<<endl; 
	  		DispAdj(G);
	  		continue;
		}
		if(k==2)
		{
			int x;
			int n;
			cout<<"请输入你要查找的结点"<<endl;
			cin>>n; 
			x=dushu(A,n);
			cout<<"度数为"<<x<<endl;
		}
		if(k==3)
		{
			int a,b;
			cout<<"请输入第一个结点"<<endl;
			cin>>a; 
			cout<<"请输入第二个结点"<<endl;
			cin>>b; 
		panduan(A,a,b);	
		}
		if(k==4)
		{
			cout<<"请输入开始结点v"<<endl;
			cin>>v;
			DFS(G,v);
		}
	  	if(k==5)
		  {
		  	cout<<"输入访问的初始结点"<<endl;
		  	cin>>v;
		  	BFS(G,v);	
		  }
		  
		if(k==6)
		{
			cout<<"若顶点全部访问到代表该图连通，若没有全部访问到代表该图不连通"<<endl;
			cout<<Connect(G)<<endl;
		 } 
		if(k==7)
		{
			cout<<"请输入第一个结点"<<endl;
			cin>>u;
			cout<<"请输入第二个结点"<<endl;
			cin>>v;
			cout<<"请输入路径长度"<<endl;
			cin>>l; 
			PathAll(G,u,v,l,path,d);
			
			
		 } 
		
	 
	 
	
}	
	
}