求一个无向图G的连通分量的个数

2021年2月1日发(作者：坦桑石)

.

《数据结构》实验报告

实验内容：

（一）判断一个图有无回路

（二）求一个无向图

G

的连通分量的个数

一、

目的和要求（需求分析）

：

1

、

了解图的定义和图的存储结构。

2

、

熟悉掌握图的邻接矩阵和邻接表。

3

、

理解图 的遍历算法

---

深度优先搜索和广度优先搜索。

4

、

学会编程处理图的连通性问题。

二、程序设计的基本思想，原理和算法描述：

（包括程序的结构，数据结构，输入

/

输出设计，符号 名说明等）

判断一个图有无回路：

在程序设计中，

先必须确定所要创建的图是有向还是无向，

是图还是网，

其次再根据各

自的特点，用连 接表来实现创建。

在有向图中，先找出入度为

0

的顶点，删除与这个顶点相关联的边（出边）

，将与 这些

边相关的其它顶点的入度减

1

，循 环直到没有入度为

0

的顶点。如果此时还有未被删除的顶

点，则必然存在环路，否则不存在回路。

无向图则可以转化为：

如果存在回路 ，则必然存在一个子图，是一个回路。因此回路中所有定点的度

>=2

< br>。

第一步：

删除所有度

<=1

的顶点及相关边，

并将另外与这些边相 关的其它顶点的度减

1

。

< p>
第二步：将度数变为

1

的顶点排入队列，并从该队 列中（使用栈）取出一个顶点，并重

复步骤一。

如果最后还有未删除的顶点，则存在回路，否则没有。

求一个无向图

G

的连通分量的个数：

用连接表创建图，

对于非连通图，

< p>
则需从多个顶点出发进行搜索，

而每一次从一个新的

起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。

所以 在设

计中，为了统计出无向图中的连通分量个数，则因在其深度优先所搜无向图时对函数

DFSTraverse(ALGraph G)

调用

DFS

次数进行统计，其结果便为无向图中连通分量个数。

三、调试和运行程序过程中产生的问题及采取的措施：

在调试和运行求一个无向图

G

的连通分量的个 数程序时，由于执行语句块

void DFSTraverse(ALGraph G)

先于

void DFS(ALGraph G,int v)

，

而

void

DFSTraverse(ALGraph

G)

内调用了

DFS(

)

，因此计算机无法正确运行，将两者

顺序进行了交 换，程序便实现了其功能，且运行正常。

四、源程序及注释：

.

.

判断一个图有无回路：

#include

#include

#include

//

输出有向图的一个拓扑序列。

//

图的邻接表存储表示

#define MAX_NAME 3

//

顶点字符串的最大长度

+1

#define MAX_VERTEX_NUM 20

#define STACK_INIT_SIZE 10

//

存储空间初始分配量

#define STACKINCREMENT 2

//

存储空间分配增量

typedef int InfoType;

//

存放网的权值

typedef char VertexType[MAX_NAME];

//

字符串类型

typedef enum{DG,DN,AG,AN}GraphKind; // {

有向图

,

有向网

,

无向图

,

无向网

}

typedef struct ArcNode

{

int adjvex;

//

该弧所指向的顶点的位置

struct ArcNode *nextarc;

//

指向下一条弧的指针

InfoType *info;

//

网的权值指针）

}ArcNode;

//

表结点

typedef struct VNode

{

VertexType data;

//

顶点信息

ArcNode *firstarc;

//

第一个表结点的地址

,

指向第一条依附该顶点

的弧的指针

< p>

}VNode,AdjList[MAX_VERTEX_NUM];//

头结点

typedef struct

{

AdjList vertices;

int vexnum,arcnum;

//

图的当前顶点数和弧数

int kind;

//

图的种类标志

}ALGraph;

//

若

G

中存在顶点

u,

则返回该顶点在图中位置

;

否则返回< /p>

-1

。

int LocateVex(ALGraph G,VertexType u)

{

int i;

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

if(strcmp(u,es[i].data)==0)

return i;

.

.

return -1;

}

//

采用邻接表存储结构

,

构造没有相关信息的图

G(

< br>用一个函数构造

4

种图

)

。

int CreateGraph(ALGraph *G)

