图的基本运算.cpp

共有10个文件代码

#include <iostream.h>
#include <malloc.h>
#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<<"创建一个图: "<<endl;
	cout<<" 顶点数 ";
	cin>>n;
	cout<<"边数：";
	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<< "条边(节点号从0到"<<n-1<<")";
		cin>>i>>j;
		p=(arcnode *)malloc(sizeof (arcnode));//创建边结点 
		p->adjvex=j;
		p->nextarc=g->adjlist[i].firstarc;//将p插入到adjlist[i]链表的前面
		g->adjlist[i].firstarc=p;	
	}
}
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 bfs(graph g,int v)
{
	int quene[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++;
	quene[rear]=v;
	while (rear!=first)
	
	{
		first++;
		v=queue[first];
		p=g.adjlist[v].firstarc;
		while (p!=NULL)
		{
			if (!visited[p->adjvex])
			{
				cout<<p->adjvex<<" ";
				visited[p->adjvex]=1;
				rear++;
				queue[rear]=p->adjvex;
			}
			p=p->nextarc;
		}
	}
}
void disp(graph *g)
{
    int i,h;
	arcnode *p;
	cout<<"输出图："<<endl;
	for(i=0;i<g->vexnum;i++)
	{ 
		p=g->adjlist[i].firstarc;
		h=0;
  	    while(p!=NULL)
		{
		  cout<<" ("<<i<<","<<p->adjvex<<")";
		  p=p->nextarc;
		  h=1;
		}
 	      if(h==1) cout<<endl;
	}
}
void main()
{
	graph g;
	int visited[vnum] , v;
	for(int i=0;i<vnum;i++)
		visited[i]=0;
	create(&g);
	disp(&g);
	cout<<"输入顶点 ";
	cin>>v;
	cout<<"深度优先序列 ";
    dfs( g, v,visited);
	cout<<endl;
	cout<<"广度优先序列 ";
    bfs(g, v);
	cout<<endl;


}