graph.cpp

用c++写的无向图的基本操作 包括深度遍历和广度遍历

#include<iostream>
#include "queue.h"
using namespace std;
#define MAX_VERTEX_NUM 20
typedef int Status;
//#define OK  2
#define TRUE 1
//#define ERROR -1
#define FALSE 0
typedef char VertexType;
typedef struct ArcNode{                 //顶点存储节点包含指向相邻顶点的指针域
	int adjvex;
	struct ArcNode *nextarc;
	//  InfoType *info;
}ArcNode;
typedef struct VNode{                    //用于存储相邻顶点的链表节点
	VertexType data;
	ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct {                          //图的存储结构
	AdjList vertices;
	int vexnum,arcnum;
	//int kind;                           //图的种类标志
}ALGraph;
Status CreatALGraph(ALGraph &G)
{
	cout<<"请输入无向图的顶点数"<<endl;
	cin>>G.vexnum;cout<<endl;
	cout<<"请输入无向图的边数"<<endl;
	cin>>G.arcnum;cout<<endl;
	cout<<"请依次输入无向图的顶点"<<endl;
	for(int v=0;v<G.vexnum;v++)
	{
		cin>>G.vertices[v].data;
		G.vertices[v].firstarc=NULL;
	}
	cout<<"顶点输入完成"<<endl<<endl;
	for(v=0;v<G.vexnum;v++)
	{
		cout<<"请输入与第"<<v+1<<"个顶点相邻的顶点的下标"<<endl;
		cout<<"没有顶点或输入完毕输入888"<<endl;
		ArcNode *b,*p;                                             //辅助指针
		int a;cin>>a;int c=1;           //c用于判断是否为第一条临边        
		while(a!=888)
		{
			b=new ArcNode;if(!b)exit(1);
			b->adjvex=a-1;b->nextarc=NULL;                 //在数组中编号比实际小1
			if(c==1)
			{
				G.vertices[v].firstarc=b;          //添加第一条相邻顶点信息
				p=b;
			}
			else
			{
				p->nextarc=b;
				p=p->nextarc;                      //添加边节点
			}
			c++;
			cin>>a;
		}
	}
	return OK;	
}
Status ShowALGraph(ALGraph G)
{
	cout<<"所有顶点如下"<<endl;
	for(int v=0;v<G.vexnum;v++)
	{
		cout<<"第"<<v+1<<"个顶点"<<G.vertices[v].data<<"   ";
	}
	cout<<endl;
	cout<<endl;
	for(v=0;v<G.vexnum;v++)
	{
		cout<<"顶点"<<G.vertices[v].data<<"的相邻顶点如下"<<endl;
		ArcNode *b;b=G.vertices[v].firstarc;
		while(b->nextarc!=NULL)
		{
			cout<<"顶点"<<G.vertices[b->adjvex].data<<"   ";
			b=b->nextarc;
		}
		cout<<"顶点"<<G.vertices[b->adjvex].data<<"   "	;
		cout<<endl<<endl;
	}
	return OK;
}
///////////////////////////////////////////////////////////////////
void BFSTraverseALGraph(ALGraph G)                   //广度优先遍历
{
	int u;
	bool visited[MAX_VERTEX_NUM];
	for(int v=0;v<G.vexnum;v++)visited[v]=FALSE;          //初始化辅助数组
    LinkQueue Q;
	InitQueue(Q);
	for(v=0;v<G.vexnum;v++)
	{
		if(visited[v]==FALSE)                              //判断顶点是否访问过
		{
			cout<<G.vertices[v].data<<"  ";
			visited[v]=TRUE;
			EnQueue(Q,v);                               //没有的话入队，输出
		}//if
		while(Q.front!=Q.rear)
		{
			int c;
			DeQueue(Q,u);                              //用u取得队列元素
			ArcNode *b;b=G.vertices[u].firstarc;  //辅助指针b指着顶点的第一个相邻顶点
			while(b!=NULL)                            //有临节点
			{
				c=b->adjvex;                        //取得第一个临节点
				if(visited[c]==FALSE)                  //没有被访问过
				{
					cout<<G.vertices[c].data<<"  ";            //输出顶点
					visited[c]=TRUE;                          //标记
					EnQueue(Q,c);                              //进队
					b=b->nextarc;                  //b移动到下一个边节点上
				}
				else b=b->nextarc;
			}//while
		}//while
	}//for
}
///////////////////////////////////////////////////////////////////////
void DFS(ALGraph G,int v);                  //事先定义DFS函数
bool visited1[MAX_VERTEX_NUM];                   //定义辅助bool数组
void DFSTraverse(ALGraph G)                          //深度优先遍历
{
	for(int v=0;v<G.vexnum;++v)visited1[v]=FALSE;
	for(v=0;v<G.vexnum;++v)
		if(visited1[v]==FALSE)DFS(G,v);
}
void DFS(ALGraph G,int v)
{
	int w;
	visited1[v]=TRUE;cout<<G.vertices[v].data<<"  ";
	ArcNode *b;b=G.vertices[v].firstarc;        //辅助指针用于找第一个和下一个相临顶点
	if(b!=NULL)w=b->adjvex;                     //取得第一个相临顶点
	for(w;w>=0;w=b->nextarc->adjvex)
		if(visited1[w]==FALSE)DFS(G,w);
}
///////////////////////////////////////////////////////////////////////////
int main()
{
	ALGraph G;
	CreatALGraph(G);
	ShowALGraph(G);
	cout<<"广度优先遍历"<<"  ";
	BFSTraverseALGraph(G);
	cout<<endl<<endl;
	cout<<"深度优先遍历"<<"  ";
	DFSTraverse(G);
	cout<<endl<<endl;
	return 0;
}