4-4.c

《C程序员成长攻略》-黎陡-源代码-4282

#define MAX_VERTEX_NUM 20
typedef enum{FALSE,TRUE} Boolean;
/*自定义的真值和假值，其中FALSE实际值为0，而TRUE实际值为1*/
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;

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 DFS(MGraph *G,char v)  /*通过递归进行深度优先遍历*/
{ /*其中v为开始遍历的顶点*/
	int i,j;
    for(i=0;i<G->vexnum;i++)  /*首先确定当前要访问的顶点在图中的位置*/
        if(G->vexs[i]==v)
            break;
    printf("%5c",v); /*输出该结点，即表示访问该结点*/
    visited[i]=TRUE;  /*将该顶点的访问标识设为TRUE，表示已经访问过*/
	for(j=0;j<G->vexnum;j++)  /*然后依次来访问与该顶点邻接的顶点*/
        if(G->arcs[i][j].adj==1 && !visited[j])/*如果某顶点满足与该顶点相邻且未被访问过*/
			DFS(G,G->vexs[j]); /*则通过递归调用来访问这个邻接的顶点*/
}

main()
{
	int i;
	MGraph *G;
	clrscr();
	CreateAppMGraph(G);
	ShowAdjMatrix(G);
	printf("Visit vertex in DFSTraverse: ");
	DFS(G,'A');/*从顶点'A'开始遍历，输出遍历的顶点序列*/
	getch();
}