graph.cpp

实现无向图(或有向图)的存储表示,并输出对该图的广度优先（或深度优先）遍历。 系统具备如下的功能： 1．初始化。从键盘输入图的顶点数与边数。 2．输出图的相应的存储表示。 3．输出图的广度优

// Graph.cpp: implementation of the CGraph class.
//
//////////////////////////////////////////////////////////////////////

#include "Graph.h"
#include "stdafx.h"
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CGraph::CGraph()
{

}

CGraph::~CGraph()
{

}
int CGraph::CreateDG(ALGraph &G)
{
	int IncInfo,i,j,k,v1,v2;//,w;
	InfoType info;
	ArcNode *p;
    printf("\nPlease input the number of G.vexnum (eg. G.vexnum=4): ");
	scanf("%d",&G.vexnum);		//输入图中的结点值
	printf("Please input the number of G.arcnum (eg. G.arcnum=4): ");
	scanf("%d",&G.arcnum);		//输入弧的个数
	printf("Please input the number of IncInfo (0 for none) : ");
	scanf("%d",&IncInfo);
	for(i=0;i<G.vexnum;++i)	//initial G.vertices
	{  
		G.vertices[i].data=i;
	    G.vertices[i].firstarc=NULL;
	}
	info=0;
	for(k=0;k<G.arcnum;++k)	//input arc(v1,v2)
	{  
		if(IncInfo==0)
		{
		    printf("\nPlease input the %dth arc(v1,v2): ",k+1);
	        scanf("%d,%d",&v1,&v2);
	        i=v1;
	        j=v2;
		}
		else
		{
		    printf("\nPlease input the %dth arc(v1,v2,info): ",k+1);
	        scanf("%d,%d,%d",&v1,&v2,&info);
	        i=v1;
	        j=v2;
		}

		while(i<1||i>G.vexnum||j<1||j>G.vexnum)	//if (v1,v2) illegal,again
		{  
			if(IncInfo==0)
			{
				printf("\nPlease input the %dth arc(v1,v2): ",k+1);//输入具体的弧的位置
				scanf("%d,%d",&v1,&v2);
				i=v1;
				j=v2;
			}
			else
			{
				printf("\nPlease input the %dth arc(v1,v2,info): ",k+1);
				scanf("%d,%d,%d",&v1,&v2,&info);
				i=v1;
				j=v2;
			}
		} //while end
		i--;
		j--;
		p=(ArcNode *)malloc(sizeof(ArcNode));	//allocate memory
		if(!p)
		{  
			printf("\nOverflow!");		//if overflow
			return (0);
		}
		p->adjvex=j;			//assign p
		p->nextarc=G.vertices[i].firstarc;
		p->info=info;
		G.vertices[i].firstarc=p;
		p=(ArcNode *)malloc(sizeof(ArcNode));	//allocate memory
		if(!p)
		{  
			printf("\nOverflow!");		//if overflow
			return (0);
		}
		p->adjvex=i;			//assign p
		p->nextarc=G.vertices[j].firstarc;
		p->info=info;
		G.vertices[j].firstarc=p;
	} //for end
	   return (OK);
} //构造一个图


void CGraph::DFS(ALGraph G, int v, int *visited)	//DFS() sub-fuction
{  
	ArcNode *p;
	visited[v]=1;
	printf("%d ",G.vertices[v].data+1);
    p=G.vertices[v].firstarc;
	while(p)
	{
		if(visited[p->adjvex]==0)
		{
			printf("->");
			DFS(G,p->adjvex,visited);		//对尚未访问的顶点调用 DFS()函数
		}
		p=p->nextarc;
	}
} //DFS() end



void CGraph::DFSTraverse(ALGraph G)//DFSTraverse() sub-function
{  
	int v;
    int visited[MAX_VERTEX_NUM];
    for(v=0;v<G.vexnum;++v)
		visited[v]=0;		//initial visited[v]
	printf("\n深度优先遍历序:");
    for(v=0;v<G.vexnum;++v)
		if(visited[v]==0)
		{
			printf("\n");
	        DFS(G,v,visited);	//从第v个顶点出发递归地深度遍历图G
		}
} //深度优先遍历图
void CGraph::dispGriph(ALGraph G)
{
	int  k;
	ArcNode *arc;
	printf("\nthis Graph is as follow: ");
	printf("\nvex num:  %",G.vexnum);		//out the number of vex
	printf("\narc num:  %",G.arcnum);		//out the number of arc

	for(k=0;k<G.arcnum;++k)	//input arc(v1,v2)
	{  
		printf("\nvex:%d",G.vertices[k].data+1);
		arc=G.vertices[k].firstarc;
		while(arc)
		{
			printf("->%d",arc->adjvex+1);
			arc=arc->nextarc;
		}

	}
}//----------图的邻接矩阵存储表示---------------

void CGraph::BFSTraverse(ALGraph G)//BFSTraverse() sub-function
{  
	int v,u;
	int visited[MAX_VERTEX_NUM];
	SqQueue Q;   //构造辅助队列
	ArcNode *p;

	for(v=0;v<G.vexnum;++v)
		visited[v]=0;		//initial visited[]
	InitQueue(Q);		//call InitQueue()
	printf("\n广度优先遍历序:");
	for(v=0;v<G.vexnum;++v)
		if(visited[v]==0)
		{  
			visited[v]=1;
			printf("\n%d",v+1);
			EnQueue(Q,v);			//v入队列
			while(!QueueEmpty(Q))
			{    
				DeQueue(Q,u);	//对头元素出队列并置为u
				p=G.vertices[u].firstarc;
				while(p)
				{
					if(visited[p->adjvex]==0)
					{  
						visited[p->adjvex]=1;
					    printf("->%d",p->adjvex+1);
					    EnQueue(Q,p->adjvex); 	//call EnQueue()
					} //if end
					p=p->nextarc;
				}
			} //while end
		} //if end
} //广度优先遍历图

int CGraph::QueueEmpty(SqQueue Q)//InitQueue() sub-function
{   
	Q.base=(QElemType *)malloc(MAX_VERTEX_NUM*sizeof(QElemType));
    if(!Q.base)			//allocate memory
    {   
		printf("\nOverflow ! ");	//if overflow
		return 0;
    }
    Q.front=Q.rear=0;		//assign Q.front=Q.rear=0
    return (OK);
} //InitQueue() end

int CGraph::EnQueue(SqQueue &Q, QElemType e)	//EnQueue() sub-function
{   
	if((Q.rear+1)%MAX_VERTEX_NUM==Q.front)	//if full
    {   
		printf("Error ! The SqQeueu is full ! ");//建一个空队列
	    return 0;
    }
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAX_VERTEX_NUM;
    return (OK);
} //插入元素到对尾



int CGraph::DeQueue(SqQueue &Q, QElemType &e)	//DeQueue() sub-function
{  
	if(Q.front==Q.rear)		//empty queue
    {
		cout<<endl<<"Errer !  It's empty!";
	    return 0;
    }
    e=Q.base[Q.front];
    Q.front=(Q.front+1)%MAX_VERTEX_NUM;
    return (e);
} //DeQueue() end删除对头元素

int CGraph::InitQueue(SqQueue &Q)//InitQueue() sub-function
{//构造一个空队列
   Q.base=(QElemType *)malloc(MAX_VERTEX_NUM*sizeof(QElemType));
    if(!Q.base)			//allocate memory
    {   
		printf("\nOverflow ! ");	//if overflow
		return 0;
    }
    Q.front=Q.rear=0;		//assign Q.front=Q.rear=0
    return (OK);
} //InitQueue() end