数据结构-求有向图的所有简单回路讲解

2021年2月1日发(作者：草莓的英文)

课

程

设

计

报

告

课程设计名称：

数据结构课程设计

< /p>

课程设计题目：

求有向图的所有简单回路

院（系）：计算机学院

专

业：计算机科学与技术（嵌入式方向）

班

级：

学

号：

姓

名：

指导教师：

I

目

录

沈阳航空航天大学

................... .................................................. ...

错误！未定义书签。

1

总体设计

........... .................................................. .................................................. ..... 1

1.1

课设要求

........... .................................................. ................................................. 1

1.2

设计原理

....................... .................................................. ..................................... 1

2

详细设计

....................... .................................................. ........................................... 2

2.1

算法与程序的设计与实现

................ .................................................. ................ 2

2.1.1

算法描述

....... .................................................. ................................................. 2

2.1.2

数据结构设计及用法说明

.................................................. ............................ 3

2.2

流程图的设计与实现

.................. .................................................. ...................... 5

3

核心数据结构函数的描述

.... .................................................. .................................. 7

3.1

建立邻接表的函数

................... .................................................. ......................... 7

3.2

深度优先遍历函数

................... .................................................. ......................... 9

4

程序测试及结果分析

.................. .................................................. ...........................

1

1

4.1

程序测试及结果

.................... .................................................. ...........................

1

1

参考文献

....................... .................................................. ............................................... 14

附

录（关键部分程序清单）

.... .................................................. ............................ 15

II

1

总体设计

1.1

课设要求

以合适方便的方式输入一个有向图，

并在内部建立有向图的邻接表储存结构，

< p>
有邻接表的形式储存有向图。然后根据有向图的储存结构，求出该有向图中所有

的简单回路。

输入有向图的方式简单方便，

能形象方便的观 察有向图的顶点名称，

相关弧的关系。

要求如下：

（

1

）熟悉图的邻接表储存结构及操作方式；

（

2

）熟悉求简单回路的算法（利用深度优先遍历）< /p>

；

（

3

）熟悉运用开发环境，基于

VC++6.0

的 软件开发环境；

（

4

）完成课程设计基本任务的设计及编码；

（

5

）熟练掌握

VC++6.0

< br>上的基本的调试方法。

1.2

设计原理

根据所学的知识，在利用邻 接表时需要做三个工作：定义表结点类型；定义

头结点类型；定义邻接表类型。再对储存 的图进行深度优先遍历，并将遍历过的

点进行标记，

放入数组储 存，

当发现有被标记的点出现时则表示出现重复的顶点，

为找到 回路，打印出有向图的回路。

1

2

详细设计

2.1

算法与程序的设计与实现

在得到该课程设计任务书时，在对求有向图的所有简单回路的算法知识做了

简单的回顾与学习。首先是邻接表储存有向图，由于有向边没有权值，所有在建

立有向 图的邻接表的时候去除了有关弧的信息。其次才用深度优先遍历的算法遍

历有向图中所有 的顶点，在遍历有向图时，对图中每个顶点至多调用一次

DFS

函

数，

因为一旦某个顶点被标记成为已被访问，

就不再从它出发进行搜索了。

因此，

遍历有向图的过程 实质上是对每个顶点查找其邻接点的过程。

2.1.1

算法描述

（

1

）邻接表：

邻接表是图的 一种链式存储结构。

在邻接表中，对图中每个顶

点建立一个单链 表，第

i

个单链表中的接点表示依附于顶点

Vi

的边（对有向图是

以顶点

Vi

为尾的弧）

。每个结点由

3

< p>
个域组成，其中邻接点域（

adjvex

）指示与

顶点

Vi

邻接的点在图中的位置，链域 （

nextare

）指示下一条边或弧的结点；数据

< p>
域（

info

）储存和边或弧相关的信息，如权值 等。每个链表上附设一个表头结点。

在表头结点中，除了设有链域（

firstarc

）指向链表中第一个结点之外，还设有储

存顶点

Vi

的名或其它有关信息的数据域（

data

）

。如下图所示：

adjvex

nextarc

图

2.1.1

表结点

info

data

firstarc

图

2.1.2

头结点

（

2

）深度优先遍历：设

x

是当前被访问顶 点，在对

x

做过访问标记后，

选择一条 从

x

出发的未检测过的边

(x

，

y)

。若发现顶点

y

已访问过，则重新

选择另一条从

x

出发的未检测过的边，

否则沿边

(x

，

y)

到达未曾访问过的

y

，

对

y

访问并将其标记为已访问过；然后从

y

开始搜索，直到搜索完从

y

出发

2

的所有路径，即访问完所有从

y

出发可达的顶点之后，才回溯到顶点

x< /p>

，并

且再选择一条从

x

< br>出发的未检测过的边。

上述过程直至从

x

出发的所有边都

已检测过为止。此时，若

x

< p>
不是源点，则回溯到在

x

之前被访问过的顶点；< /p>

否则图中所有和源点有路径相通的顶点

(

即从源点可达的所有顶点

)

都已被

访问 过，若图

G

是连通图，则遍历过程结束，否则继续选择一个尚未 被访问

的顶点作为新源点，进行新的搜索过程。

在本次课程设计中还需要对深度优先遍历进行递归，

关于深度优先遍历

的递归，首先访问出发点

v

，并将其标记为已 访问过；然后依次从

v

出发搜

索

v

的每个邻接点

w

。 若

w

未曾访问过，则以

w

为新的出发点继续进行深度

