graph.cpp

实现一个图的遍历

#include <iostream.h>
#include <malloc.h>
#include <cstdlib>
#define Vnum 20					//  定义最多顶点数
typedef struct arcnode			//  边结构
{
	int adjvex;					//  下一边始点编号
	struct arcnode *nextarc;	//  下一边指针
}arcnode;
typedef struct vexnode			//  顶点数组
{
	int vertex;					//  顶点编号
	arcnode *firstarc;			//  指向第一条边指针
}adjlist[Vnum];
typedef struct graphs			//  图类型
{
	adjlist adjlist;			//  顶点数组
	int vexnum,arcnum;			//  顶点个数和边数
}graph;
void create(graph *g)			//  建图
{
	int n,e,i,j,k;
	arcnode *p;
	cout<<"创建一个图：\t";
	cout<<"顶点数：";
	cin>>n;
	cout<<"\t\t边数：";
	cin>>e;
	g->vexnum=n;g->arcnum=e;
	for(i=0;i<n;i++)
	{
		g->adjlist[i].vertex=i;
		g->adjlist[i].firstarc=NULL;
	}
	for(k=0;k<e;k++)
	{
		cout<<"第"<<k+1<<"条边:";
		cin>>i>>j;
		p=(arcnode *)malloc(sizeof(arcnode));		  //创建边节点
		p->adjvex=j;
		p->nextarc=g->adjlist[i].firstarc;			  //将p插到链表adjlist前
		g->adjlist[i].firstarc=p;
		
		p=(arcnode *)malloc(sizeof(arcnode));		  //边重连构造无向图
		p->adjvex=i;
		p->nextarc=g->adjlist[j].firstarc;			  
		g->adjlist[j].firstarc=p;
	}
}
void disp(graph *g)									  //输出图
{
	int i,have;
	arcnode *p;
	cout<<"输出此图节点的拓扑结构："<<endl;
	for (i=0;i<g->vexnum;i++)
	{
		p=g->adjlist[i].firstarc;
		have=0;
		while (p!=NULL)
		{
			cout<<i<<"--->"<<p->adjvex<<"\t";
			p=p->nextarc;
			have=1;
		}
		if (have==1)
			cout<<endl;

	}
}
void dfs(graph g,int v,int visited[])			  //深度优先搜索（递归法）
{
	arcnode *p;
	cout<<v<<" ";
	visited[v]=1;
	p=g.adjlist[v].firstarc;
	while (p!=NULL)
	{
		if (!visited[p->adjvex])
			dfs(g,p->adjvex,visited);			 
		p=p->nextarc;
	}
}
void dfsl(graph g,int v)						    //深度优先搜索（非递归）				
{
	int i;
	arcnode *p;
	int visited[Vnum],top=-1,stack[Vnum];
	for (i=0;i<g.vexnum;i++)
	visited[i]=0;								    //节点访问标识置0
	cout<<v<<" ";								    //访问v
	top++;										    //v入栈
	stack[top]=v;
	visited[v]=1;
	while (top>=0)								    //栈不空，循环
	{
		v=stack[top];top--;							//取栈顶
		p=g.adjlist[v].firstarc;
		while (p!=NULL&&visited[p->adjvex]==1)
			p=p->nextarc;
		if (p==NULL)								//无，退到前一个
			top--;
		else										//有，选择一个
		{
			v=p->adjvex;
			cout<<v<<" ";							//访问
			visited[v]=1;
			top++;									//入栈
			stack[top]=v;
		}
	}
	cout<<endl;
}
void bfs(graph g,int v)							 // 广度优先搜索
{
	int queue[Vnum],rear=0,first=0;
	int visited[Vnum],i;
	arcnode *p;
	for(i=0;i<Vnum;i++)							 // 赋初值
		visited[i]=0;
	cout<<v<<" ";
	visited[v]=1;
	rear++;										 // v入队
	queue[rear]=v;
	while (rear!=first)							 // 队列不空
	{
		first++;								 // 出队
		v=queue[first];
		p=g.adjlist[v].firstarc;
		while (p!=NULL)
		{
			if (!visited[p->adjvex])
			{
				cout<<p->adjvex<<" ";			 // 访问p
				visited[p->adjvex]=1;
				rear++;							 // p入队
				queue[rear]=p->adjvex;

			}
			p=p->nextarc;
		}
	}
}
int  degree(graph g, int v)						//求顶点的度
{
	arcnode *p;
	int n=0;
	p=g.adjlist[v].firstarc;
	while (p!=NULL)
	{
		n++;
		p=p->nextarc;

	}return n;
	
}
void putout(graph g,int v)						 //输出度
{
	cout<<"该顶点的度是：";
	cout<<degree(g,v);
}
void putoutmaxdu(graph g)						//输出最大度节点与度数
{
	int maxv=0,maxdu=0,i,k;
	for(i=0;i<g.vexnum;i++)
	{
		k=degree(g,i);
		if(k>=maxdu)
		{
			maxdu=k;maxv=i;
			cout<<"最大度节点是："<<maxv<<"\t"<<"度是：" <<maxdu;
		}cout<<endl;
	}
}
void main()
{
	graph g;
	int visited[Vnum],i,v;
	for (i=0;i<Vnum;i++)						 // 赋初值
		visited[i]=0;
	create(&g);
	disp(&g);
	putoutmaxdu(g);cout<<endl;
	for (int t=0;t<7;t++)
	{
	cout<<"输入顶点：";
	cin>>v;
	putout(g,v);cout<<endl;
	cout<<"深度优先序列：";
	dfsl(g,v);cout<<endl;
	cout<<"广度优先序列：";
	bfs(g,v);cout<<endl;
	}
system("pause");
}