邻接矩阵实现图的遍历

#include<stdio.h>
#include<stdlib.h>
#define GRAPHMAX 20
#define FALSE 0
#define TRUE 1
#define QueueSize 30
typedef struct {
char vexs[GRAPHMAX];
int adj[GRAPHMAX][GRAPHMAX];
int n,e;
}MGraph;
int visited[10];
typedef struct
{
int front,rear,count;
int data[QueueSize];
}LinkQueue;
void InitQueue(LinkQueue *Q)
{
Q->front=Q->rear=0;
Q->count=0;
}
int QueueEmpty(LinkQueue *Q) {
return Q->count=QueueSize;
}
int QueueFull(LinkQueue *Q)
{
return Q->count==QueueSize;
}
void EnQueue(LinkQueue *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(LinkQueue *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 CreateMGraph(MGraph *G)
{
int i,j,k;
char c1,c2;
printf("\n请输入顶点数，边数，以空格间隔，并回车：");
scanf("%d%d",&(G->n),&(G->e));
for(i=0;i<G->n;i++)
{
printf("\n请输入第%d个顶点并回车：",i+1);
scanf("%c",&(G->vexs[i]));
G->vexs[i]=getchar();
}
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->adj[i][j]=0;
for(k=0;k<G->e;k++)
{
getchar();
printf("\n请输入第%d条边的顶点序号（如：ab）：",k+1);
scanf("%c%c",&c1,&c2);
for(i=0;c1!=G->vexs[i];i++);
for(j=0;c2!=G->vexs[j];j++);
G->adj[i][j]=1;
}
}

void DFSM(MGraph *G,int i)
{
int j;
printf("%c ",G->vexs[i]);
visited[i]=TRUE;
for(j=0;j<G->n;j++)
if(G->adj[i][j]==1 && visited[j]!=1)
DFSM(G,j);
}

void BFSM(MGraph *G,int k)
{
int i,j;
LinkQueue Q;
InitQueue(&Q);
printf("%c ",G->vexs[k]);
visited[k]=TRUE;
EnQueue(&Q,k); //入队
while(!QueueEmpty(&Q))
{
i=DeQueue(&Q); //出队
for(j=0;j<G->n;j++)
if(G->adj[i][j]==1 && visited[j]!=1)
{
visited[j]=TRUE;
EnQueue(&Q,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);
}
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);
}

void main()
{
MGraph *G,a;
int i,j,k,s;
G=&a;
printf("\n请建立一个图的邻接矩阵表示\n");
CreateMGraph(G);
printf("\n已成功建立一个图的邻接矩阵存储：\n");
for(i=0;i<G->n;i++)
{
printf("\n");
for(j=0;j<G->n;j++)
printf("%3d&quo

t;,G->adj[i][j]);
}
getchar();
s=1;
while(s==1)
{
printf("\n");
printf("\n请选择功能：0.退出 1.深度优先遍历，2.广度优先遍历 ，3.更新邻接矩阵：");
scanf("%d",&k);
switch(k)
{
case 0:s=0;break;

case 1:printf("深度优先遍历序列：");DFSTraverseM(G);break;
case 2:printf("广度优先遍历序列：");BFSTraverseM(G);break;
case 3:CreateMGraph(G);printf("\n图的邻接矩阵存储建立完成\n");break;
default:printf("\n输出错误！清重新输入！");
}
}
}