圖---鄰接矩陣(建立，深度周遊，廣度周遊)

    圖的存儲方式可以用鄰接矩陣來表示，我們假定頂點序号從0開始，即圖G的頂點集的一般形式是V(G)={v0 ，vi ，…，Vn-1 }。

以下代碼測試過，為圖的鄰接矩陣表示方式。

/************************************************************************/

/* 圖的鄰接矩陣存儲結構 */

/************************************************************************/

#include <stdio.h>

#define MaxVertexNum 100

#define QueueSize 30

typedef enum{FALSE,TRUE}Boolean;

Boolean visited[MaxVertexNum];

typedef char VertexType;

typedef int EdgeType;

typedef struct

{

VertexType vexs[MaxVertexNum]; //頂點表

EdgeType edges[MaxVertexNum][MaxVertexNum]; //鄰接矩陣,可看做邊表

int n,e; //圖中目前的頂點數和邊數

}MGraph;

/************************************************************************/

/* 鄰接矩陣的建立 */

/************************************************************************/

void CreateMGraph(MGraph *G)

{

int i,j,k;

char ch1,ch2;

printf("請輸入頂點數和邊數(輸入格式為:頂點數,邊數):/n");

scanf("%d,%d",&(G->n),&(G->e));

printf("請輸入頂點資訊(頂點号<CR>)每個頂點以回車作為結束:/n");

for(i=0;i<G->n;i++)

{

getchar();scanf("%c",&(G->vexs[i]));

}

for(i=0;i<G->n;i++)

for(j=0;j<G->n;j++)

G->edges[i][j]=0;

printf("請輸入每條邊對應的兩個頂點的序号(輸入格式為:i,j):/n");

for(k=0;k<G->e;k++)

{

getchar();

printf("請輸入第%d條邊的頂點序号：",k+1);

scanf("%c,%c",&ch1,&ch2);

for(i=0;ch1!=G->vexs[i];i++);

for(j=0;ch2!=G->vexs[j];j++);

G->edges[i][j]=1;

}

}

/************************************************************************/

/* 深度優先周遊（深度優先搜尋） */

/************************************************************************/

void DFSM(MGraph *G,int i)

{

int j;

printf("深度優先周遊結點: 結點%c/n",G->vexs[i]); //通路頂點vi

visited[i]=TRUE;

for(j=0;j<G->n;j++) //依次搜尋vi鄰接點

if(G->edges[i][j]==1 && !visited[j])

DFSM(G,j);

}

void DFSTraverseM(MGraph *G)

{

int i;

for(i=0;i<G->n;i++)

visited[i]=FALSE;

for(i=0;i<G->n;i++)

if(!visited[i])

DFSM(G,i);

}

/************************************************************************/

/* 廣度優先周遊（廣度優先搜尋） */

/************************************************************************/

typedef struct

{

int front;

int rear;

int count;

int data[QueueSize];

}CirQueue;

void InitQueue(CirQueue *Q)

{

Q->front=Q->rear=0;

Q->count=0;

}

int QueueEmpty(CirQueue *Q)

{

return Q->count=QueueSize;

}

int QueueFull(CirQueue *Q)

{

return Q->count==QueueSize;

}

void EnQueue(CirQueue *Q,int x)

{

if (QueueFull(Q))

printf("Queue overflow");

else

{

Q->count++;

Q->data[Q->rear]=x;

Q->rear=(Q->rear+1)%QueueSize;

}

}

int DeQueue(CirQueue *Q)

{

int temp;

if(QueueEmpty(Q))

{

printf("Queue underflow");

return NULL;

}

else

{

temp=Q->data[Q->front];

Q->count--;

Q->front=(Q->front+1)%QueueSize;

return temp;

}

}

void BFSM(MGraph *G,int k)

{

int i,j;

CirQueue Q;

InitQueue(&Q);

printf("廣度優先周遊結點: 結點%c/n",G->vexs[k]);

visited[k]=TRUE;

EnQueue(&Q,k);

while (!QueueEmpty(&Q))

{

i=DeQueue(&Q);

for (j=0;j<G->n;j++)

if(G->edges[i][j]==1&&!visited[j])

{

printf("廣度優先周遊結點:%c/n",G->vexs[j]);

visited[j]=TRUE;

EnQueue(&Q,j);

}

}

}

void BFSTraverseM(MGraph *G)

{

int i;

for (i=0;i<G->n;i++)

visited[i]=FALSE;

for (i=0;i<G->n;i++)

if (!visited[i])

BFSM(G,i);

}

/************************************************************************/

/* 主函數調用 */

/************************************************************************/

int main()

{

MGraph G;

CreateMGraph(&G);

DFSTraverseM(&G);

BFSTraverseM(&G);

return 0;

}

測試結構如下（含測試資料）：