数据结构C语言实现图的建立-图的广度-深度遍历.doc

图的建立，图的广度，深度遍历
#include "stdio.h"
#define maxsize 1000
# define n 100
typedef struct
{ char vexs[n] ;
int arcs[n][n] ;
int num ;
}G;
typedef struct
{
int data[maxsize];
int front,rear;
} V;

void GInit(G *L)
{
L->num=0;
}

int GVexs(G *L)
{
return(L->num);
}

void GCreate(G *L)
{
int i,j;
GInit(L);
printf("请输入顶点数目：\n");
scanf("%d",&L->num);
printf("请输入各顶点：\n");
for(i=0;inum;i++)
{
fflush(stdin);
scanf("%c",&L->vexs[i]);
}

printf("请输入各顶点边的关系（1是有关0是无关）：\n");
for(i=0;inum;i++)
{
for(j0;jnum;j++)
{
scanf("%d",&L->arcs[i][j]);
}
}

}

void GOut(G L)
{
int i,j;
printf("\n图的顶点数目为：%d",L.num);
printf("\n图的各顶点的信息为：\n");
for(i=0;i"%7d ",L.arcs[i][j]);
}
printf("\n");
}

}

void DFS(G g,int qidian,int mark[])

{
int v1;
mark[qidian]=1;
printf("%c ",g.vexs[qidian]);
for(v1=0;v1mark[maxsize];
printf("\n深度遍历：");
printf("\n请输入起点的下标：");
scanf("%d",&qidian);
getchar();
for(v=0;vfront=0;
sq->rear=0;
}

int QueueIsEmpty(V sq)

{
if (sq.rear==sq.front)
return(1);
else
return(0);
}
int QueueFront(V sq, int *e)

{
if (QueueIsEmpty(sq))
{ printf("queue is empty!\n");return 0;}
else
{ *e=sq.data[(sq.front)]; return 1;}
}

int QueueIn (V *sq, int x)
//
{
if (sq->front==(sq->rear+1)%maxsize)
{
printf("queue is full!\n");
return 0;
}
else
{
sq->data[sq->rear]=x;
sq->rear=(sq->rear+1)%maxsize;
return(1);
}
}

int QueueOut(V *sq)

{
if (QueueIsEmpty(*sq))
{
printf("queue is empty!\n");
return 0;
}
else
{
sq->front=(sq->front+1)%maxsize;
return 1;
}
}

void BFS(G g,int v,int mark[])

{
int v1,v2;
V q;
QueueInit(&q);
QueueIn(&q,v);
mark[v]=1;
printf("%c ",g.vexs[v]);
while(QueueIsEmpty(q)==0)
{
QueueFront(q,&v1);
QueueOut(&q);
for(v2=0;v2