数据结构--图的基本操作

1．实验题目

图的基本操作

2．实验目的

1) 掌握图的邻接矩阵、邻接表的表示方法。 2) 掌握建立图的邻接矩阵的算法。

3) 掌握建立图的邻接表的算法。

4) 加深对图的理解，逐步培养解决实际问题的编程能力 3．需求分析

(1)编写图基本操作函数。 ①建立图的邻接表，邻接矩阵

Create_Graph( LGraph lg. MGraph mg )

②邻接表表示的图的递归深度优先遍历 LDFS( LGraph g, int i ) ③邻接矩阵表示的图的递归深度优先遍历MDFS( MGraph g,int i, int vn ) ④邻接表表示的图的广度优先遍历 ⑤邻接矩阵表示的图的广度优先遍历 (2)调用上述函数实现下列操作。 ①建立一个图的邻接矩阵和图的邻接表。 ②采用递归深度优先遍历输出图的邻接矩阵 ③采用递归深度优先遍历输出图的邻接表。 ④采用图的广度优先调历输出图的邻接表。 ⑤采用图的广度优先遍历输出图的邻接矩阵 4．概要设计 （1） ：

/**********************************图的基本操作**********************************/ //------------------------------- 邻接矩阵数据类型的定义--------------------------------

// 最大顶点个数

LBFS( LGraph g, int s, int n ) MBFS(MGraph g, int s, int n )

typedef struct {

char vexs[MAX_VERTEX_NUM];

// 顶点向量

// 邻接矩阵

int acrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

int vexnum,arcnum;

// 图当前顶点数和弧数

}MGraph ;

//--------------------------------邻接表数据类型的定义---------------------------------- typedef struct ArcNode {

int adjvex;

// 该弧所指向的顶点的位置

struct ArcNode *nextarc;

}ArcNode;

typedef struct VNode { char data;

ArcNode *firstarc;

}VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices;

int vexnum,arcnum;

}LGraph;

2） 本程序主要包含6个函数：

• 主函数 main()

• 建立图的邻接矩阵，邻接表

• 邻接表表示的图的递归深度优先遍历 • 邻接矩阵表示的图的递归深度优先遍历 • 邻接表表示的图的广度优先遍历 • 邻接矩阵表示的图的广度优先遍历

各函数间调用关系如下：

main

3） 主函数的伪码

main()

{ 定义邻接矩阵和邻接表；

建立邻接矩阵和邻接表； 邻接矩阵MDFS 深度优先遍历； 邻接矩阵MBFS 广度优先遍历 ； 邻接表LDFS 深度优先遍历； 邻接表LBFS 广度优先遍历

福建师范大学物光院计算机教学辅导讲义

// 指向下一条弧的指针

// 顶点信息

// 指向第一条依附该顶点的弧的指针

// 图当前顶点数和弧数

Create_Graph () LDFS () MDFS () LBFS () MBFS （）

Create_Graph () LDFS () MDFS ()

LBFS () MBFS （）

2

（

（

} 5详细设计

/**********************************图的基本操作**********************************/ //------------------------------- 邻接矩阵数据类型的定义-------------------------------- // 最大顶点个数 typedef struct { char vexs[MAX_VERTEX_NUM]; // 顶点向量

int acrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vexnum,arcnum; // 图当前顶点数和弧数 }MGraph ;

//--------------------------------邻接表数据类型的定义---------------------------------- typedef struct ArcNode { int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 }ArcNode;

typedef struct VNode { char data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针 }VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum,arcnum; // 图当前顶点数和弧数 }LGraph;

int Create_Graph( MGraph *Mg , LGraph *Lg ) // 建立图的邻接矩阵，邻接表 { 输入图的顶点个数（字符），构造顶点向量 输入图的任意两个顶点的弧

构造邻接矩阵 构造邻接表 }

void LDFS(LGraph *Lg,int i) 邻接表表示的图的递归深度优先遍历 {

显示顶点向量，

指针指向下一个顶点向量 下一个顶点没有被访问，继续

否则 退会上一个顶点向量的另一个边 }

void MDFS(MGraph *Mg,int i) 邻接矩阵表示的图的递归深度优先遍历

3

{

显示顶点向量，

指针指向下一个顶点向量 下一个顶点没有被访问，继续

否则 退会上一个顶点向量的另一个边

}

