数据结构作业——图

要求

1，创建有向图
2，输出拓扑排序
3，输出深度遍历次序
4，输出广度遍历次序

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int in[maxn];
int f[maxn];
//队列 
typedef struct qnode{
	int x;
	struct qnode *nex;
} qnode,*queueptr;
typedef struct{
	queueptr front;
	queueptr rear;
}linkqueue;

//邻接表 
typedef struct Node{
	int x;
	Node *nex;
} *ve;
/************入队********/ 
void Push(linkqueue &q,int x)
{
	qnode *p; 
	p=new qnode;
	p->x=x;
	p->nex=NULL;
	q.rear->nex=p;
	q.rear=p;
}
/*******************得到对顶元素****************/ 
int Top(linkqueue q)
{
	return q.front->nex->x;
}
/***************出队************************/ 
void Pop(linkqueue &q)
{
	qnode *p;
	p=q.front->nex;
	q.front->nex=p->nex;
	if(q.rear==p) q.rear=q.front;
	delete p;
}
/*****************判空 *******************/
int Empty(linkqueue l)
{
	if(l.front==l.rear) return 1;
	else return 0;
}
/*********************将元素防放入邻接表之中 *******/
void Push(Node &l,int x)
{
	Node *p;
	p=new Node;
	p->nex=l.nex;
	p->x=x;
	l.nex=p;
}
/**************************深度优先搜索***************************** */
void DFS(ve *vec,int x)
{
	Node *now;
	now =new Node;
	now=vec[x]->nex;
	if(f[x]) return ;
	
	f[x]=1;
	while(now!=NULL)                                   //遍历这个节点指向的节点 
	{
		int y=now->x;
		now=now->nex;
		if(f[y]==0) {								  //如果没有标记过输出 
			printf("%d->%d\n",x,y);
			DFS(vec,y);
		} 
	}
}
/*******************************************广度优先搜索************************************************/ 
void BFS(ve *vec,int x)
{
	//初始化队列 
	linkqueue *qu;
	qu=new linkqueue;
	qu->front=qu->rear=new qnode;
	qu->front->nex=NULL;
	
	Push(*qu,x);
	while(Empty(*qu)==0)
	{
		int x=Top(*qu);
		Pop(*qu);
		f[x]=1;
		Node *now;
		now =new Node;
		now=vec[x]->nex;
		while(now!=NULL)//遍历这个节点指向的节点 
		{
			int y=now->x;
			now=now->nex;
			if(f[y]) continue; 
			printf("%d->%d\n",x,y);
			Push(*qu,y);
		}
	}
	delete qu;
}
/******************************** 拓扑排序************************************/	
void tuo_pu(ve *vec,int n,int m)
{
	//初始化队列 
	linkqueue *qu;
	qu=new linkqueue;
	qu->front=qu->rear=new qnode;
	qu->front->nex=NULL;
	 
	for(int i=1;i<=n;i++) if(in[i]==0) Push(*qu,i);             //把入度为零的节点放进队列去 
	int sum=0; 
	
/*******************************开始遍历拓扑序列 ************************************/
	while(Empty(*qu)==0)
	{
		int x=Top(*qu);
		cout<<x<<" ";
		Pop(*qu);
		sum++;
		Node *now;
		now =new Node;
		now=vec[x]->nex;
		while(now!=NULL)										//遍历这个节点指向的节点 
		{
			int y=now->x;
			in[y]--;											//将他指向的节点的入度减 1 
			if(in[y]==0)										//如果为零就放进队列去 
			{
				Push(*qu,y);
			}
			now=now->nex;
		}
	}
	if(sum!=n) puts("剩下的节点有环的出现，请你自习检查！");	//如果sum不等于n那么说明有环的存在 
	else puts("");
	delete qu; 
} 
void chang_jian(ve *vec,int &n,int &m)
{
	int x,y;
	puts("请输入该图一共有 n 个顶点，m 条边，n 和 m 的值："); 
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){										//初始化邻接表 
		in[i]=0;
		vec[i]=new Node;
		vec[i]->nex=NULL;
	}
	puts("请输入m条边，注意顶点值不能大于n");
	while(m--)													//存边 
	{
		while(1)
		{
			scanf("%d%d",&x,&y);
			if(x>0&&x<=n&&y>0&&y<=n) break;
			else puts("输入数据不合法，超出了范围请重新输入");
		}
		Push(*(vec[x]),y);
		in[y]++;                                               //入度加一 
	}
}
void zhu_cai_dan()
{
	puts("\n 返回主菜单请输输入 1");
	puts(" 创建有向图请输入 2");
	puts(" 进行拓扑排序请输入 3");
	puts(" 进行深度优先搜索请输入 4");
	puts(" 进行广度优先搜索请输入 5");
	puts(" 退出程序请输入 6");
}

int main()
{
	int n,m;
	int x,y;	
	ve vec[1000];//创建邻接表 
	int flag=1; 
	int F=0;
	zhu_cai_dan();
	while(1)
	{
		scanf("%d",&x);
		switch(x)
		{
			case 1: 
					zhu_cai_dan();
					break;
			case 2:
					if(flag==0) {
						puts("你已经创建过有向图了，请进行其他操作");
						break;
					} 
					chang_jian(vec,n,m);
					puts("创建成功"); 
					flag=0;
					break;
			case 3:	
					if(flag) 
					{
						puts("你还为创建有向图请先创建再进行操作谢谢");
						break;
					} 
					tuo_pu(vec,n,m);//拓扑函数 
					break;
			case 4:	
					if(flag) 
					{
						puts("你还为创建有向图请先创建再进行操作谢谢");
						break;
					}
					printf("请输入开始深度遍历的第一个节点是多少 节点大小在1~%d 之间\n",n);
					while(1)
					{
						scanf("%d",&x);
						if(x>0&&x<=n) break;
						else puts("输入数据不合法，超出了范围请重新输入");
					}
					for(int i=1;i<=n;i++) f[i]=0;
 					DFS(vec,x);
					break;
			case 5:	
					if(flag) 
					{
						puts("你还为创建有向图请先创建再进行操作谢谢");
						break;
					}
					printf("请输入开始深度遍历的第一个节点是多少 节点大小在1~%d 之间\n",n);
					while(1)
					{
						scanf("%d",&x);
						if(x>0&&x<=n) break;
						else puts("输入数据不合法，超出了范围请重新输入");
					}
					for(int i=1;i<=n;i++) f[i]=0;
					BFS(vec,x);
					break;
			case 6:	
					F=1;
					puts("感谢老师指导，谢谢使用");
					break;
			defalut:	puts("数据不合法请重新输入");
				
		}
		if(F) break;
	}
	return 0;
}