图的广度优先遍历.cpp

能够输入节点 然后完成图的广度优先遍历

#include<stdio.h>
#include<malloc.h>
#define NULL 0
#define MAX_VERTEX_NUM 20
typedef enum{D,U}kind;
typedef struct ArcNode
{
   int adjvex;     //该弧指向的顶点的位置
   struct ArcNode *nextarc;    //指向下一条弧的指针
   int  *info;    //该弧相关信息的指针
}ArcNode;
typedef struct VNode
{
	char data;   //顶点信息
	ArcNode *firstarc;   //指向第一条依附于该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct 
{
	AdjList vertices;
	int vexnum,arcnum;  //图的当前顶点数和弧数
    int kind;    //图的种类标志
}ALGraph;
typedef struct QNode
{
	char data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
    QueuePtr front;
	QueuePtr rear;
}LinkQueue;
int visited[MAX_VERTEX_NUM];
int vexnum,arcnum;
void CreateDG(ALGraph &G)    //采用邻接表存储表示，构造有向图
{
	ArcNode *p;
	printf("请输入当前图的顶点数！\n");
    scanf("%d",&G.vexnum);
	fflush(stdin);
    printf("请输入当前图的弧数！\n");
	scanf("%d",&G.arcnum);
	fflush(stdin);
	for(int i=0;i<G.vexnum;i++)
   {  
	   printf("请输入顶点\n");
	   scanf("%c",&G.vertices[i].data);
	   fflush(stdin);
	   G.vertices[i].firstarc=NULL;
   }
	for(int k=0;k<G.arcnum;++k)
    {
	   int i,j;
	   printf("请输入弧的信息!\n");
	   scanf("%d,%d",&i,&j);
	   p=(ArcNode*)malloc (sizeof(ArcNode));
	   p->adjvex=j;p->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p;
    }
}
int FirstAdjVex(ALGraph &G,int v)
{
	if(G.vertices[v].firstarc) 
	{
		return G.vertices[v].firstarc->adjvex;
	}
	else 
	{
		return -1;
	}
}
int NextAdjVex(ALGraph &G,int v,int w)
{
	w=G.vertices[v].firstarc->adjvex;
	if(G.vertices[w].firstarc) 
	{
		return G.vertices[w].firstarc->nextarc->adjvex;
	}
	else
	{
		return -1;
	}
}
void InitQueue(LinkQueue &Q)
{
	Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
	if(!Q.front)printf("分配空间失败!\n");
    else Q.front->next =NULL;
}
void EnQueue(LinkQueue &Q,char e)
{
	QNOde *p;
	p=(QueuePtr)malloc(sizeof(QNode));
    if(!p)printf("分配空间失败!\n");
	else
	{
		p->data=e;
		p->next=NULL;
		Q.rear->next = p;
		Q.rear = p;
	}
}
void DeQueue(LinkQueue &Q,char e)
{
	QNode *p;
	if(Q.front==Q.rear)printf("错误信息！\n");
	else
	{
		p=Q.front->next;
		e=p->data;
		Q.front->next = p->next;
		if(Q.rear == p)Q.rear=Q.front;
		free(p);
	}
}
void BFSTraverse(ALGraph &G)
{
	
	for(int v=0;v<G.vexnum;++v)
	{
		visited[v]=0;
	}
	InitQueue(Q);
    for(v=0;v<G.vexnum;++v)
	{	
		if(visited[v]==0) 
		{
			visited[v]=1;
			printf("%c\n",G.vertices[v].data);
			EnQueue(Q,G.vertices[v].data);
			while(!QueueEmpty(Q))
			{
			    int u;
				DeQueue(Q,G.vertices[u].data);
				int w;
				for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
				{
					if(visited[w]==0)
					{
						visited[w]=1;
			            printf("%c\n",G.vertices[w].data);
						EnQueue(Q,G.vertices[w].data);
					}
				}
			}
		}
	}
}
void main()
{
	ALGraph S;
	printf("您创建的图是有向图\n");
    printf("进行广度优先探索:\n");
	printf("广度遍历结点为\n");
	DFSTraverse(S);
	printf("\n");

	

}