#include
#include
#include
#include
#define maxsize 64
#define TRUE 1
#define FALSE 0
#define n 10
#define e 13
typedef char datatype ;
typedef char vextype;
typedef int adjtype;
typedef struct
{
vextype vexs[maxsize];
adjtype arcs[maxsize][maxsize];
}graph;
typedef struct
{
datatype data[maxsize];
int front,rear;
}sequeue;
typedef struct node
{
int adjvex;
struct node *next;
}edgenode;
typedef struct
{
vextype vertex;
edgenode *link;
}vexnode;
vexnode gl[maxsize];
graph *ga;
sequeue *Q;
graph *CREATGRAPH()
{
int i,j,k;
char ch;
system("cls");
scanf("%c",&ch);
printf("n请输入顶点信息(邻接矩阵):");
for(i=1;ivexs[i]);
for(i=1;iarcs[j][i]=1;
}
return ga;
}
void PRINT()
{
int i,j;
system("cls");
printf("n对应的邻接矩阵是：nn");
for(i=1;iadjvex=i;
s->next=gl[j].link;
gl[j].link=s;
}
}
void PRINTL()
{
int i;
edgenode *s;
system("cls");
printf("n对应的邻接表是：n");
for(i=1;iadjvex);
s=s->next;
}
printf("n");
}
}
sequeue *SETNULL(sequeue *P)
{
P->front=maxsize-1;
P->rear=maxsize-1;
return P;
}
int EMPTY(sequeue *Q)
{
if(Q->rear==Q->front)
return TRUE;
else
return FALSE;
}
sequeue *ENQUEUE(sequeue *Q,int k)
{
if(Q->front==(Q->rear+1)%maxsize)
{
printf("队列已满!n");
return NULL;
}
else
{
Q->rear=(Q->rear+1)%maxsize;
Q->data[Q->rear]=k;
}
return Q;
}
int DEQUEUE(sequeue *Q)
{
if(EMPTY(Q))
{
printf("队列为空,无法出队!n");
return FALSE;
}
else
{
Q->front=(Q->front+1)%maxsize;
return Q->data[Q->front];
}
return 1;
}
void BFS(int k)
{
int i,j;
int visited[maxsize]={0};
printf("n广度优先遍历后得到的序列是:");
Q=SETNULL(Q);
printf("%3c",ga->vexs[k]);
visited[k]=TRUE;
Q=ENQUEUE(Q,k);
while(!EMPTY(Q))
{
i=DEQUEUE(Q);
for(j=1;jarcs[i][j]==1)&&(!visited[j]))
{
printf("%3c",ga->vexs[j]);
visited[j]=TRUE;
Q=ENQUEUE(Q,j);
}
}
printf("nn深度优先遍历后得到的序列是:");
}
void BFSL(int k)
{
int i;
int visited[maxsize]={0};
edgenode *p;
Q=SETNULL(Q);
printf("n广度优先遍历后得到的序列是:");
printf("%3c",gl[k].vertex);
visited[k]=TRUE;
Q=ENQUEUE(Q,k);
while(!EMPTY(Q))
{
i=DEQUEUE(Q);
p=gl[i].link;
while(p!=NULL)
{
if(!visited[p->adjvex])
{
printf("%3c",gl[p->adjvex].vertex);
visited[p->adjvex]=TRUE;
Q=ENQUEUE(Q,p->adjvex);
}
p=p->next;
}
}
printf("nn深度优先遍历后得到的序列是:");
}
void DFS(int i)
{
int j;
static int visited[maxsize]={0};
printf("%3c",ga->vexs[i]);
visited[i]=TRUE;
for(j=1;jarcs[i][j]==1)&&(!visited[j]))
DFS (j);
}
void DFSL(int k)
{
int j;
edgenode *p;
static int visited[maxsize]={0};
printf("%3c",gl[k].vertex);
visited[k]=TRUE;
p=gl[k].link;
while(p)
{
j=p->adjvex;
if(!visited[j])
DFSL(j);
p=p->next;
}
}
void main()
{
int i,k;
int ch;
Q=malloc(sizeof(graph));
ga=malloc(sizeof(graph));
while(1)
{
printf("nnn");
printf("输入你的选择:");
scanf("%d",&ch);
switch(ch)
{
case 1:CREATADJLIST();
PRINTL();
printf("想从第几号结点开始:");
scanf("%d",&k);
BFSL(k);
DFSL(k);break;
case 2:ga=CREATGRAPH();
PRINT();
printf("想从第几号结点开始:");
scanf("%d",&i);
BFS(i);
DFS(i);break;
case 3:exit (0);
}
}
}