优先遍历，直至图中所有和源点

< br>v

有路径相通的顶点

(

称为从源 点可达的顶

点

)

均已被访问为止。

2.1.2

数据结构设计及用法说明

（

1

）邻接表的形式说明及其建表算法 ：

通过表头结点（可以链相接）通常以顺序结构的形式储存， 以便随机访

问任一顶点的链表。一个邻接表储存结构可以定于如下：

//

边表结点

Typedef struct ArcNode{

int adjvex;//

邻接点域

struct node *nextarc; //

链域

InfoType *info//

若要表示边上的权，则应增加一个数据域

} ArcNode;

//

顶点表结点

typedef struct vnode{

VertexType data;//

顶点域

EdgeNode *firstarc;//

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

}VertexNode;

//AdjList

是邻接表类型

typedef VertexNode AdjList[MaxVertexNum];

typedef struct{

AdjList adjlist;//

邻接表

3

int n

，

e;//

图中当前顶点数和边数

}ALGraph;

（

< p>
2

）深度优先遍历的算法说明：

在遍历图时，

对图中每个顶点至多调用一次

DFS

函数，

因为一旦某个顶点被

标记成为已被访 问，就不再从它出发进行搜索了。因此，遍历图的过程实质上是

对每个顶点查找其邻接点 的过程。

Boolean visited[MAX];//

访问标志数组

Status

（

* VisitFunc

）

（

int v< /p>

）

;//

函数变量

void DFS

（

Graph G

，

int v

）

｛

//

从第

v

个顶点出发递归地深度优先遍历 图

G

visited[v] = TURE;

VisitFunc

（

v

）

;//

访问第

v

个顶点

for

（

< br>w=FirstAdjVex(G,v);w>=0

；

w =NextAdjVex

（

G

，

v

，

w

）

< p>
）

if

（！

< p>
visited[w]

）

DFS

< br>（

G

，

w

）

｝

4

2.2

流程图的设计与实现

（

1

）建立邻接表流程图如下：

Y

结束

图

2.2.1

建立邻接表流程图

开始

输入顶点个数和弧的条数

输入顶点名称

Y

是否重复

N

输入弧的信息，

弧的起点与终点

Y

是否重复

N

根据顶点信息，

将弧赋予当前指< /p>

针和指向下一弧的指针

建立结点和顶点链表

N

是否弧已全部进行操作

5

（

2

）深度优先遍历的流程图如下：

N

图

2.2.2

深度遍历流程图

6

开始

将顶点全部初始化为未遍历

将当前顶点指针指向根顶点

对当前顶点进行操

作并标记为遍历

获取当前顶点的下

一个子顶点

将当前指针指向该顶点

N

是否获得

Y

将当前顶点放入数

组保存，然后将 当

前指针指向获得的

顶点

从顶点数记录中减一

回到上一顶点

对当前顶点进行操作

是否该顶点周围的

子顶点都已遍历

该顶点是否与第

一个顶点相同

Y

输出保存有顶点信

息的数组

N

Y

结束

3

核心数据结构函数的描述

3.1

建立邻接表的函数

函数名称：

int CreateADG(ALGraph &g)

函数功能：实现在键盘上输入有向图顶点数、顶点名称（用整数表示，如

1

就表

示顶点

1

）

、弧数以及弧的顶点与起点，并用邻接表储存图。

函数具体代码如下：

int CreateADG(ALGraph &g){

int i,j,k,l;

ArcNode *p;

int v1,v2;

int c;

printf(

请输入有向图的顶点数

:

scanf(

i=*(-1);

printf(

请输入有向图的边数

:

scanf(

getchar();

printf(

请依次输入有向图的各个顶点

:

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

{

scanf(

l=locateALG(g,c);

if(l>=0)

{

printf(

输入的顶点重复，请重新输入

n

i--;

continue;

7

}

es[i].data=c;

es[i].firstarc=NULL;

}

for(k=0;k<;k++)

{

printf(

请输入第

%d

条弧的起点与终点

< p>
(

用逗号分隔

)

：

scanf(

i=locateALG(g,v1);

j=locateALG(g,v2);

if(i<0||j<0||i==j||(<0))

{

k--;

continue;

}

p=(ArcNode*)m alloc(sizeof(ArcNode));//

建立结点

if(!p)

return -1;

p->adjvex=j;

p->nextarc=es[i].firstarc;//

顶点

i

的链表

es[i].firstarc=p;//

添加到最左边

}

printf(

有向图的邻接表创建成功

nn

return 1;

}

8

3.2

深度优先遍历函数

函数名称：

void dfs(ALGraph G,int cur,int* save,int size)

函数功能：实现从选定的顶点开始 对有向图进行深度优先遍历，函数中

g

为

当前要搜索的图，

cur

为当前搜索的顶点的下标，

save

是一个数组，用来保存搜

索过的顶点，

size

为

save

< br>数组的大小。在遍历中将遍历的顶点放入

save

中，当

搜索到的顶点回到起点时，为找到回路，打印出有向图的回路。

函数的具体代码如下：

void dfs(ALGraph G,int cur,int* save,int size)

{

int i;

ArcNode *p=es[cur].firstarc;

save[size]=cur;

while(p)

{

if(save[0]==p->adjvex)

{

count++;

printf(

第

%d

条回 路

for(i=0;i

{

printf(

}

printf(

}

else if(flag[p->adjvex]==0)

{

flag[p->adjvex]=1;

dfs(G,p->adjvex,save,size+1);

9