4-5.c

《C程序员成长攻略》-黎陡-源代码-4282 中国水利水电出版社 程序员成长之路丛书

#include"stdio.h"
#define MAX_VERTEX_NUM 20
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MAX_VERTEX_NUM];
typedef struct ArcCell{
	int adj;
	char *info;
}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct {
    char vexs[MAX_VERTEX_NUM];
    AdjMatrix arcs;
    int vexnum,arcnum;
}MGraph;

int Q[MAX_VERTEX_NUM]; /*队列数组*/
int tail; /*指示队尾的变量*/

void InitQueue() /*初始化队列*/
{
	int i;
    tail=-1;  /*队尾变量初始化为-1，表示队列为空*/
    for(i=0;i<MAX_VERTEX_NUM;i++)
        Q[i]=-1; /*数组各元素值先置为-1*/
}

void EnQueue(int v) /*进队操作*/
{
    Q[++tail]=v; /*将新成员添加到队列尾端*/
}

int DeQueue()  /*出队操作*/
{
    int i,v;
    v=Q[0];   /*首先获得队列头结点的值*/
    for(i=0;i<tail;i++) /*然后将随后的队列各结点依次往前移一个位置*/
        Q[i]=Q[i+1];
    Q[tail--]=-1; /*原本队列尾端的位置此时要置-1，表示此位置为空。且队尾指示变量值减1*/
    return v; /*函数返回队头元素值*/
}

Boolean QueueEmpty() /*判断队列是否为空*/
{
    if(tail==-1)    /*如果tail为-1，则表示队空，否则队列不为空*/
        return TRUE;  /*利用程序自定义的FASLE和TRUE值，使函数返回1或0值*/
    return  FALSE;
}

void CreateAppMGraph(MGraph *G) /*同样采用直接赋值的方法来创建指定图*/
{
	int i,j;
    G->vexnum=8;
    G->arcnum=9;
	for(i=0;i<G->vexnum;i++)
        G->vexs[i]='A'+i;
	for(i=0;i<G->arcnum;i++)
	  for(j=0;j<G->vexnum;j++)
        G->arcs[i][j].adj=0;
    G->arcs[0][1].adj=G->arcs[1][0].adj=1;
    G->arcs[0][2].adj=G->arcs[2][0].adj=1;
    G->arcs[1][3].adj=G->arcs[3][1].adj=1;
    G->arcs[1][4].adj=G->arcs[4][1].adj=1;
    G->arcs[3][7].adj=G->arcs[7][3].adj=1;
    G->arcs[4][7].adj=G->arcs[7][4].adj=1;
	G->arcs[2][5].adj=G->arcs[5][2].adj=1;
	G->arcs[2][6].adj=G->arcs[6][2].adj=1;
	G->arcs[5][6].adj=G->arcs[6][5].adj=1;
}

void ShowAdjMatrix(MGraph *G)
{
	int i,j;
	for(i=0;i<G->vexnum;i++)
	{ 
		printf("%5c  |",G->vexs[i]);
		for(j=0;j<G->vexnum;j++)
			printf("%5d",G->arcs[i][j].adj);
		printf("\n\n");
	}
}

void BFS(MGraph *G,char v)/*按广度优先非递归遍历图*/
{ /*从顶点v开始*/
	int i,j,k;
    InitQueue(Q);  /*队列初始化*/
    for(k=0;k<G->vexnum;k++)
        if(G->vexs[k]==v)
            break;  /*找到v在图中的位置，即为k*/
    printf("%5c",G->vexs[k]); /*首先访问v这个顶点*/
    visited[k]=TRUE;  /*置v的访问标识为TRUE*/
    EnQueue(k);   /*顶点v入队列*/
    while(!QueueEmpty())  /*队列不空，则循环*/
	{
        i=DeQueue(); /*队头顶点出队列，并将该顶点的位置赋给变量i*/
        for(j=0;j<G->vexnum;j++)
        if(G->arcs[i][j].adj==1 && !visited[j])
        {/*找到与该队头顶点邻接且未访问过的顶点*/
	        printf("%5c",G->vexs[j]); /*访问这个顶点*/
	        visited[j]=TRUE;  /*相应标识置为TRUE*/
            EnQueue(j);  /*将这个顶点入队列*/
        }
	}
}

main()
{
	int i;
    MGraph *G;
	clrscr();
	CreateAppMGraph(G);
	ShowAdjMatrix(G); 
	printf("Visit vertex in BFSTraverse: ");
	BFS(G,'A');
	getch();
}