void LBFS( LGraph *Lg )邻接表表示的图的广度优先遍历 {

初始化 visited[] 初始化 队列 没被访问过

显示顶点向量入队

出队访问下一个顶点向量 }

void MBFS(MGraph *Mg )邻接矩阵表示的图的广度优先遍历 {

初始化 visited[] 初始化 队列 没被访问过

显示顶点向量入队

出队访问下一个顶点向量 }

//-------------------主函数------------------------------- main()

{ 定义邻接矩阵和邻接表；

建立邻接矩阵和邻接表； 邻接矩阵MDFS 深度优先遍历； 邻接矩阵MBFS 广度优先遍历 ； 邻接表LDFS 深度优先遍历； 邻接表LBFS 广度优先遍历 }

4

7. 参考文献 《数据结构》 8．附录

#include #include #include #include #define OK 1 #define ERROR 0

#define MAX_VERTEX_NUM 20

/**********************************图的基本操作**********************************/

int visited[MAX_VERTEX_NUM];

//------------------------------- 邻接矩阵数据类型的定义-------------------------------- {

char vexs[MAX_VERTEX_NUM]; int vexnum,arcnum;

// 顶点向量

// 邻接矩阵

int acrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; }MGraph ;

//--------------------------------邻接表数据类型的定义----------------------------------

5

// 访问标志数组

// 最大顶点个数

typedef struct

// 图当前顶点数和弧数

typedef struct ArcNode {

int adjvex;

// 该弧所指向的顶点的位置 // 指向下一条弧的指针

struct ArcNode *nextarc;

}ArcNode;

typedef struct VNode {

char data;

// 顶点信息

// 指向第一条依附该顶点的弧的指针

ArcNode *firstarc;

}VNode, AdjList[MAX_VERTEX_NUM]; typedef struct {

//_________________________________队列函数__________________________________________ typedef struct Queue {

int arry[MAX_VERTEX_NUM]; int front,rear; AdjList vertices; int vexnum,arcnum;

// 图当前顶点数和弧数

}LGraph;

}Queue; Queue Q; void InitQueue() { }

int QueueEmpty(Queue *Q) { }

void EnQueue(Queue *Q,int w)// 入队 {

// 队列初始化

Q.front=Q.rear=0;

// 清空队列

if(Q->front==Q->rear) else

return 0; return 1;

if((Q->rear+1)%MAX_VERTEX_NUM==Q->front) else {

Q->arry[Q->rear]=w;

6

printf("Error!");

}

int DeQueue(Queue *Q) { }

//____________________________________队列函数end_______________________________________ /**************************************************************************************** *函数：Create_Graph

*功能：建立图的邻接矩阵，邻接表

*说明：该构建的为无向网 mg 为邻接矩阵 ，lg 为邻接表 , 无权值

***************************************************************************************/ {

// 出队

int u;

return -1;

if(Q->front==Q->rear)

u=Q->front;

Q->front=(Q->front+1)%MAX_VERTEX_NUM; return u;

int Locatevex(MGraph *Mg , char v) { }

int i;

for(i=0;Mg->vexs[i]!=v;i++); if(i>Mg->vexnum) return i;

// 确定 v 元素在Mg 中的位置

// 输入的元素不正确则显示 错误 // 返回位置

printf("ERROR ");

int Create_Graph( MGraph *Mg , LGraph *Lg ) // 建立图的邻接矩阵，邻接表

int i , j , k ; char v1 , v2 ; ArcNode *q,*p;

printf("输入图的顶点数和弧数: "); getchar();

Lg->vexnum=Mg->vexnum; Lg->arcnum=Mg->arcnum;

for(i=0;ivexnum;i++) {

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

Lg->vertices[i].data=Mg->vexs[i]; // 赋值 Lg->vertices[i].firstarc=NULL;

// 指向第一条依附该顶点的弧的指针 为空

7

scanf("%d %d",&Mg->vexnum,&Mg->arcnum);

// 邻接表的顶点数和弧数

// 构造顶点向量

printf("请输入一个图的顶点(字符):");

}

/**************************************************************************************** *函数：LDFS

*功能：邻接表表示的图的递归深度优先遍历 *说明：

***************************************************************************************/

}

