邻接矩阵、邻接表表示图时的深度优先序列、广度优先序列

邻接矩阵、邻接表表示图时的深度优先序列、广度优先序列
已知一个图的顶点集V各边集G如下：
V = {0,1,2,3,4,5,6,7,8,9}；
E = {（0,1）,（0,4）,（1,2）,（1,7）,（2,8）,（3,4）,（3 ,8）,（5,6）,（5,8）,（5,9）,（6,7）,（7,8）,（8,9）}
当它用邻接矩阵表示和邻接表表示时,分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列.
假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的.
图 深度优先序列 广度优先序列
邻接矩阵表示时
邻接表表示时

#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对应的邻接矩阵是：\n\n");
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("\n\n深度优先遍历后得到的序列是:");
}
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("\n\n深度优先遍历后得到的序列是:");
}
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("\n\n\n");
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);
}
}
}