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

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