void LDFS(LGraph *Lg,int i) {

8

for(i=0;ivexnum;i++)

for(j=0;jvexnum;j++)

Mg->acrs[i][j]=0 ;

// 构造邻接矩阵和邻接表

// 初始化邻接矩阵

for(k=0;karcnum;k++) { }

return OK ;

printf("请输入一条边连接的2个顶点："); scanf("%c %c",&v1,&v2); getchar();

i=Locatevex(Mg,v1); j=Locatevex(Mg,v2);

// 确定 v1 在Mg 中的位置 // 确定 v2 在Mg 中的位置

Mg->acrs[j][i]=Mg->acrs[i][j]=1; // 置《v1,v2》的对称弧《v2,v1》 p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=i;

// 确认顶点位置 // 赋值

// 确认顶点位置 // 赋值

p->nextarc=Lg->vertices[j].firstarc;// 指向下一条弧的指针 Lg->vertices[j].firstarc=p; q->adjvex=j;

q=(ArcNode *)malloc(sizeof(ArcNode));

q->nextarc=Lg->vertices[i].firstarc;// 指向下一条弧的指针 Lg->vertices[i].firstarc=q;

int LAdjVex(LGraph *Lg,int k) {

ArcNode *p;

// 位置

for(p=Lg->vertices[k].firstarc;p!=NULL;p=p->nextarc)

if(!visited[p->adjvex])

return p->adjvex;

return -1;

}

/**************************************************************************************** *函数：MDFS

*功能：邻接矩阵表示的图的递归深度优先遍历 *说明：

***************************************************************************************/ { }

/**************************************************************************************** *函数：LBFS

*功能：邻接表表示的图的广度优先遍历 *说明：

***************************************************************************************/

void LBFS( LGraph *Lg ) {

printf("%c",Lg->vertices[i].data);

for(k=LAdjVex(Lg,i);k>=0;k=LAdjVex(Lg,k))

if(!visited[k])

LDFS(Lg,k);

int AdjVes(MGraph *Mg,int k) { }

int i;

for(i=0;ivexnum;i++)

// 位置

if(Mg->acrs[k][i]&&(!visited[i]))

return i;

return -1;

// 递归深度优先遍历

void MDFS(MGraph *Mg,int i)

int k; visited[i]=1;

// 访问标志数组某位 置 1 // 显示

printf("%c",Mg->vexs[i]);

if(!visited[k])

MDFS(Mg,k);

for(k=AdjVes(Mg,i);k>=0;k=AdjVes(Mg,k))

// 递归

int i,u,w;

for(i=0;ivexnum;++i)

visited[i]=0;

// 初始化 队列 // 没被访问过

9

// 初始化 visited[]

InitQueue();

for(i=0;ivexnum;++i)

if(!visited[i]) {

}

/**************************************************************************************** *函数：MBFS

*功能：邻接矩阵表示的图的广度优先遍历 *说明：

***************************************************************************************/ void MBFS(MGraph *Mg ) {

}

EnQueue(&Q,i); { }

u=DeQueue(&Q);

if(!visited[w]) { }

visited[w]=1;

printf("%c",Lg->vertices[w].data); EnQueue(&Q,w);

// 入队

// 出队

for(w=LAdjVex(Lg,u);w>=0;w=LAdjVex(Lg,u))

// 没被访问过

// 入队

while(!QueueEmpty(&Q))

int i,w,u;

for(i=0;ivexnum;i++)

visited[i]=0;

// 初始化队列 // 没被访问过

InitQueue();

// 初始化 visited[]

for(i=0;ivexnum;++i)

if(!visited[i]) {

visited[i]=1;

printf("%c",Mg->vexs[i]); EnQueue(&Q,i); {

u=DeQueue(&Q);

// 出队

for(w=AdjVes(Mg,u);w>=0;w=AdjVes(Mg,u))

// 没被访问过

{ }

10

// 显示

// 入队

while(!QueueEmpty(&Q))

if(!visited[w])

visited[w]=1;

printf("%c",Mg->vexs[w]);

// 显示 // 入队

EnQueue(&Q,w);

福建师范大学物光院计算机教学辅导讲义

}

/***************************************主函数*******************************************/ void main()

{

printf("\n邻接表LBFS 广度优先遍历：\t"); LBFS(&Lg) ; printf("\n");

● 每位同学必须完成实验任务，并提交实验报告。杜绝抄袭和拷贝，一经发现该次实验雷同报告均以零分计。

● 请将实验报告以电子文档提交， “网络工程”专业请发送到[email protected]信箱中，“电子信息”专业请发送到[email protected] 信箱中，请附上程序清单.C 源程序文件、和实验报告WORD 文档两部分，以打包压缩文件形式提交，每次实验为一个文件夹的打包压缩文件，文件夹名统一为*⊙⊙⊙??.rar 或*⊙⊙⊙??.zip ，其中*为你的学号（全部号码），⊙⊙⊙为你中文姓名，?? 分别为01，02，03……11表示第几次实验。

11 } } int i ; MGraph Mg; LGraph Lg; Create_Graph( &Mg, &Lg); printf("邻接矩阵MDFS 深度优先遍历：\t"); for(i=0;i

1．实验题目

图的基本操作

2．实验目的

1) 掌握图的邻接矩阵、邻接表的表示方法。 2) 掌握建立图的邻接矩阵的算法。

3) 掌握建立图的邻接表的算法。

