bfs.cpp

VC++实现广度优先遍历

// BFS.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#define OK 1
#define MAX_VERTEX_NUM  20  
#define TRUE 1
#define FALSE 0

typedef struct ArcCell
{ 
     int  adj;  
} ArcCell, AdjMatrix [MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{                      
	char vexs[MAX_VERTEX_NUM]; 
	int visited[MAX_VERTEX_NUM];
	AdjMatrix  arcs;                   
	int  vexnum, arcnum;          
} MGraph;
MGraph G1;
typedef struct 
{ 
	int queue[MAX_VERTEX_NUM];
	int  front ,rear;
}sequeuetp;
sequeuetp Q1;
int InitQueue(sequeuetp &Q)
{
	Q.front = Q.rear = 0;
	return OK;
}
int Enqueue(sequeuetp  &Q, int e)
{ 
	if (Q.rear==MAX_VERTEX_NUM)
		return  FALSE;            //队列已满
	else
	{
		Q.queue[Q.rear] = e;
		Q.rear++;                      
		return  OK;
	}
}
int Delqueue(sequeuetp  &Q, int &e)
 { 
	if (Q.front == Q.rear)
		return  (NULL);          //队列空
	else 
	{
		e = Q.queue[Q.front];
		Q.front++;                      
		return  OK;
	}
}
int QueueEmpty(sequeuetp &Q)
{
	if (Q.front == Q.rear)
		return TRUE;
	else 
		return FALSE;
}
int LocateVex(MGraph G, char v)
{
	int i = 0,j =0;
	for(i = 0;i < G.vexnum;++i)
		if(G.vexs[i] == v)
			j = i;
	return j;
}
int Creat(MGraph &G)
{
	int i = 0,j = 0,k = 0,w = 0;
	char v1,v2;
	printf("请输入(连通)图的相关信息:(当前顶点数，弧数)\n");
	scanf("%d,%d",&G.vexnum,&G.arcnum);
	fflush(stdin);
	printf("请输入图中包含的所有结点:\n");
	for(i = 0;i < G.vexnum;i++)
	{
		scanf("%c",&G.vexs[i]);
		fflush(stdin);
		G.visited[i] = 0;
	}
    for(i = 0;i < G.vexnum;++i)
		for(j = 0;j < G.vexnum;++j)
			G.arcs[i][j].adj= 0;
	printf("请输入各弧:(顶点v1,顶点v2,权值w,无权图输入1)\n");
    for(k = 0;k < G.arcnum;++k)
	{
		scanf("%c,%c,%d",&v1,&v2,&w);
		fflush(stdin);
		i = LocateVex(G,v1);
		j = LocateVex(G,v2);
		G.arcs[i][j].adj = w;
		G.arcs[j][i]=G.arcs[i][j];
	}
	return OK;
}
void visit(char v)
{
	printf("%4c",v);
}
int FirstAdjVex(MGraph G,int e)
{
	int i = 0;
	while(G.arcs[e][i].adj == 0 && G.visited[i] ==0 && i < G.vexnum)
		i++;
	return i;
}
int NextAdjVex(MGraph G,int e,int f)
{
	int i = f;
	while(G.arcs[e][i].adj == 0 && G.visited[i] ==0 && i < G.vexnum)
		i++;
    return i;
}
void BFSTraverse(MGraph G,char v)
{
	int i = 0,j = 0,k = 0;
	i = LocateVex(G,v);
	printf("BFS遍历结果为:\n");
	InitQueue(Q1);                 // 置空的辅助队列Q
    for (i = 0;i < G.vexnum;++i )
		if (!G.visited[i])// v 尚未访问  
		{          
			G.visited[i] = TRUE;  
			visit(G.vexs[i]);    // 访问v
			Enqueue(Q1, i);  // v入队列
			while (!QueueEmpty(Q1))//循环结束时访问整个连通子图
			{
				Delqueue(Q1,j);              // 队头元素出队并置为u
				for(k = FirstAdjVex(G,j);k != 0;k = NextAdjVex(G,j,k))
					if (!G.visited[k]) 
					{
						G.visited[k] = TRUE;
						visit(G.vexs[k]);
						Enqueue(Q1,k);         // 访问的顶点w入队列
					} // if
			} // while
		} 
} // BFSTraverse

int main(int argc, char* argv[])
{
	char v1;
	Creat(G1);
	printf("请输入BFS遍历起始结点:\n");
	scanf("%c",&v1);
	fflush(stdin);
	BFSTraverse(G1,v1);
	printf("\n");
	return 0;
}