图的深度和广度优先遍历

数据结构课程实验报告

1

2

3

4

}

int GraphVexs(GRAPH *L)//求结点数 {

return(L->num); }

void GraphCreate(GRAPH *L)//创建图 { }

void GraphOut(GRAPH L)//图的输出 { }

void DFS(GRAPH g,int qidian,int mark[])//从第qidian个点出发深度优先遍历图g中能访问的各个顶点 {

int v1; mark[qidian]=1;

printf("%c ",g.vexs[qidian]); for(v1=0;v1<g.num;v1++) { }

5

if(g.arcs[qidian][v1]!=0&&mark[v1]==0)

DFS(g,v1,mark);

int i;

printf("\n图的顶点数目为：%d",L.num); printf("\n图的各顶点的信息为：\n"); for(i=0;i<L.num;i++)

printf("%c ",L.vexs[i]);

int i; GraphInit(L);

printf("请输入顶点数目："); scanf("%d",&L->num);

printf("请输入各顶点的信息(单个符号）：\n"); for(i=0;i<L->num;i++) { }

printf("图已经创建完毕！");

fflush(stdin);

scanf("%c",&L->vexs[i]);

L->num=0;

void GraphDFS(GRAPH g)//深度优先遍历图g中能访问的各个顶点 { }

void QueueInit(SEQQUEUE *sq)//建立空队列 {

sq->front=0; sq->rear=0; }

int QueueIsEmpty(SEQQUEUE sq)//判断队列是否为空 {

if (sq.rear==sq.front) return(1); else return(0); }

int QueueFront(SEQQUEUE sq,DATATYPE *e)//保存队头元素 { {

printf("queue is empty!\n");return 0;}

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

for(v=qidian;v<g.num+qidian;v++) { }

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

DFS(g,v1,mark);

mark[v]=0;

else { *e=sq.data[(sq.front)]; return 1;} }

int QueueIn (SEQQUEUE *sq,DATATYPE x)//把元素x入队尾 {

if(sq->front==(sq->rear+1)%maxsize) {

printf("queue is full!\n"); return 0;

6

}

else { }

sq->data[sq->rear]=x;

sq->rear=(sq->rear+1)%maxsize; return(1);

int QueueOut(SEQQUEUE *sq)//删除队首元素 { } }

void BFS(GRAPH g,int v,int mark[])//从v出发广度优先遍历图g中能访问的各个顶点 {

int v1,v2; SEQQUEUE 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++) { }

7

if(g.arcs[v1][v2]!=0&&mark[v2]==0) { }

QueueIn(&q,v2); mark[v2]=1;

printf("%c ",g.vexs[v2]);

if(QueueIsEmpty(*sq)) { } else {

sq->front=(sq->front+1)%maxsize; return 1;

printf("queue is empty!\n"); return 0;

8