4) 加深对图的理解，逐步培养解决实际问题的编程能力 3．需求分析

(1)编写图基本操作函数。 ①建立图的邻接表，邻接矩阵

Create_Graph( LGraph lg. MGraph mg )

②邻接表表示的图的递归深度优先遍历 LDFS( LGraph g, int i ) ③邻接矩阵表示的图的递归深度优先遍历MDFS( MGraph g,int i, int vn ) ④邻接表表示的图的广度优先遍历 ⑤邻接矩阵表示的图的广度优先遍历 (2)调用上述函数实现下列操作。 ①建立一个图的邻接矩阵和图的邻接表。 ②采用递归深度优先遍历输出图的邻接矩阵 ③采用递归深度优先遍历输出图的邻接表。 ④采用图的广度优先调历输出图的邻接表。 ⑤采用图的广度优先遍历输出图的邻接矩阵 4．概要设计 （1） ：

/**********************************图的基本操作**********************************/ //------------------------------- 邻接矩阵数据类型的定义--------------------------------

// 最大顶点个数

LBFS( LGraph g, int s, int n ) MBFS(MGraph g, int s, int n )

typedef struct {

char vexs[MAX_VERTEX_NUM];

// 顶点向量

// 邻接矩阵

int acrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

int vexnum,arcnum;

// 图当前顶点数和弧数

}MGraph ;

//--------------------------------邻接表数据类型的定义---------------------------------- typedef struct ArcNode {

int adjvex;

// 该弧所指向的顶点的位置

struct ArcNode *nextarc;

}ArcNode;

typedef struct VNode { char data;

ArcNode *firstarc;

}VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices;

int vexnum,arcnum;

}LGraph;

2） 本程序主要包含6个函数：

• 主函数 main()

• 建立图的邻接矩阵，邻接表

• 邻接表表示的图的递归深度优先遍历 • 邻接矩阵表示的图的递归深度优先遍历 • 邻接表表示的图的广度优先遍历 • 邻接矩阵表示的图的广度优先遍历

各函数间调用关系如下：

main

3） 主函数的伪码

main()

{ 定义邻接矩阵和邻接表；

建立邻接矩阵和邻接表； 邻接矩阵MDFS 深度优先遍历； 邻接矩阵MBFS 广度优先遍历 ； 邻接表LDFS 深度优先遍历； 邻接表LBFS 广度优先遍历

福建师范大学物光院计算机教学辅导讲义

// 指向下一条弧的指针

// 顶点信息

// 指向第一条依附该顶点的弧的指针

// 图当前顶点数和弧数

Create_Graph () LDFS () MDFS () LBFS () MBFS （）

Create_Graph () LDFS () MDFS ()

LBFS () MBFS （）

2

（

（

} 5详细设计

/**********************************图的基本操作**********************************/ //------------------------------- 邻接矩阵数据类型的定义-------------------------------- // 最大顶点个数 typedef struct { char vexs[MAX_VERTEX_NUM]; // 顶点向量

int acrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vexnum,arcnum; // 图当前顶点数和弧数 }MGraph ;

//--------------------------------邻接表数据类型的定义---------------------------------- typedef struct ArcNode { int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 }ArcNode;

typedef struct VNode { char data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针 }VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum,arcnum; // 图当前顶点数和弧数 }LGraph;

