2023年数据结构图的遍历实验报告

实验报告

课程名:数据结构（C语言版）

实验名:图的遍历

姓名：

班级：

学号：

时间：2023.11.15

一实验目的与规定

1.掌握图的遍历的方法

2.运用C语言实现图的遍历

二实验内容

•将一个图存储起来

•对该图分别进行先深和先广遍历

三实验结果与分析

程序：

#include<std1ib.h>

#include<stdio.h>

#defineINFINITY32767

#defineMAX_VEX20//最大顶点个数

#defineQUEUE_SIZE(MAX_VEX+1)〃队列长度

//usingnamespacestd；

bool*visited;//访问标志数组，避免同一顶点多次访问

/****图的邻接矩阵存储结构******/

typedefstruct{

char*vexs；//顶点向量

intares[MAX_VEX][MAX_VEX];〃邻接矩阵

intvexnum,arcnum；//图的当前顶点数和弧数

}Graph;

/*********队歹lj类************/

classQueue{

pub1ic：

voidInitQueue(){

base=(int*)maHoc(QUEUE_SIZEsizeof(int));

front=rear=0；

}

voidEnQueue(inte){

base[rear]=e;

rear=(rear+1)%QUEUE_SIZE；

)

voidDeQueue(int&e){

e=base[front];

front=(front+1)%QUEUE_SIZE;

}

public：

int*base;

intfront;

intrear；

)；

/*图G中查找元素c的位置*/

intLocate(GraphG,charc)

(

for(inti=0;i<G.vexnum；i++)

if(G.vexs[i]==c)returni;

return-1;

)

/*创建无向网*/

voidCreateUDN(Graph&G){

inti,j,w,sl,s2;

chara,b,temp;

printf("输入顶点数和弧数:")；

scanf("%d%d",&G.vexnum,&G.arcnum);

temp=getchar();〃接受回车

G.vexs=(char*)malloc(G.vexnum*sizeof(char))；//分派顶

点数目

printf("输入％(1个顶点.\n”,G.vexnum);

for(i=0；iVGvexnum；i++){//初始化顶点

printf(n输入顶点％金”,i);

scanf(M%cn,&G.vexs[i]);

ternp=getchar();〃接受回车

)

for(i=0;i<G.vexnum;i++)〃初始化邻接矩阵

fbr(j=O;j<G.vexnum；j++)

G.arcs[i][j]=INFINITY；

printf("输入％d条弧.\nn,G.arcnum);

for(i=0；i<G.arcnum;i++){〃初始化弧

printf("输入弧％d:”,i);

scanf("%c%c%dn,&a,&b,&w);〃输入一条边依附的顶点和权值

temp=getchar()；〃接受回车

s1=Locate(G,a);

s2=Locate(G,b)；

G.arcs[sl][s2]=Garcs[s2]fsl]=w;

/*****图G中顶点k的第一个邻接顶点***********/

intFirstVex(GraphG,intk){

if(k>=0&&k<G.vexnum){//k合理

for(inti=0;i<G.vexnum；i++)

if(G.arcs[k]fi]!=INFINITY)returni;

}

return-1；

)

/************图G中顶点i的第j个邻接顶点的下一个邻接顶点

intNextVex(GraphG,inti,intj){

if(i>=0&&i<G.vexnum&&j>=0&&j<G.vexnum){//i,j

合理

for(intk=j+l;k<G.vexnum;k4-+)

if(G.arcs[i][k]!=INFINITY)returnk;

)

retum-1;

)

/*************深度优先遍历************/

voidDFS(GraphG,intk){

inti；

if(k==—1){〃第一次执行DFS时,k为一1

for(i=0;i<G.vexnum;i++)

if(!visited：i])DFS(G,i)；//对尚未访问的顶点调用DFS

)

else(

visited[k]=true；

printf("%c",G.vexs[k]);//访问第k个顶点

for(i=FirstVex(G,k);i>=0；i=NextVex(G,k,i))

if(!visited[i])DFS(G,i)；//对k的尚未访问的邻接顶点i递归调用D

FS

)

}

I****************广度优先遍历***************/

voidBFS(GraphG){

intk;

QueueQ；〃辅助队列Q

Q.InitQueue()；

for(inti=0;i<G.vexnum;i++)

if(!visited[i]){//i尚未访问

visitedfi]=true;

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

Q.EnQueue(i);//i入列

while(Q.front!=Q.rear){

Q.DeQueue(k);〃队头元素出列并置为k

for(intw=FirstVex(G,k);w>=0;w=NextVex(G,k,w))

if(!visited[w]){〃w为k的尚未访问的邻接顶点

visited[w]=true;

printf(n%c”，Gvexs[w]);

Q.EnQueue(w);

}

}

/***********主函数***************/

voidmain(){

inti;

GraphG;

CreateUDN(G);

visit6d=(boo1*)malloc(G.vexnum*siz