{

int i,j,k;

int w;

//

权值

VertexType va,vb;

ArcNode *p;

printf(

请输入图的类型

(

有向图

:0,

有 向网

:1,

无向图

:2,

无向网

:3):

scanf(

printf(

请输入图的顶点数和边数

:

（空格）

n

scanf(

< /p>

printf(

请输入

%d

个顶点的值

(

小于

%d

个字符

):n

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

//

构造顶点向量

{

scanf(

(*G).vertices[i].firstarc = NULL;

}

if((*G).kind == 1 || (*G).kind == 3) //

网

< /p>

printf(

请顺序输入每条弧

(

边

)

的权值、

弧尾 和弧头

(

以空格作为间隔

):n

else //

图

< /p>

printf(

请顺序输入每条弧

(

边

)

的弧尾和弧头

(

以空格作为间隔

):n

for(k = 0;k < (*G).arcnum; ++k) //

构造表结点链表

{

if((*G).kind==1||(*G).kind==3) //

网

scanf(

else

//

图

scanf(

i = LocateVex(*G,va); //

弧尾

j = LocateVex(*G,vb); //

弧头

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

p->adjvex = j;

if((*G).kind == 1 || (*G).kind == 3) //

网

{

p->info = (int *)malloc(sizeof(int));

*(p->info) = w;

}

else

p->info = NULL; //

图

p->nextarc = (*G).vertices[i].firstarc; //

插在表头

(*G).vertices[i].firstarc = p;

.

.

if((*G).kind >= 2) //

< p>
无向图或网

,

产生第二个表结点

< br>

{

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

p->adjvex = i;

if((*G).kind == 3) //

无向网

{

p->info = (int*)malloc(sizeof(int));

*(p->info) = w;

}

else

p->info = NULL; //

无向图

p->nextarc = (*G).vertices[j].firstarc; //

插在表头

(*G).vertices[j].firstarc = p;

}

}

return 1;

}

void Display(ALGraph G) //

输出图的邻接表

G

。

{

int i;

ArcNode *p;

switch()

{

case DG: printf(

有向图

n

break;

case DN: printf(

有向网

n

break;

case AG: printf(

无向图

n

break;

case AN: printf(

无向网

n

}

printf(

个顶点：

n

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

printf(

printf(

条弧

(

边

):n< /p>

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

{

p = es[i].firstarc;

while(p)

{

if( <= 1) //

有向

{

.

.

printf(

→

%s

es[p->adjvex].data);

if( == DN) //

网

printf(

}

else

//

无向

(

避免输出两次

)

{

if(i < p->adjvex)

{

printf(

－

%s

es[p->adjvex].data);

if( == AN)

//

网

printf(

}

}

p=p->nextarc;

}

printf(

}

}

void FindInDegree(ALGraph G,int indegree[]) //

求顶点的入度。

{

int i;

ArcNode *p;

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

indegree[i]=0; //

赋初值

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

{

p=es[i].firstarc;

while(p)

{

indegree[p->adjvex]++;

p=p->nextarc;

}

}

}

typedef int SElemType; //

栈类型

typedef struct SqStack //

栈的顺序存储表示

{

SElemType *base;

//

在栈构造之前和销毁之后，

ba se

的值为

NULL

SElemType *top;

//

栈顶指针

.

.

int stacksize;

//

当前已分配的存储空间，以元素为单位

}SqStack;

//

顺序栈

int InitStack(SqStack *S) //

构造一个空栈

S

{

//

为栈底分配一个指定大小的存储空间

(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));

if( !(*S).base )

exit(0);

//

存储分配失败

(*S).top = (*S).base;

//

栈底与栈顶相同表示一个空栈

(*S).stacksize = STACK_INIT_SIZE;

return 1;

}

//

若栈

S

为空栈（栈顶与栈底相同的）

，则返回

1

，否则返回

0

。

< br>

int StackEmpty(SqStack S)

{

if( == )

return 1;

else

return 0;

}

int Push(SqStack *S, SElemType e) //

插入元素

e

为新的栈顶元素。

{

if((*S).top - (*S).base >= (*S).stacksize)

//

栈满，追加存储空间

{

(*S).base = (SElemType *)realloc((*S).base,

((*S).stacksize + STACKINCREMENT) * sizeof(SElemType));

if( !(*S).base )

exit(0); //

存储分配失败

(*S).top = (*S).base+(*S).stacksize;

(*S).stacksize += STACKINCREMENT;

}

*((*S).top)++=e;

//

这个等式的

++ *

优先级相同，但是它们的运算方式，是自右向左

return 1;

}

//

若栈不空，则删除

< p>
S

的栈顶元素，用

e

返回 其值，并返回

1

；否则返回

0

。

int Pop(SqStack *S,SElemType *e)

{

if((*S).top == (*S).base)

return 0;

.