int Create_Graph( MGraph *Mg , LGraph *Lg ) // 建立图的邻接矩阵，邻接表 { 输入图的顶点个数（字符），构造顶点向量 输入图的任意两个顶点的弧

构造邻接矩阵 构造邻接表 }

void LDFS(LGraph *Lg,int i) 邻接表表示的图的递归深度优先遍历 {

显示顶点向量，

指针指向下一个顶点向量 下一个顶点没有被访问，继续

否则 退会上一个顶点向量的另一个边 }

void MDFS(MGraph *Mg,int i) 邻接矩阵表示的图的递归深度优先遍历

3

{

显示顶点向量，

指针指向下一个顶点向量 下一个顶点没有被访问，继续

否则 退会上一个顶点向量的另一个边

}

void LBFS( LGraph *Lg )邻接表表示的图的广度优先遍历 {

初始化 visited[] 初始化 队列 没被访问过

显示顶点向量入队

出队访问下一个顶点向量 }

void MBFS(MGraph *Mg )邻接矩阵表示的图的广度优先遍历 {

初始化 visited[] 初始化 队列 没被访问过

显示顶点向量入队

出队访问下一个顶点向量 }

//-------------------主函数------------------------------- main()

{ 定义邻接矩阵和邻接表；

建立邻接矩阵和邻接表； 邻接矩阵MDFS 深度优先遍历； 邻接矩阵MBFS 广度优先遍历 ； 邻接表LDFS 深度优先遍历； 邻接表LBFS 广度优先遍历 }

4

7. 参考文献 《数据结构》 8．附录

#include #include #include #include #define OK 1 #define ERROR 0

#define MAX_VERTEX_NUM 20

/**********************************图的基本操作**********************************/

int visited[MAX_VERTEX_NUM];

//------------------------------- 邻接矩阵数据类型的定义-------------------------------- {

char vexs[MAX_VERTEX_NUM]; int vexnum,arcnum;

// 顶点向量

// 邻接矩阵

int acrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; }MGraph ;

//--------------------------------邻接表数据类型的定义----------------------------------

5

// 访问标志数组

// 最大顶点个数

typedef struct

// 图当前顶点数和弧数

typedef struct ArcNode {

int adjvex;

// 该弧所指向的顶点的位置 // 指向下一条弧的指针

struct ArcNode *nextarc;

}ArcNode;

typedef struct VNode {

char data;

// 顶点信息

// 指向第一条依附该顶点的弧的指针

ArcNode *firstarc;

}VNode, AdjList[MAX_VERTEX_NUM]; typedef struct {

//_________________________________队列函数__________________________________________ typedef struct Queue {

int arry[MAX_VERTEX_NUM]; int front,rear; AdjList vertices; int vexnum,arcnum;

// 图当前顶点数和弧数

}LGraph;

}Queue; Queue Q; void InitQueue() { }

int QueueEmpty(Queue *Q) { }

void EnQueue(Queue *Q,int w)// 入队 {

// 队列初始化

Q.front=Q.rear=0;

// 清空队列

if(Q->front==Q->rear) else

return 0; return 1;

if((Q->rear+1)%MAX_VERTEX_NUM==Q->front) else {

Q->arry[Q->rear]=w;

6

printf("Error!");

}

int DeQueue(Queue *Q) { }

//____________________________________队列函数end_______________________________________ /**************************************************************************************** *函数：Create_Graph

*功能：建立图的邻接矩阵，邻接表

*说明：该构建的为无向网 mg 为邻接矩阵 ，lg 为邻接表 , 无权值

***************************************************************************************/ {

// 出队

int u;

return -1;

if(Q->front==Q->rear)

u=Q->front;

Q->front=(Q->front+1)%MAX_VERTEX_NUM; return u;

int Locatevex(MGraph *Mg , char v) { }

int i;

for(i=0;Mg->vexs[i]!=v;i++); if(i>Mg->vexnum) return i;

// 确定 v 元素在Mg 中的位置

// 输入的元素不正确则显示 错误 // 返回位置

printf("ERROR ");

int Create_Graph( MGraph *Mg , LGraph *Lg ) // 建立图的邻接矩阵，邻接表

int i , j , k ; char v1 , v2 ; ArcNode *q,*p;

printf("输入图的顶点数和弧数: "); getchar();

Lg->vexnum=Mg->vexnum; Lg->arcnum=Mg->arcnum;

for(i=0;ivexnum;i++) {

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

Lg->vertices[i].data=Mg->vexs[i]; // 赋值 Lg->vertices[i].firstarc=NULL;

// 指向第一条依附该顶点的弧的指针 为空

7

scanf("%d %d",&Mg->vexnum,&Mg->arcnum);

// 邻接表的顶点数和弧数

// 构造顶点向量

printf("请输入一个图的顶点(字符):");

}

/**************************************************************************************** *函数：LDFS

*功能：邻接表表示的图的递归深度优先遍历 *说明：

***************************************************************************************/

}

