邻接表.cpp

数据结构作业的邻接表算法

#include<iostream.h>
#include<malloc.h>
#define max 100
int visited[max];
typedef enum{DG,DN,UDG,UDN}graphkind;
typedef struct arcnode{
	int adjvex;
	struct arcnode*nextarc;
}arcnode;
typedef struct vnode{
	int data;
	arcnode* firstarc;
}vnode;
typedef struct{
	vnode adjlist[max];
	int vexnum,arcnum;
	graphkind kind;
}algraph;
void create(algraph *g)
{
	int i,k,j;
	arcnode*s;
	cout<<"输入顶点数:";cin>>g->vexnum;
    cout<<"输入边数:";cin>>g->arcnum;
	g->kind=DG;
	for(i=0;i<g->vexnum;i++)
	{
		g->adjlist[i].data=i;
		g->adjlist[i].firstarc=NULL;
	}
	for(k=0;k<g->arcnum;k++)
	{
		cout<<"输入第"<<k+1<<"条边(节点从0到"<<g->vexnum-1<<"):";
		cin>>i>>j;
		s=(arcnode*)malloc(sizeof(arcnode));
		s->adjvex=j;
		s->nextarc=g->adjlist[i].firstarc;
		g->adjlist[i].firstarc=s;
	}
}
void display(algraph *g)
{
	int i,h;
	arcnode *s;
	cout<<"输出图:"<<endl;
	for(i=0;i<g->vexnum;i++)
	{
		s=g->adjlist[i].firstarc;
		h=0;
		while(s!=NULL)
		{
			cout<<" ("<<i<<","<<s->adjvex<<")";
			s=s->nextarc;
			h=1;
		}
		if(h==1)
			cout<<endl;
	}
}
void dfs(algraph *g,int v)
{
	arcnode*p;
	visited[v]=1;
	cout<<g->adjlist[v].data<<" ";
	p=g->adjlist[v].firstarc;
	while(p)
	{
		if(!visited[p->adjvex])
			dfs(g,p->adjvex);
		p=p->nextarc;
	}
}
void dfstraverse(algraph *g,int v)
{
	int k;
	for(k=0;k<max;k++)
		visited[k]=0;
	for(k=0;k<g->vexnum;k++)
		if(!visited[k])
			dfs(g,v);
}
typedef struct{
	int elem[max];
	int front,rear;
}queue;
void bfstraverse(algraph *g,int v)
{
	int k;arcnode*p;
	for(k=0;k<g->vexnum;++k)
		visited[k]=0;
	queue q;q.front=q.rear=0;
	visited[v]=1;
	cout<<v<<" ";
	q.elem[++q.rear]=v;
	while(q.rear!=q.front)
	{
		v=q.elem[++q.front];
		p=g->adjlist[v].firstarc;
		while(p)
		{
			if(!visited[p->adjvex])
			{
				cout<<p->adjvex<<" ";
				visited[p->adjvex]=1;
				q.elem[++q.rear]=p->adjvex;
			}
			p=p->nextarc;
		}
	}
}
void main()
{
	int v;char ch='y';
	algraph g;
	do{
		create(&g);
	    display(&g);
	    cout<<" 输入第一顶点:";cin>>v;
	    cout<<"输出深度优先遍历:"<<endl;
	    dfstraverse(&g,v);cout<<endl;
	    cout<<"输出广度优先遍历:"<<endl;
	    bfstraverse(&g,v);cout<<endl;
		cout<<"是否要继续(是y/否n)";cin>>ch;
	}while(ch!='n');
}