数据结构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;i<L->num;i++)
{
fflush(stdin);
scanf("%c",&L->vexs[i]);
}

printf("请输入各顶点边的关系（1是有关0是无关）：\n");
for(i=0;i<L->num;i++)
{
for(j=0;j<L->num;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<L.num;i++)
printf("%7c",L.vexs[i]);
printf("\n");

for(i=0;i<L.num;i++)
{
for(j=0;j<L.num;j++)
{
printf("%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;v1<g.num;v1++)
{
if(g.arcs[qidian][v1]!=0&&mark[v1]==0)
DFS(g,v1,mark);
}
}

void GDFS(G g)

{
int qidian,v,v1,mark[maxsize];
printf("\n深度遍历：");
printf("\n请输入起点的下标：");
scanf("%d",&qidian);
getchar();
for(v=0;v<g.num;v++)
{
mark[v]=0;
}
for(v=qidian;v<g.num+qidian;v++)
{

v1=v%g.num;
if(mark[v1]==0)
DFS(g,v1,mark);
}
}

void QueueInit(V *sq)

{
sq->front=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<g.num;v2++)
{
if(g.arcs[v1][v2]!=0&&mark[v2]==0)
{
QueueIn(&q,v2);
mark[v2]=1;
printf("%c ",g.vexs[v2]);
}
}
}
}

void GBFS(G g)

{
int qidian,v,v1,mark[maxsize];
printf("\n广度遍历：");

printf("\n");
scanf("%d",&qidian);
for(v=0;v<g.num;v++)
{
mark[v]=0;
}
for(v=qidian;v<g.num+qidian;v++)
{
v1=v%g.num;
if(mark[v1]==0)
BFS(g,v1,mark);
}
}

void main()
{
G tu;
GCreate(&tu);
GOut(tu);
GDFS(tu);
GBFS(tu);
}