/*
	图的构建及其广度优先搜索
*/
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 30

typedef int VrType;
typedef char VtType;
bool visted[MAX_VERTEX_NUM];		//搜索时的标记矩阵

typedef struct ARC					//用于表征图的连接关系
{
	VrType adj;						//连接关系
	ARC *info;						//附加信息
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct						//定义图的完整结构
{
	VtType vertex[MAX_VERTEX_NUM];	//顶点		
	AdjMatrix arcs;					//邻接矩阵
	int vertexnum,arcnum;			//弧线和顶点的数目
}MGraph;

typedef struct node					//FIFO链表（队列）
{
	int vid;
	struct node* next;
}Queue;

Queue* head=NULL; 

void CreateG(MGraph &G)				//创建图
{
	int i,j;

	printf("Construct the Graph...\n");
	G.vertexnum=8;
	G.arcnum=9;

	for(i=0;i<MAX_VERTEX_NUM;i++)	//邻接矩阵的初始化
	{
		for(j=0;j<MAX_VERTEX_NUM;j++)
		{
			G.arcs[i][j].adj=0;
			G.arcs[i][j].info=NULL;
		}
	}

	G.vertex[0]=‘a‘;				//顶点赋值
	G.vertex[1]=‘b‘;
	G.vertex[2]=‘c‘;
	G.vertex[3]=‘d‘;
	G.vertex[4]=‘e‘;
	G.vertex[5]=‘f‘;
	G.vertex[6]=‘g‘;
	G.vertex[7]=‘h‘;

	G.arcs[0][1].adj=1;				//邻接矩阵赋值
	G.arcs[0][1].info=NULL;
	G.arcs[1][0].adj=1;
	G.arcs[1][0].info=NULL;

	G.arcs[1][3].adj=1;
	G.arcs[1][3].info=NULL;
	G.arcs[3][1].adj=1;
	G.arcs[3][1].info=NULL;

	G.arcs[3][7].adj=1;
	G.arcs[3][7].info=NULL;
	G.arcs[7][3].adj=1;
	G.arcs[7][3].info=NULL;

	G.arcs[4][7].adj=1;
	G.arcs[4][7].info=NULL;
	G.arcs[7][4].adj=1;
	G.arcs[7][4].info=NULL;

	G.arcs[4][1].adj=1;
	G.arcs[4][1].info=NULL;
	G.arcs[1][4].adj=1;
	G.arcs[1][4].info=NULL;

	G.arcs[0][2].adj=1;
	G.arcs[0][2].info=NULL;
	G.arcs[2][0].adj=1;
	G.arcs[2][0].info=NULL;

	G.arcs[2][5].adj=1;
	G.arcs[2][5].info=NULL;
	G.arcs[5][2].adj=1;
	G.arcs[5][2].info=NULL;

	G.arcs[2][6].adj=1;
	G.arcs[2][6].info=NULL;
	G.arcs[6][2].adj=1;
	G.arcs[6][2].info=NULL;

	G.arcs[5][6].adj=1;
	G.arcs[5][6].info=NULL;
	G.arcs[6][5].adj=1;
	G.arcs[6][5].info=NULL;

	printf("Construction of Graph OK!\n\n");
	return;
}

void ShowAdjMat(MGraph G)			//邻接矩阵的显示
{
	int i,j;

	printf("The adjacent matrix is:\n");
	for(i=0;i<G.vertexnum;i++)
	{
		for(j=0;j<G.vertexnum;j++)
		{
			printf("%d ",G.arcs[i][j].adj);
		}
		printf("\n");
	}
	printf("\n");

	return;
}

void addnode(Queue* head,int v)		//链表添加新节点
{
	Queue* temp,*newnode;

	if(head==NULL)
	{
		head=(Queue*)malloc(sizeof(Queue));
		head->next=NULL;
		head->vid=v;
	}
	else
	{
		temp=head;
		while(temp->next!=NULL)
		{
			temp=temp->next;
		}
		newnode=(Queue*)malloc(sizeof(Queue));
		newnode->next=NULL;
		newnode->vid=v;
	}
	return;
}

int GetNextVid(Queue* head)			//链表中获取下一结点，删除出队结点
{
	Queue* temp;
	int id;
	while(1)
	{
		if(head!=NULL)
		{
			id=head->vid;
			temp=head;
			head=head->next;
			free(temp);
		}
		else
		{
			break;
		}
		if(visted[id]!=true)
		{
			break;
		}
	}

	return id;
}

void BFS(MGraph G,int v)			//广度优先遍历
{
	int i;
	int nextvid;

	printf("%c ",G.vertex[v]);
	visted[v]=true;
	addnode(head,v);
	while(head!=NULL)
	{
		for(i=0;i<G.vertexnum;i++)
		{
			if(G.arcs[v][i].adj==1 && visted[i]!=true)
			{
				BFS(G,i);
			}
		}
		nextvid=GetNextVid(head);		
		BFS(G,nextvid);	
	}
	return;
}

void BFSTraverse(MGraph G)			//广度优先搜索
{
	int i;

	printf("The depth first traverse result is:\n");
	for(i=0;i<G.vertexnum;i++)
	{
		visted[i]=false;
	}

	for(i=0;i<G.vertexnum;i++)
	{
		if(visted[i]!=true)
		{
			BFS(G,i);
		}
	}
}

int main(void)
{
	MGraph G;

	CreateG(G);
	ShowAdjMat(G);
	BFSTraverse(G);

	printf("\n\n");
	system("pause");
	return 0;
}