学步园

和深搜不同，广搜在访问一个节点之后会访问这个节点周围的所有节点

然后扩散出去：

这里要用到队列，所以把先前的队列代码直接拿来就用。。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define number 20

typedef int QElemType;
typedef int Status;
typedef struct node
{
	int info;		//图的节点存放的信息，可随时变动
}GraphNode;
typedef struct
{
	GraphNode matrix[number+1][number+1];		//构造邻接矩阵
	int vexs[number+1];							//顶点向量
	int vertex,edge;							//顶点个数、弧个数
}Graph;

//构造队列的数据结构
typedef struct QNode
{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;
typedef struct  
{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;



//队列基本操作
Status InitQueue(LinkQueue *Q);
Status DestroyQueue(LinkQueue *Q);
Status ClearQueue(LinkQueue *Q);
Status QueueEmpty(LinkQueue *Q);
Status QueueLength(LinkQueue *Q);
Status GetHead(LinkQueue *Q);
Status EnQueue(LinkQueue *Q,QElemType data);
Status DeQueue(LinkQueue *Q);
Status QueueTraverse(LinkQueue *Q);

int visited[number+1];

Status InitQueue(LinkQueue *Q)
{
	Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
	if(! Q->front)exit(1);
	Q->front->next = NULL;
	return 1;
}

Status DestroyQueue(LinkQueue *Q)
{
	while(Q->front)
	{
		Q->rear = Q->front->next;
		free(Q->front);
		Q->front = Q->rear;
	}

	return 1;
}

Status ClearQueue(LinkQueue *Q)
{
	Q->front = Q->rear = NULL;

	return 1;
}

Status QueueEmpty(LinkQueue *Q)
{
	return ((Q->front == Q->rear)? 1:0);
}

Status QueueLength(LinkQueue *Q)
{
	int flag=0;
	QueuePtr temp = Q->front;
	while(temp->next)
	{
		Q->rear = temp->next;
		flag++;
		temp = Q->rear;
	}

	return flag;
}

Status GetHead(LinkQueue *Q)
{
	if(Q->front == Q->rear)
	{
		printf("Queue Handle Error.\n");
		exit(1);
	}
	return Q->front->next->data;
}

Status EnQueue(LinkQueue *Q,QElemType data)
{
	QueuePtr tmp;
	tmp = (QueuePtr)malloc(sizeof(QNode));
	tmp->data = data;
	tmp->next = NULL;

	Q->rear->next = tmp;
	Q->rear = tmp;
	return 1;
}

Status DeQueue(LinkQueue *Q)
{
	QueuePtr temp;
	if (Q->front == Q->rear)
	{
		printf("error.\n");
		return 0;
	}

	temp = Q->front->next;
	Q->front->next = temp->next;
	if(Q->rear == temp)Q->rear = Q->front;		//如果删除的是队列最后一个元素，要将队尾指针重新赋值
	free(temp);
	return 1;

}
//创建图
void CreatGraph(Graph *G)
{
	int i,k;
	int x,y,data;
	int vertex,edge;
	printf("输入图的顶点个数和边的个数.\n");
	scanf("%d%d",&vertex,&edge);
	G->vertex = vertex;G->edge = edge;
	printf("输入图的每个顶点.\n");
	for(i=1;i<=vertex;i++)
		scanf("%d",&G->vexs[i]);
	for(i=1;i<=vertex;i++)
		for(k=1;k<=vertex;k++)
			G->matrix[i][k].info = 0;

	printf("请输入 %d 条边的横坐标、纵坐标、数值.\n",edge);
	for(i=1;i<=edge;i++)
	{
		scanf("%d%d%d",&x,&y,&data);
		G->matrix[x][y].info=data;
		G->matrix[y][x].info=data;
	}
}

//找出给定顶点的位置
int LocateVex(Graph *G,int V)
{
	int i;
	for(i=1;i<=G->vertex;i++)
		if(G->vexs[i] == V)
			return i;
	return -1;						//失败返回-1
}

//将指定顶点的数值改变
void PutVex(Graph *G,int V,int value)
{
	int temp;
	if((temp =LocateVex(G,V)) == -1)return;
	else G->vexs[temp] = value;
}


//向图中插入一个顶点
int InsertVex(Graph *G,int V)
{
	int i;
	G->vertex++;
	if(G->vertex > number)return 0;
	G->vexs[G->vertex] = V;
	for(i=1;i<=G->vertex;i++)
		G->matrix[G->vertex][i].info = 0;
	for(i=1;i<G->vertex;i++)
		G->matrix[i][G->vertex].info = 0;
	return 1;
}

//在图中删除一个顶点
int DeleteVex(Graph *G,int V)
{
	int i,temp,k;
	int count=0;
	if((temp=LocateVex(G,V)) == -1)return -1;

	//顶点数组变化
	for(i=temp;i<G->vertex;i++)
		G->vexs[i] = G->vexs[i+1];
	//顶点入度变化
	for(i=1;i<=G->vertex;i++)
	{
		if(G->matrix[i][temp].info)count++;
		for(k=temp;k<G->vertex;k++)
		{
			G->matrix[i][k].info=G->matrix[i][k+1].info;
		}
	}
	//顶点出度变化
	for(i=1;i<G->vertex;i++)
	{
		for(k=temp;k<G->vertex;k++)
			G->matrix[k][i].info = G->matrix[k+1][i].info;
	}
	G->vertex--;		//顶点减一
	G->edge -= count;	//弧减去对应的个数
	return 1;
}

//在图中插入一条弧
int InsertArc(Graph *G,int v,int w)
{
	int digit;
	if(v<0||v> G->vertex||w<0||w>G->vertex)return -1;
	printf("输入弧的权值.\n");
	scanf("%d",&digit);
	G->matrix[v][w].info = G->matrix[w][v].info  = digit;
	return 1;
}

//在图中删除一条弧
int DeleteArc(Graph *G,int v,int w)
{
	if(v<0||v> G->vertex||w<0||w>G->vertex)return -1;
	G->matrix[v][w].info = G->matrix[w][v].info  = 0;
	return 1;
}

//打印图
void DisplayGraph(Graph *G)
{
	int i,k;
	for(i=1;i<=G->vertex;i++)
	{
		for(k=1;k<=G->vertex;k++)
			printf("%-4d ",G->matrix[i][k].info);
		printf("\n");
	}
	printf("\n");
}


void RecoverGraph(Graph *G)
{
	int i,k;
	for(i=1;i<=G->vertex;i++)
		for(k=1;k<=G->vertex;k++)
			G->matrix[i][k].info=0;
	memset(G->vexs,0,sizeof(G->vexs));
	G->vertex = G->edge = 0;
	
}

//找出指定顶点在图中的第一个邻接点
int FirstAdjVex(Graph *G,int V)
{
	int temp,i;
	if((temp = LocateVex(G,V))==-1) return -1;	//失败返回-1
	else
	{
		for(i=1;i<=G->vertex;i++)
			if(G->matrix[temp][i].info != 0)
				return i;
	}
	return -1;
}

int NextAdjVertex(Graph *G,int v,int w)
{
	int temp,i;
	if((temp=LocateVex(G,v)) == -1)return -1;

	for(i=w+1;i<=G->vertex;i++)
		if(G->matrix[temp][i].info)return i;
	
	return -1;
}

void BFS(Graph *G)
{
	int v,w;
	LinkQueue queue;
	InitQueue(&queue);		//初始化队列
	//构造辅助数组
	for(v=1;v<=G->vertex;v++)
		visited[v] = 0;

	for(v=1;v<=G->vertex;v++)
	{
		if(!visited[v])		//顶点v尚未访问
		{
			visited[v]=1;printf("%d ",G->vexs[v]);	//访问之
			EnQueue(&queue,v);		//进入队列
			while(QueueEmpty(&queue)!=1)
			{
				DeQueue(&queue);
				//寻找节点的所有邻接节点
				for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVertex(G,v,w))		
					if(!visited[w])
					{
						visited[w]=1;printf("%d ",G->vexs[w]);
						EnQueue(&queue,w);
					}	//if
			}//while
		}//if
	}//for
}

int main()
{
	Graph G;
	CreatGraph(&G);
	BFS(&G);
	RecoverGraph(&G);
	return 0;
}