图的遍历.cpp

图的遍历_邻接表存储.cpp 检验深度优先和广度优先的程序(邻接表存储表示)

// 图的遍历_邻接表存储.cpp   检验深度优先和广度优先的程序(邻接表存储表示)
#include<string.h>	//strcmp()
#include<malloc.h> 
#include<process.h>	//exit()
#include<iostream.h>	//cout,cin

typedef char VertexType[5]; // 顶点类型为字符串
 // 图的邻接表存储表示
#define MAXV 20 //最大边数

struct ArcNode // 表结点结构，省掉弧的相关信息（无权图）
{
	int adjvex; // 该弧所指向的顶点的位置
	ArcNode *nextarc; // 指向下一条弧的指针
}; // 表结点

typedef struct VNode
{
	VertexType data;	// 顶点信息
	ArcNode *firstarc; // 第一个表结点的地址,指向第一条依附该顶点的弧的指针
}AdjList[MAXV]; // 头结点

struct ALGraph
{
	AdjList vertices;
	int vexnum,arcnum; // 图的当前顶点数和弧数
};
 
//与单链表的变量类型建立联系
typedef ArcNode *LinkList; // 定义指向单链表结点的指针是指向图的表结点的指针

int LocateVex(ALGraph G,VertexType u)
{ // 初始条件：图G存在，u和G中顶点有相同特征
  // 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1
	for(int i=0;i<G.vexnum;++i)
		if(strcmp(u,G.vertices[i].data)==0)
			return i;
		cout<<"无顶点"<<u<<endl;		//边的顶点数据有误
		exit(0);
}

void CreateGraph(ALGraph &G)
{ // 采用邻接表存储结构
	int i,j,k;
	VertexType vi,vj; // 连接边或弧的2顶点
	cout<<"请输入此图的顶点数和边数:";
	cin>>G.vexnum;	//读入顶点数
	cin>>G.arcnum;	//读入边数
	cout<<"请输入此图所有顶点的编号:";
	for(i=0;i<G.vexnum;++i)		// 构造顶点向量
	{
		cin>>G.vertices[i].data;
		G.vertices[i].firstarc=NULL; // 初始化与该顶点有关的出弧链表
	}
	cout<<"请输入此图的有向边(按照起点、终点依次输入):\n";
	for(k=0;k<G.arcnum;++k) // 构造相关弧链表
	{
		cin>>vi;
		cin>>vj;
        i=LocateVex(G,vi);
        j=LocateVex(G,vj);
        ArcNode *p;
        p=(ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex=j;
        p->nextarc=G.vertices[i].firstarc;
        G.vertices[i].firstarc=p;
	}
}

void Display(ALGraph G)
{ // 输出图的邻接矩阵G
	int i;
	ArcNode *p;
	cout<<"该无向图有"<<G.vexnum<<"个顶点:";
	for(i=0;i<G.vexnum;++i)
		cout<<G.vertices[i].data<<'\t';
	cout<<"\n该无向图有"<<G.arcnum<<"条边:\n";
	for(i=0;i<G.vexnum;i++)
	{
		p=G.vertices[i].firstarc;
		while(p)
		{
			if(i<p->adjvex) // 无向图两次中只显示一次
			{ 
				cout<<G.vertices[i].data<<"-"<<G.vertices[p->adjvex].data<<endl;
			}
			p=p->nextarc;
		}
	}
	cout<<endl;
}

int visited[MAXV]; // 访问标志数组(全局量)

void DFS(ALGraph G,int v)	//仅适用于邻接表存储结构(与算法7.5有不同)
{ // 从第v个顶点出发递归地深度优先遍历图G。
   int w;
   ArcNode *p;
   visited[v]=1;	 // 设置访问标志为1(已访问)
   cout<<G.vertices[v].data<<'\t'; // 访问第v个顶点
   for(p=G.vertices[v].firstarc; p ;p=p->nextarc)
   {
	   w=p->adjvex;
	   if(!visited[w]) DFS(G,w); // 对v的尚未访问的邻接点w递归调用DFS
   }
}
void DFSTraverse(ALGraph G)
{ // 对图G作深度优先遍历。算法7.4
	int i;
	for(i=0;i<G.vexnum;i++)
		visited[i]=0; // 访问标志数组初始化
	cout<<"深度优先搜索的结果:\n";
	for(i=0;i<G.vexnum;i++)
		if(!visited[i]) DFS(G,i); // 对尚未访问的顶点调用DFS
		cout<<endl;
}

// 单链队列－－队列的链式存储结构
typedef struct QNode
{
	int data;
	QNode *next;
}*QueuePtr;
struct LinkQueue
{
	QueuePtr front,rear; // 队头、队尾指针
};

void InitQueue(LinkQueue &Q)
{ // 构造一个空队列Q
	if(!(Q.front=Q.rear=new QNode)) exit(0);
	Q.front->next=NULL;
}
void EnQueue(LinkQueue &Q,int e)		//入队
{ // 插入元素e为Q的新的队尾元素
	QueuePtr p;
	if(!(p=new QNode)) exit(0);		// 存储分配失败
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
}
int DeQueue(LinkQueue &Q,int &e)	//出队
{ // 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR
	QueuePtr p;
	if(Q.front==Q.rear) return 0;
	p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p)
		Q.rear=Q.front;
	delete p;
	return 1;
}

void BFSTraverse(ALGraph G)
{   //按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。算法
	int v,u,w;
	ArcNode *p;
	LinkQueue Q;
	for(v=0;v<G.vexnum;++v) visited[v]=0;		// 置初值(未访问标志)
	InitQueue(Q);		// 置空的辅助队列Q
	cout<<"广度优先搜索的结果:\n";
	for(v=0;v<G.vexnum;v++) // 如果是连通图，只v=0就遍历全图
		if(!visited[v]) // v尚未访问
		{
			visited[v]=1;	//置已访问标志
			cout<<G.vertices[v].data<<'\t';
			EnQueue(Q,v);	// v入队列
			while(Q.front->next!=NULL) // 队列不空
			{
				DeQueue(Q,u); // 队头元素出队并置为u
				p=G.vertices[u].firstarc;
				while (p)
				{
					w=p->adjvex;
					if(!visited[w]) // w为u的尚未访问的邻接顶点
					{
						visited[w]=1;
						cout<<G.vertices[w].data<<'\t';
						EnQueue(Q,w); // w入队
					}
					p=p->nextarc;
				}
			}
			cout<<"\n";
		}
}

void main()
{
	ALGraph g;
	CreateGraph(g); // 创建无向图
	Display(g);		// 输出无向图
	DFSTraverse(g); // 调用算法7.4，有改动
	BFSTraverse(g); // 调用算法7.6，有改动
 }