#include<stdio.h>
#define QUEUE_MAXSIZE 30
typedef struct
{
int Data[QUEUE_MAXSIZE];
int head;
int tial;
}SeqQueue;
void QueueInit(SeqQueue *Q)
{
Q->head = Q->tail = 0;
}
int QueueIsEmpty(SeqQueue)
{
return Q.head == Q.tail;
}
int QueueIn(SeqQueue *Q,int ch)
{
if((Q->tail+1) % QUEUE_MAXSIZE == Q->head)
return 0;
Q->Data[Q->tail] = ch;
Q->tail = (Q->tail+1) % QUEUE_MAXSIZE;
return 1;
}
int QueueOut(SeqQueue *Q,int *ch)
{
if(Q->head == Q->tail)
return 0;
*ch = Q->Data[Q->head];
Q->head = (Q->head +1 ) % QUEUE_MAXSIZE;
return 1;
}
void BFSM(MatrixGraph *G,int k)
{
int i,j;
SeqQueue Q;
QueueInit(&Q);
G->isTrav[k] = 1;
printf("->%c",G->Vertex[k]);
QueueIn(&Q,k); while(!QueueIsEmpty(Q)) { QueueOut(&Q,&i); for(j=0;j<G->VertexNum;j++) if(G->Edge[i][j] != MAXVALUE && !G->isTrav[j]) { printf("->%c",G->Vertex[j]); G->isTrav[j] = 1; QueueIn(&Q,j); } }
}
//广度优先遍历
void BFSTraverse(MatrixGraph *G)
{
int i;
for(i=0;i<G->VertexNum;i++)
G->isTrav[i] = 0;
for(i=0;i<G->VertexNum;i++)
if(!G->isTrav[i])
BFSM(G,i);
printf("\n");
}
//深度优先遍历
void DFSM(MatrixGraph *G,int i)
{
int j;
G->isTrav[i] = 1;
printf("->%c",G->Vertex[i]);
for(j=0;j<G->Vertexnum;j++)
if(G->Edges[i][j] != MAXVALUE && !G->isTrav[i])
DFSM(G,j);
}
void DFSMTraverse(MatrixGraph *G)
{
int i;
for(i=0;i<G->VertexNum;i++)
G->isTrav[i] = 0;
for(i=0;i<G->VertexNum;i++) if(!G->isTrav[i]) DFSM(G,i);
printf("\n");
}