void LDFS(LGraph *Lg,int i) {

8

for(i=0;ivexnum;i++)

for(j=0;jvexnum;j++)

Mg->acrs[i][j]=0 ;

// 构造邻接矩阵和邻接表

// 初始化邻接矩阵

for(k=0;karcnum;k++) { }

return OK ;

printf("请输入一条边连接的2个顶点："); scanf("%c %c",&v1,&v2); getchar();

i=Locatevex(Mg,v1); j=Locatevex(Mg,v2);

// 确定 v1 在Mg 中的位置 // 确定 v2 在Mg 中的位置

Mg->acrs[j][i]=Mg->acrs[i][j]=1; // 置《v1,v2》的对称弧《v2,v1》 p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=i;

// 确认顶点位置 // 赋值

// 确认顶点位置 // 赋值

p->nextarc=Lg->vertices[j].firstarc;// 指向下一条弧的指针 Lg->vertices[j].firstarc=p; q->adjvex=j;

q=(ArcNode *)malloc(sizeof(ArcNode));

q->nextarc=Lg->vertices[i].firstarc;// 指向下一条弧的指针 Lg->vertices[i].firstarc=q;

int LAdjVex(LGraph *Lg,int k) {

ArcNode *p;

// 位置

for(p=Lg->vertices[k].firstarc;p!=NULL;p=p->nextarc)

if(!visited[p->adjvex])

return p->adjvex;

return -1;

}

/**************************************************************************************** *函数：MDFS

*功能：邻接矩阵表示的图的递归深度优先遍历 *说明：

***************************************************************************************/ { }

/**************************************************************************************** *函数：LBFS

*功能：邻接表表示的图的广度优先遍历 *说明：

***************************************************************************************/

void LBFS( LGraph *Lg ) {

printf("%c",Lg->vertices[i].data);

for(k=LAdjVex(Lg,i);k>=0;k=LAdjVex(Lg,k))

if(!visited[k])

LDFS(Lg,k);

int AdjVes(MGraph *Mg,int k) { }

int i;

for(i=0;ivexnum;i++)

// 位置

if(Mg->acrs[k][i]&&(!visited[i]))

return i;

return -1;

// 递归深度优先遍历

void MDFS(MGraph *Mg,int i)

int k; visited[i]=1;

// 访问标志数组某位 置 1 // 显示

printf("%c",Mg->vexs[i]);

if(!visited[k])

MDFS(Mg,k);

for(k=AdjVes(Mg,i);k>=0;k=AdjVes(Mg,k))

// 递归

int i,u,w;

for(i=0;ivexnum;++i)

visited[i]=0;

// 初始化 队列 // 没被访问过

9

// 初始化 visited[]

InitQueue();

for(i=0;ivexnum;++i)

if(!visited[i]) {

}

/**************************************************************************************** *函数：MBFS

*功能：邻接矩阵表示的图的广度优先遍历 *说明：

***************************************************************************************/ void MBFS(MGraph *Mg ) {

}

EnQueue(&Q,i); { }

u=DeQueue(&Q);

if(!visited[w]) { }

visited[w]=1;

printf("%c",Lg->vertices[w].data); EnQueue(&Q,w);

// 入队

// 出队

for(w=LAdjVex(Lg,u);w>=0;w=LAdjVex(Lg,u))

// 没被访问过

// 入队

while(!QueueEmpty(&Q))

int i,w,u;

for(i=0;ivexnum;i++)

visited[i]=0;

// 初始化队列 // 没被访问过

InitQueue();

// 初始化 visited[]

for(i=0;ivexnum;++i)

if(!visited[i]) {

visited[i]=1;

printf("%c",Mg->vexs[i]); EnQueue(&Q,i); {

u=DeQueue(&Q);

// 出队

for(w=AdjVes(Mg,u);w>=0;w=AdjVes(Mg,u))

// 没被访问过

{ }

10

// 显示

// 入队

while(!QueueEmpty(&Q))

if(!visited[w])

visited[w]=1;

printf("%c",Mg->vexs[w]);

// 显示 // 入队

EnQueue(&Q,w);

福建师范大学物光院计算机教学辅导讲义

}

/***************************************主函数*******************************************/ void main()

{

printf("\n邻接表LBFS 广度优先遍历：\t"); LBFS(&Lg) ; printf("\n");

● 每位同学必须完成实验任务，并提交实验报告。杜绝抄袭和拷贝，一经发现该次实验雷同报告均以零分计。

● 请将实验报告以电子文档提交， “网络工程”专业请发送到[email protected]信箱中，“电子信息”专业请发送到[email protected] 信箱中，请附上程序清单.C 源程序文件、和实验报告WORD 文档两部分，以打包压缩文件形式提交，每次实验为一个文件夹的打包压缩文件，文件夹名统一为*⊙⊙⊙??.rar 或*⊙⊙⊙??.zip ，其中*为你的学号（全部号码），⊙⊙⊙为你中文姓名，?? 分别为01，02，03……11表示第几次实验。

11 } } int i ; MGraph Mg; LGraph Lg; Create_Graph( &Mg, &Lg); printf("邻接矩阵MDFS 深度优先遍历：\t"); for(i=0;i


相关文章

  • 20130515基本农田数据库成果汇交要求

    • 基本农田数据库成果汇交要求 根据<基本农田数据库标准>(调整试行版)(以下简称<调整版>),结合各地基本农田数据库建设的实际情况,对各省级汇交到部的基本农田数据库成果提出以下要求: 一.数据内容和数据格式 以县为基本 ...查看


  • 数据结构A教学大纲

    • 数据结构A 教学大纲 (Data Structures A) 课程编号: 06311360 学 分: 5.0 学 时: 75 (其中:讲课学时:60 实验学时:0 上机学时:15) 先修课程:离散数学.程序设计基础.面向对象程序设计 适用专 ...查看


  • 餐饮管理系统_详细设计(MS)1

    • 文档编号: 版 本 号: 文档名称: 详细设计说明书 项目名称: 餐饮管理系统 开发小组成员: 编写人: 评 分: 教 师: 评分日期: 年 月 日 目录 1．引言...................................... ...查看


  • 就业信息管理子系统

    • 就业信息系统 目录 1 引言 ......................................................................................................... ...查看


  • 软件技术基础知识要点复习

    • 软件技术基础知识要点复习 1.软件的概念,软件的特性,软件的分类图1-5,软件的内容?图1-6 概念:软件是"与计算机系统操作有关的程序.过程.规则,以及任何有关的文档资料和数据". 或软件是程序.数据及相应文档所组成的 ...查看


  • 基本农田划定实施方案

    • ***基本农田划定 工作方案 二〇一二年六月 目 录 一.指导思想 ...................................................................................... ...查看


  • 数据库原理期末考试习题

    • 第一章 绪论 一.选择题: 1.使用二维表格结构表达数据和数据间联系的数据模型是(C ) C .关系模型 2.DB .DBS .DBMS 间的关系是(C ) A .层次模型 B .网状模型 D .实体-联系模型 A .DB 包括DBMS 和 ...查看


  • 数据库及应用复习题

    • 数据库及应用复习题 一. 填空题 1. 2. 3. 在查询分析器中运行SQL 语句可以用__F5__功能键. 保存当前的查询命令或查询结果文件的扩展名为_____.sql______. 函数DATEDIFF ()功能是计算两个日期间的距离. ...查看


  • 教学管理系统标准论文

    • 课程设计报告 教学信息管理系统 学 院 年级专业 学生姓名 指导教师 提交日期 青岛大学经济学院课程设计报告 摘 要 本文简要阐述了教学管理系统建设的意义以及系统的分析设计过程.从用户的角度出发,对教学管理系统的功能进行了全面的分析.本系统 ...查看


  • 数据结构中的名词解释

    • 本章主要介绍了如下一些基本概念:  数据结构:数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中 的存储表示(即所谓数据的逻辑结构和物理结构),并对这种结构定义相适应的运算,设计出相应的算法,而且确保经过这些运算后所得到的新结 ...查看


热门内容