数据结构课设有向图强连通分量求解

沈阳航空航天大学

课程设计报告

课程设计名称：数据结构课程设计

课程设计题目：有向图强连通分量求解

院（系）：计算机学院

专业：网络工程

班级：

学号：

姓名：

指导教师：

沈阳航空航天大学课程设计报告

目录

1 算法分析 (2)

1.1假设条件 (2)

1.2算法描述 (2)

1.2.1 有向图的存储结构 (2)

1.2.2 深度优先遍历 (3)

1.2.3 求解强连通分量 (3)

2 系统设计 (4)

2.1设计说明 (4)

2.2数据结构描述 (4)

2.3 MAIN()函数 (5)

2.4邻接表和逆邻接表的建立 (7)

2.5邻接表的遍历 (8)

2.6逆邻接表的遍历 (9)

3 系统实现 (12)

3.1错误分析 (12)

3.2实现结论 (12)

参考文献 (13)

附录（关键部分程序清单） (14)

1 算法分析

1.1假设条件

有向图的强连通分量是有向图中的最大强连通子图。而对于一个有向图G，如果对于每一对的Vi和V j∈V，Vi≠V j，从Vi到V j和V j到Vi都存在路径，则称G是强连通图。

有向图强连通分量求解的设置分为存储、输入以及输出三大部分。

（1）算法的存储分为对有向图的顶点的存储，对有向图的弧的存储和对整个有向图的链式存储。

（2）输入分为三大部分：第一，输入有向图的顶点数以及弧条数（均为整数）；第二，输入各个顶点的信息（均为字符型）；第三，输入每一条弧的弧尾与弧头所对应的顶点信息，即对各顶点进行链式存储时的顶点信息，并以输出0 0 为结束标志。

（3）算法的输出为该有向图的所有强连通分量（以集合的形式表示）以及该有向图是否是强连通图。

1.2算法描述

该算法是为了实现输入一有向图到适当的存储结构中，判断该有向图是否强连通，若不是强连通图则求出该图的所有强连通分量并输出。

1.2.1 有向图的存储结构

对于输入的有向图，利用链式的存储结构进行存储即对有向图的顶点、弧以及有向图进行链式的存储。

有向图顶点的存储中包含邻接点域(adjvex)指示与顶点Vi邻接的点在图中的位置和链域(next)指示下一条弧的结点。有向图的弧的存储包含存储顶点Vi信息数据域(data)以及指向第一条依附该顶点的弧的指针(firstarc)指向链表中第一个结点。有向图的存储包含存储顶点的链表的最大长度，当前顶点数以及弧数。创建一个新的有向图就要输入图所包含的顶点数，弧条数，各顶点信息以及每条弧的弧尾和

弧头所对应的顶点序号，并以输入0 0 为结束的标志。

1.2.2 深度优先遍历

假设初始状态为图中所有顶点都未被访问即flag[m]=0,则从图中的某个顶点出发，访问此顶点，对有向图的邻接表和逆邻接表进行深度优先遍历，并令flag[m]=1表示该结点已经被访问。当该结点未被访问时利用递归再对其进行访问,直到图中所有顶点都被访问到为止。

1.2.3 求解强连通分量

深度优先遍历是求解有向图的强连通分量的一个新的有效方法。

（1）对于以链式存储的有向图G，从某个顶点出发沿以该顶点为尾的弧进行深度优先搜索遍历，并按其所有邻接点的搜索都完成的顺序将顶点排列起来。

（2）再从最后完成搜索的顶点出发，沿着以该顶点为头的弧作逆向的深度优先遍历，若此次遍历不能访问到有向图中所有的顶点，则从余下的顶点中最后完成搜索的那个顶点出发，继续作逆向的深度优先遍历，依此类推，直至有向图中所有顶点都被访问到为止。

由此，每一次调用DFS作逆向深度优先遍历所访问到的顶点集便是有向图G 中一个强连通分量的顶点集。

例如，图1.2.2所示的有向图，假设从顶点V1出发作深度优先搜索遍历，得到finished数组中的顶点号为（2,4,3,1）；则再从顶点V1出发作逆向的深度优先搜索遍历，得到顶点集{V1，V3，V4}和{V2}，这就是该有向图的两个强连通分量的顶点集。

2 系统设计

2.1设计说明

该算法设计共包含五大模块，即：有向图的主函数模块，链式存储模块，建立有向图的原图的邻接表和逆邻接表模块，深度优先遍历原图的邻接表模块，深度优先遍历原图的逆邻接表模块。主函数模块调用原图的邻接表和逆邻接表两个深度优先遍历的函数。函数模块关系如图2. 1.1所示：

2.2数据结构描述

该函数包含三个结构体，即存储弧、存储顶点和存储图的结构体。其结构体分别如下所示：

存储弧的结构体,其中包含两个变量adjvex和指针next，adjvex指示与顶点Vi邻接的点在图中的位置和next指示下一条弧的结点：

typedef struct ArcNode{

int adjvex;

struct ArcNode *next;

}ArcNode;

存储顶点的结构体,其中包含两个变量data和指针firstarc，存储顶点Vi

信息数据域(data)以及指向第一条依附该顶点的弧的指针(firstarc)指向链表中第一个结点：

typedef struct Vnode{

char data;

ArcNode *firstarc;

} Vnode ;

存储图的结构体,其中包含存储顶点表的最大长度值及变量顶点数和弧条数，存储顶点的链表的最大长度，当前顶点数vexnum以及弧数arcnum：

typedef struct ALGraph{

Vnode list[MAX];

int vexnum ,arcnum;

}ALGraph;

2.3 main()函数

创建一个有向图，对建立的有向图的邻接表及逆邻接表进行深度优先遍历。从而求解出该有向图的强连通分量，并判断该有向图是否为强连通图，输出该有向图的强连通分量的顶点集。主函数流程图如图2.3.1所示：

2.4邻接表和逆邻接表的建立

用函数creatgraph(&G1，&G2)建立有向图的邻接表G1和逆邻接表G2。输入该有向图的顶点数和弧条数，各顶点的信息及每条弧的弧尾和弧头所对应的顶点序号并以0 0作为其结束的标志。其流程图如图2.4.1所示：

2.5邻接表的遍历

利用DFSTraverse1（&G1，m）函数和对有向图的邻接表进行深度优先遍历，并用flag[m]=1表示已经遍历过该结点，flag[m]=0表示该结点未被遍历。若该结点未被遍历即flag[m]=0，则利用递归调用DFS1（&G1,m）函数从该结点出发对有向图进行深度优先遍历，直到访问完该有向图中的所有顶点。该遍历流程图如图2.5.1和图2.5. 2所示：

2.6逆邻接表的遍历

利用DFSTraversel2（&G2，m）函数对有向图的逆邻接表进行深度优先遍历，

并同2.5节中一样利用flag[m]=1标记已经遍历过的结点，flag[m]=0标记未被遍历的结点，再对该结点利用递归调用DFS2（&G2，m）函数从该结点出发对有向图进行深度优先遍历。最后输出该有向图的强连通分量（顶点集形式）。这部分算法的流程图如图2.6.1和图2.6.2所示：

3 系统实现

3.1错误分析

（1）算法在执行过程中，输入结点的信息时，如果输入的结点格式不对称即输入时结点间间隔不一致，都将导致不能输入每条弧的弧头和弧尾信息而直接输出该有向图是否为有向图的结论和强连通分量的顶点集。例如输入顶点数为4，弧的条数为5，输入顶点信息为a b c d时，若将输入的格式变为（a b c d ），则下一步将直接跳过对每一条弧的弧头和弧尾的输入而输出结果：{}{b}{}{}及“该图不是强连通图！”。而对于其他的一些实现时并无什么语法的错误。

（2）编写算法时，对函数DFS1(ALGraph &G,int m)忘记声明，导致程序无法调用该函数，运行出现错误，经过改正后，运行成功。

（3）输入顶点数时，未考虑顶点的最大数目，从而导致数组越界，程序无法正常运行。改正时可将输入的顶点数目减小或者将MAX值增大，消除数组越界，使程序正常运行。

（4）对于一直困扰自己的遍历邻接表的作用是什么的问题，经过查阅资料，和同学一起讨论和思考，只能得出自己的初步解释。因为，深度优先遍历邻接表是为了求出finished[m]数组中的所有值，从而为逆邻接表的深度优先遍历寻找到起始的数值，从而控制算法的运行。实验中，我将邻接表的遍历函数删除后得出结果只有该有向图是否为强连通图，而无法求出其强连通分量。对于其本质原因，只能进一步去学习或者向老师请教。

3.2实现结论

该算法实现了输入一个有向图到适当的存储结构中，判断出该有向图是否为强连通图，如果不是时则求出该有向图的所有的强连通分量并输出。而且对于任意一个按要求输入的有向图都能将该有向图的所有强连通分量以结点集的形式输出。该实验需要改进的地方时将输出变成以有向图的形式输出。但由于个人水平有限，无法实现该功能。

参考文献

[1] 严蔚敏，吴伟民. 数据结构（C语言版）［M］. 北京：清华大学出版社，2006

[2] 张千帆. 数据结构与算法（C语言实现）[M] . 北京：科学出版社，2009

[3] 吕国英. 算法设计与分析[M] . 北京：清华大学出版社，2006

[4] 徐宝文李志. C程序设计语言[M] . 北京：机械工业出版社，2004

附录（关键部分程序清单）

#include #include

#define MAX 20 #define NULL 0

typedef struct ArcNode{ int adjvex; struct ArcNode *next;

}ArcNode;

typedef struct Vnode{ char data; ArcNode *firstarc;

}Vnode;

typedef struct ALGraph{ Vnode list[MAX]; int vexnum,arcnum;

}ALGraph;

int flag[MAX],finished[MAX],a[MAX];

int count=0;

void creatgraph(ALGraph &G1,ALGraph &G2)

{ int i,j,v,a; ArcNode *p1,*p2;

char ch;

printf("请输入顶点数和弧条数\n");

scanf("%d %d",&v,&a);

getchar();

G1.vexnum=G2.vexnum=v; G1.arcnum=G2.arcnum=a;

printf("请输入顶点信息\n");

for(i=1;i<=v;i++){ scanf("%c",&ch);

getchar();

G1.list[i].data=G2.list[i].data=ch;

G1.list[i].firstarc=G2.list[i].firstarc=NULL; } printf("请输入每条弧的弧尾和弧头所对应的顶点序号,以输入0 0作为结束标志\n");

scanf("%d %d",&i,&j);

while((i>0)&&(j>0)){ p1=(ArcNode*)malloc(sizeof(ArcNode));

p1->adjvex=j;

p1->next=G1.list[i].firstarc;

G1.list[i].firstarc=p1;

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

p2->adjvex=i;

p2->next=G2.list[j].firstarc;

G2.list[j].firstarc=p2;

scanf("%d %d",&i,&j);

} }

void DFS1(ALGraph &G,int m)

{ ArcNode *p; int i; flag[m]=1;

p=G.list[m].firstarc;

while(p!=NULL){

i=p->adjvex;

if(flag[i]==0)

DFS1(G,i);

p=p->next; }

finished[++count]=m; }

void DFStraverse1(ALGraph &G)

{ int i,v; v=G.vexnum;

for(i=1;i<=v;i++)

flag[i]=0;

for(i=1;i<=v;i++)

if(flag[i]==0)

DFS1(G,i); }

void DFS2(ALGraph &G,int m)

{ ArcNode *p; int i; flag[m]=1;

printf("%c",G.list[m].data);

p=G.list[m].firstarc;

while(p!=NULL){

i=p->adjvex;

if(flag[i]==0)

DFS2(G,i);

p=p->next; } }

void DFStraverse2(ALGraph &G)

{int i,v,n,j; v=G.vexnum;

for(i=1;i<=v;i++)

flag[i]=0;

for(i=count;i>=1;i--){ n=finished[i];

if(flag[n]==0){ printf("{");

DFS2(G,n);

printf("}"); }

if(i==count)

for(j=count;j>=1;j--)

a[j]=flag[j]; } } void main( )

{int j,s; ALGraph G1,G2; creatgraph(G1,G2); DFStraverse1(G1); DFStraverse2(G2); j=count; s=1; while(j>=1){ if(a[j]==1)

j--;

else {s=0;break;} }

if(s==1)

printf("\n该图是强连通图!\n");

else

printf("\n该图不是强连通图!\n");

printf("\n");}

沈阳航空航天大学课程设计报告

图的连通性总结

图的连通性总结 boboo 目录 1.图的遍历及应用 1.1.DFS遍历 1.2.DFS树的边分类 1.3.DFS树的性质 1.4.拓补排序 1.5.欧拉回路 2.无向图相关 2.1求割顶 2.2求图的桥 2.3求图的块 3.有向图相关 3.1求强连通分量（SCC划分） 3.2求传递闭包 4.最小环问题

一、图的遍历及应用 1.1 DFS遍历 DFS是求割顶、桥、强连通分量等问题的基础。 DFS对图进行染色， 白色：未访问； 灰色：访问中（正在访问它的后代）； 黑色：访问完毕 一般在具体实现时不必对图的顶点进行染色，只需进行访问开始时间和访问结束时间的记录即可，这样就可以得出需要的信息了。 -发现时间D[v]:变灰的时间 -结束时间f[v]:变黑的时间 -1<=d[v]

数据结构课程设计报告模板

《数据结构I》三级项目报告 大连东软信息学院 电子工程系 ××××年××月

三级项目报告注意事项 1. 按照项目要求书写项目报告，条理清晰，数据准确； 2. 项目报告严禁抄袭，如发现抄袭的情况，则抄袭者与被抄袭者均 以0分计； 3. 课程结束后报告上交教师，并进行考核与存档。 三级项目报告格式规范 1. 正文：宋体，小四号，首行缩进2字符，1.5倍行距，段前段后 各0行； 2. 图表：居中，图名用五号字，中文用宋体，英文用“Times New Roman”，位于图表下方，须全文统一。

目录 一项目设计方案 (3) 二项目设计分析 (4) 三项目设计成果 (4) 四项目创新创业 (5) 五项目展望 (6) 附录一：项目成员 (6) 附录二：相关代码、电路图等 (6)

一项目设计方案 1、项目名称: 垃圾回收 2、项目要求及系统基本功能： 1）利用数据结构的知识独立完成一个应用系统设计 2）程序正常运行，能够实现基本的数据增加、删除、修改、查询等功能3）体现程序实现算法复杂度优化 4）体现程序的健壮性 二项目设计分析 1、系统预期实现基本功能： （结合本系统预期具体实现，描述出对应基本要求(增、删、改、查等)的具体功能） 1. 2. 3. 4. 5. 6. 7. 2、项目模块功能描述 （基本分为组织实施组织、程序功能模块编写、系统说明撰写等。其中程序功能子模块实现） 模块一： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块二： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块n： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

08-图论-离散数学讲义-海南大学(共十一讲)

08-图论-离散数学讲义-海南大学(共十一讲)

8.图论Topics in Graph Theory §8.1 图Graphs G= V={v 1,v 2 ,······,v n} 顶点vertex集。 E={ e | e=( v i , v j ), v i ,v j ∈V, v i≠v j}无向边edge集。 γ(e)={ v i, v j}, e的端点end points集。 简写为G＝（V，E）。 TD(v i)顶点v i的度数degree：连接到v i的边的条数。连接一个顶点的圈loop算两度。 孤立点isolated vertex：度数为0的点。 两个顶点相邻adjacent：有一边相连。 定理1. (握手定理) TD＝ TD(v i)=2m. 推论. 任意图的奇数度顶点必有偶数多个。 完全图complete graph： 任意两点都相邻简单图。 定理2. n个顶点的完全图有n(n-1)/2条边。正则图regular graph：每个顶点都有相同的度数。E={|v i ,v j∈V}有向边集有向图 有向边 ，

v i 起点弧尾， v j 终点弧头 TD(v i ):顶点的度degree: 以v i 为端点的边的数目。 OD(vi): 出度, 以v i 为起点的边的数目。 ID(v i ): 入度，以v i 为终点的边的数目。 TD(v i )= OD(vi)+ ID(v i ) OD=ID, TD=2|E|，E| =1/2*TD TD OD ID 为整个图的总度,出度,入度数。 路径path ： v i ······v j ， 以v i 为起点v j 为终点的顶点序列，相邻顶点相邻。 路径的长length : 路径上边的数目， 简单路径simple path :点都不重复的路径， 回路circuit : 首尾相接的路径， 简单回路simple circuit : 除起点和终点以外都不重复的路径， v i v j 连通connected : 有路径 v i ······v j 相连。 连通图: 任意两点都连通的图。 例 左图a,c,d,g 是简单路径 右图a,d,b,c,e 是简单路径。 f,e,a,d,b,a,f 是简单回路。 f,e,d,c,e,f 不是简单回路。 b f g d c e a f d c a e b

(完整版)数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include// 库头文件------ 动态分配内存空间 typedef int elemtype;// 定义数据域的类型 typedef struct linknode// 定义结点类型 { elemtype data;// 定义数据域 struct linknode *next;// 定义结点指针 }nodetype; 2）创建单链表

nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"<> d; if(d==0) break;// 以0 表示输入结束 if(i==1)// 建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));// 表示指针h h->data=d;h->next=NULL;t=h;//h 是头指针 } else// 建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t 始终指向生成的单链表的最后一个节点

数据结构课程设计报告模板

课程设计说明书 课程名称：数据结构 专业：班级： 姓名：学号： 指导教师：成绩： 完成日期：年月日

任务书 题目：黑白棋系统 设计内容及要求： 1.课程设计任务内容 通过玩家与电脑双方的交替下棋，在一个8行8列的方格中，进行棋子的相互交替翻转。反复循环下棋，最后让双方的棋子填满整个方格。再根据循环遍历方格程序，判断玩家与电脑双方的棋子数。进行大小判断，最红给出胜负的一方。并根据y/n选项，判断是否要进行下一局的游戏。 2.课程设计要求 实现黑白两色棋子的对峙 开发环境：vc++6.0 实现目标： （1）熟悉的运用c语言程序编写代码。 （2）能够理清整个程序的运行过程并绘画流程图 （3）了解如何定义局部变量和整体变量； （4）学会上机调试程序，发现问题，并解决 （5）学习使用C++程序来了解游戏原理。 （6）学习用文档书写程序说明

摘要 本文的研究工作在于利用计算机模拟人脑进行下黑白棋，计算机下棋是人工智能领域中的一个研究热点，多年以来，随着计算机技术和人工智能技术的不断发展，计算机下棋的水平得到了长足的进步 该程序的最终胜负是由棋盘上岗双方的棋子的个数来判断的，多的一方为胜，少的一方为负。所以该程序主要运用的战术有削弱对手行动战术、四角优先战术、在游戏开局和中局时，程序采用削弱对手行动力战术，即尽量减少对手能够落子的位置；在游戏终局时则采用最大贪吃战术，即尽可能多的吃掉对手的棋子；而四角优先战术则是贯穿游戏的始终，棋盘的四角围稳定角，不会被对手吃掉，所以这里是兵家的必争之地，在阻止对手进角的同时，自己却又要努力的进角。 关键词：黑白棋；编程；设计

浅谈强连通分量与拓扑排序的应用

浅谈强连通分量与拓扑排序的应用 浙江唐文斌摘要 强连通分量与拓扑排序是图论中最基础的算法之一。本文选取了两个简单但富有代表性的例子，说明这两个算法在一类图论问题中的应用。 [例一]Going from u to v or from v to u?1 给定一个有向图，问是否对于图中的任意两点u、v，总是存在u到v可达或者v到u （下文中将以a→b表示a到b可达）可达。图中点数不超过1000，边数不超过6000。 算法分析 题目描述很简单，我们最直观的想法就是求一个传递闭包，然后对于任意两点a、b判断是否a→b或者b→a。然而在本题中点数多达1000，传统的求传递闭包方法Floyd是行不通的。题目中的规模很小，似乎我们可以枚举起点s，并且从s开始对图进行一次宽度优先搜索，这样我们可以在O（N*（N+M））时间内求得传递闭包。似乎这个办法可行，但事实上，在本题中虽然规模小，但是数据组数高达200组，所以这个方法也是必然超时的。 我们抛开传递闭包，重新来看问题。题目中问是否对于任意两点都在至少一个方向上可达。那么如果两个点u、v，u→v且v→u，它们当然是符合要求的。所以我们第一个想法就是找到一个点集，该点集内所有点两两可达。由于其内部两两可达，所以我们可以将其缩成一个点，仅保留连向外界的边，并不会影响问题的本质。这个点集，就是强连通分量。所以我们的第一步操作就是：求图中所有的极大强连通分量，将每一个强连通分量缩成一个点，保留不同分量间的连边信息，得到一个新图。 我们对原图进行强连通分量缩点得到新图有什么好处呢？在这个过程中，我们将一些冗余信息进行了处理，得到的新图具有一个很重要的性质：无环（拓扑有序）。因为如果有环存在，那么这些环上的点都是互相可达的，所以它们应该同属于一个极大强连通分量，将被缩成一个点。所以我们现在的问题就是对于新图——一个拓扑有序的图，判断图中是否任意两点是否在至少一个方向上可达。 如果一个拓扑有序的图满足要求，那么它将拥有一些什么性质呢？我们先来看一些小规模的情况： （1）如果图只有一个点，则必然满足条件 （2）如果图中包含两个点，那么必须从一个点到另一个点有边相连。不妨设为a→b （显然b到a不可达）。 （3）如果图中包含3个点，不妨设第三个为c。那么必须满足c→a或者b→c。 通过上面3个情况的观察，我们大致就有了一个猜想： 1Poj Monthly Special – Jiajia&Wind’s story , problem G (POJ2762)

数据结构课程设计报告

山东建筑大学 课程设计成果报告 题目： 1.数组实现两个矩阵的相乘运算 2.成绩分析问题 课程：数据结构A课程设计 院（部）：管理工程学院 专业：信息管理与信息系统 班级：信管*** 学生姓名：*** 学号：******** 指导教师：******* 完成日期：2016年12月29日

目录 目录 (2) 一、课程设计概述 (3) 二、课程设计题目一 (3) 用数组实现两个矩阵的相乘运算 (3) 2.1[问题描述] (3) 2.2[要求及提示]： (3) 2.3[详细设计] (4) 2.4[调试分析] (5) 2.5[运行结果及分析] (5) 三、课程设计题目二 (6) 成绩分析问题 (6) 3.1[问题描述] (6) 3.2[概要设计] (6) 3.3[存储结构] (7) 3.4[流程图] (7) 3.5[详细设计] (8) 3.6[调试分析] (8) 3.7[运行结果及分析] (22) 四、参考文献： (25)

一、课程设计概述 本次数据结构课程设计共完成两个题：用数组实现两个矩阵相乘运算、成绩分析问题。使用语言：C 编译环境：vc6.0 二、课程设计题目一 用数组实现两个矩阵的相乘运算 2.1[问题描述] #include “stdio.h” int r[6][6]; void mult(int a[6][6] , int b[6][6]){ } main(){ int i,j; int num1[6][6],num2[6][6]; printf(“请输入第一个矩阵的值:”,); for(i=1;i<=6;i++) for(j=1;j<=6;j++) scanf(“%d”,&num1[i][j]); printf(“请输入第二个矩阵的值:”,); for(i=1;i<=6;i++) for(j=1;j<=6;j++) scanf(“%d”,&num2[i][j]); mult(num1,num2); printf(“\n两个矩阵相乘后的结果为：”); for(i=1;i<=6;i++) {for(j=1;j<=6;j++) printf(“%4d”,r[i][j]); printf(“\n”); } } 2.2[要求及提示]： 1、要求完善函数mult( ),

连通图的割点、割边(桥)、块、缩点,有向图的强连通分量

连通图的割点、割边(桥)、块、缩点，有向图的强连通分量 一、基本概念 无向图 割点：删掉它之后(删掉所有跟它相连的边)，图必然会分裂成两个或两个以上的子图。 块：没有割点的连通子图 割边：删掉一条边后，图必然会分裂成两个或两个以上的子图，又称桥。 缩点：把没有割边的连通子图缩为一个点，此时满足任意两点间都有两条路径相互可达。 求块跟求缩点非常相似，很容易搞混，但本质上完全不同。割点可以存在多个块中(假如存在k个块中)，最终该点与其他点形成k个块，对无割边的连通子图进行缩点后(假设为k个)，新图便变为一棵k个点由k-1条割边连接成的树，倘若其中有一条边不是割边，则它必可与其他割边形成一个环，而能继续进行缩点。 有割点的图不一定有割边，如： 3是割点，分别与(1,2)和(4,5)形成两个无割点的块 有割边的图也不定有割点,如：

w(1,2)为割边， 有向图 强连通分量：有向图中任意两点相互可达的连通子图，其实也相当于无向图中的缩点 二、算法 无向图 借助两个辅助数组dfn[],low[]进行DFS便可找到无向图的割点和割边，用一个栈st[]维护记录块和“缩点”后连通子图中所有的点。 dfn[i]表示DFS过程中到达点i的时间，low[i]表示能通过其他边回到其祖先的最早时间。low[i]=min(low[i],dfn[son[i]]) 设 v,u之间有边w(v,u)，从v->u： 如果low[u]>=dfn[v],说明v的儿子u不能通过其他边到达v的祖先，此时如果拿掉v,则必定把v的祖先和v的儿子u，及它的子孙分开，于是v便是一个割点，v和它的子孙形成一个块。 如果low[u]>dfn[v]时，则说明u不仅不能到达v的祖先，连v也不能通过另外一条边直接到达，从而它们之间的边w(v,u)便是割边，求割边的时候有一个重边的问题要视情况处理，如果v,u之间有两条无向边，需要仍视为割边的话，则在DFS的时候加一个变量记录它的父亲,下一步遇到父结点时不扩展回去，从而第二条无向重边不会被遍历而导致low[u]==dfn[v] ,而在另外一些问题中，比如电线连接两台设备A,B 如果它们之间有两根电线，则应该视为是双连通的，因为任何一条电线出问题都不会破坏A和B之间的连通性，这个时候，我们可以用一个used[]数组标记边的id,DFS时会把一条无向边拆成两条有向边进行遍历,但我们给它们俩同一个id号，在开始遍历v->u前检查它的id是否在上一次u->v 时被标记，这样如果两点之间有多条边时，每次遍历都只标记其中一条，还可以通过其他边回去，形成第二条新的路 求割点的时候，维护一个栈st 每遍历到一个顶点v则把它放进去，对它的子孙u如果dfn[u]为0，则表示还没有遍历到则先DFS(u),之后再判断low[u]和dfn[v]，如果low[u]>=dfn[v],则把栈中从栈顶到v这一系列元素弹出，这些点与v 形成一个块，如果u的子孙x也是一个割点，这样做会不会错把它们和v，u放在一起形成一个块呢，这种情况是不会发生的，如果发现x是一个割点，则DFS 到x那一步后栈早就把属于x的子孙弹出来了，而只剩下v,u的子孙，它们之间不存在割点，否则在回溯到v之前也早就提前出栈了！画一个图照着代码模拟一下可以方便理解。 求割边也是一样的。

有向图的强连通分量

实验报告 课程名称数据结构 实验项目名称有向图的强连通分量 班级与班级代码14计算机实验班 实验室名称（或课室）实验楼803 专业计算机科学与技术 任课教师 学号： 姓名： 实验日期：2015年12 月03 日 广东财经大学教务处制

姓名实验报告成绩 评语： 指导教师（签名） 年月日说明：指导教师评分后，实验报告交院（系）办公室保存。

一、实验目的与要求 采用邻接表存储的有向图。 二、实验内容 （1）创建N个节点的空图 DiGraph CreateGraph(int NumVertex)//创建一个N个节点的空图 { DiGraph G; G = malloc( sizeof( struct Graph ) ); if( G == NULL ) FatalError( "Out of space!!!" ); G->Table = malloc( sizeof( struct TableEntry ) * NumVertex ); if( G->Table == NULL ) FatalError( "Out of space!!!" ); G->NumVertex = NumVertex; G->NumEdge = 0; int i; for (i=0;iTable[i].Header=MakeEmpty(NULL); G->Table[i].V=i; } return G; } （2）在图G上执行DFS，通过对DFS生成森林的后序遍历对G的顶点编号。 //后序DFS遍历图G，并将节点按后序遍历的顺序编号 int *PostDFS(DiGraph G) { int NumVertex=G->NumVertex; int visited[NumVertex]; int i;

数据结构课程设计报告模板

校园导游系统设计 一、设计要求 1．问题描述 设计一个校园导游程序，为来访的客人提供信息查询服务。 2．需求分析 （1）设计学校的校园平面图。选取若干个有代表性的景点抽象成一个无向带权图（无向网），以图中顶点表示校内各景点，边上的权值表示两景点之间的距离。 （2）存放景点代号、名称、简介等信息供用户查询。 （3）为来访客人提供图中任意景点相关信息的查询。 （4）为来访客人提供图中任意景点之间的问路查询。 （5）可以为校园平面图增加或删除景点或边，修改边上的权值等。 二、概要设计 为了实现以上功能，可以从3个方面着手设计。 1．主界面设计 为了实现校园导游系统各功能的管理，首先设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户使用本系统。本系统主控菜单运行界面如图7-10所示。 2．存储结构设计 本系统采用图结构类型（mgraph）存储抽象校园图的信息。其中：各景点间的邻接关系用图的邻接矩阵类型（adjmatrix）存储；景点（顶点）信息用结构数组（vexs）存储，其中每个数组元素是一个结构变量，包含景点编号、景点名称及景点介绍三个分量；图的顶点个数及边的个数由分量vexnum、arcnum表示，它们是整型数据。 此外，本系统还设置了三个全局变量：visited[ ] 数组用于存储顶点是否被访问标志；d[ ]数组用于存放边上的权值或存储查找路径顶点的编号；campus是一个图结构的全局变量。 3．系统功能设计 本系统除了要完成图的初始化功能外还设置了8个子功能菜单。图的初始化由函数initgraph( )实现。依据读入的图的顶点个数和边的个数，分别初始化图结构中图的顶点向量数组和图的邻接矩阵。8个子功能的设计描述如下。 （1）学校景点介绍 学校景点介绍由函数browsecompus( )实现。当用户选择该功能，系统即能输出学校全部景点的信息：包括景点编号、景点名称及景点简介。 （2）查看浏览路线 查看浏览路线由函数shortestpath_dij( )实现。该功能采用迪杰斯特拉（Dijkstra）算法实现。当用户选择该功能，系统能根据用户输入的起始景点编号，求出从该景点到其它景点的最短路径线路及距离。 （3）查看两景点间最短路径

《数据结构》实验报告

《数据结构》实验报告 实验序号：4 实验项目名称：栈的操作

附源程序清单： 1. #include #define MaxSize 100 using namespace std; typedef int ElemType; typedef struct { ElemType data[MaxSize]; int top; }SqStack; void InitStack(SqStack *st) //初始化栈 { st->top=-1; } int StackEmpty(SqStack *st) //判断栈为空{ return (st->top==-1); } bool Push(SqStack *st,ElemType x) //元素进栈{ if(st->top==MaxSize-1)

{ return false; } else { st->top++; //移动栈顶位置 st->data[st->top]=x; //元素进栈 } return true; } bool Pop(SqStack *st,ElemType &e) //出栈 { if(st->top==-1) { return false; } else { e=st->data[st->top]; //元素出栈 st->top--; //移动栈顶位置} return true; } //函数名：Pushs //功能：数组入栈 //参数：st栈名,a->数组名，i->数组个数 bool Pushs(SqStack *st,ElemType *a,int i) { int n=0; for(;n数组名，i->数组个数 bool Pops(SqStack *st,ElemType *a,int i) { int n=0; for(;n

7.4.1无向图的连通分量和生成树

7.4.1无向图的连通分量和生成树。

void DFSForest(Graph G,CSTree &T) //建立无向图G的深度优先生成森林的 //（最左）孩子（右）兄弟链表T。 { T=NULL; for(v=0;vnextSibling=p; //是其他生成树的根（前一棵的根的“兄弟”）。 q=p; //q指示当前生成树的根。 DFSTree(G,v,p); //建立以p为根的生成树。 }// if(!visited[v]) }// for(v=0;vlchild=p;first=FALSE; }// if(first) else //w是v的其它未被访问的邻接顶点 { //是上一邻接顶点的右兄弟节点。 q->nextsibling=p; }// else q=p; DFSTree(G,w,q); //从第w个顶点出发深度优先遍历图G，建立子生成树q。 }// if(!visited[w]) }// for(w=FirstAdjVex(G,v); }// DFSTree

数据结构课程设计报告

哈希表实现电话号码查询系统 一目的 利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用 C/C++语言进行程序设计，并规范地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。 二需求分析 1、程序的功能 1)读取数据 ①读取原电话本存储的电话信息。 ②读取系统随机新建电话本存储的电话信息。 2)查找信息 ①根据电话号码查询用户信息。 ②根据姓名查询用户信息。 3)存储信息 查询无记录的结果存入记录文档。 2、输出形式 1)数据文件“old.txt”存放原始电话号码数据。 2)数据文件“new.txt”存放有系统随机生成的电话号码文件。 3)数据文件“out.txt”存放未查找到的电话信息。 4)查找到相关信息时显示姓名、地址、电话号码。 3、初步测试计划 1)从数据文件“old.txt”中读入各项记录，或由系统随机产生各记录，并且把记录保存 到“new.txt”中。 2)分别采用伪随机探测再散列法和再哈希法解决冲突。 3)根据姓名查找时显示给定姓名用户的记录。 4)根据电话号码查找时显示给定电话号码的用户记录。

5)将没有查找的结果保存到结果文件Out.txt中。 6)系统以菜单界面工作，运行界面友好，演示程序以用户和计算机的对话方式进行。三概要设计 1、子函数功能 int Collision_Random(int key,int i) //伪随机数探量观测再散列法处理冲突 void Init_HashTable_by_name(string name,string phone,string address) //以姓名为关键字建立哈希表 int Collision_Rehash(int key,string str) //再哈希法处理冲突 void Init_HashTable_by_phone(string name,string phone,string address) //以电话号码为关键字建立哈希表 void Outfile(string name,int key) //在没有找到时输出未找到的记录，打开文件out.txt并将记录储存在文档中void Outhash(int key) //输出哈希表中的记录 void Rafile() //随机生成数据，并将数据保存在new.txt void Init_HashTable(char*fname,int n) //建立哈希表 int Search_by_name(string name) //根据姓名查找哈希表中的记录 int Search_by_phone(string phone) //根据电话号码查找哈希表中的记录

数据结构课程实验报告(15)

课程实验报告课程名称：数据结构 专业班级：信安1302 学号： 姓名： 指导教师： 报告日期：2015. 5. 12 计算机科学与技术学院

目录 1 课程实验概述............ 错误!未定义书签。 2 实验一基于顺序结构的线性表实现 2.1 问题描述 ...................................................... 错误!未定义书签。 2.2 系统设计 ...................................................... 错误!未定义书签。 2.3 系统实现 ...................................................... 错误!未定义书签。 2.4 效率分析 ...................................................... 错误!未定义书签。 3 实验二基于链式结构的线性表实现 3.1 问题描述 ...................................................... 错误!未定义书签。 3.2 系统设计 ...................................................... 错误!未定义书签。 3.3 系统实现 ...................................................... 错误!未定义书签。 3.4 效率分析 ...................................................... 错误!未定义书签。 4 实验三基于二叉链表的二叉树实现 4.1 问题描述 ...................................................... 错误!未定义书签。 4.2 系统设计 ...................................................... 错误!未定义书签。 4.3 系统实现 ...................................................... 错误!未定义书签。 4.4 效率分析 ...................................................... 错误!未定义书签。 5 实验总结与评价 ........... 错误!未定义书签。 1 课程实验概述 这门课是为了让学生了解和熟练应用C语言进行编程和对数据结构进一步深入了解的延续。

求强连通分量的Kosaraju算法和Tarjan算法的比较 by ljq

求强连通分量的Kosaraju算法和Tarjan算法的比较 一、定义 在有向图中，如果两个顶点vi,vj间有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图的每两个顶点都强连通，则称该有向图是一个强连通图。非强连通的有向图的极大强连通子图，称为强连通分量(strongly connected components)。 而对于一个无向图，讨论强连通没有意义，因为在无向图中连通就相当于强连通。 由一个强连通分量内的所有点所组成的集合称为缩点。在有向图中的所有缩点和所有缩点之间的边所组成的集合称为该有向图的缩图。 例子： 原图： 缩图： 上面的缩图中的 缩点1包含：1、2,；缩点2包含：3； 缩点3包含：4；缩点4包含：5、6、7。

二、求强连通分量的作用 把有向图中具有相同性质的点找出来，形成一个集合（缩点），建立缩图，能够方便地进行其它操作，而且时间效率会大大地提高，原先对多个点的操作可以简化为对它们所属的缩点的操作。 求强连通分量常常用于求拓扑排序之前，因为原图往往有环，无法进行拓扑排序，而求强连通分量后所建立的缩图则是有向无环图，方便进行拓扑排序。 三、Kosaraju算法 时间复杂度：O（M+N）注：M代表边数，N代表顶点数。 所需的数据结构：原图、反向图（若在原图中存在vi到vj的有向边，在反向图中就变成为vj到vi的有向边）、标记数组（标记是否遍历过）、一个栈（或记录顶点离开时间的数组）。 算法描叙： 步骤1：对原图进行深度优先遍历，记录每个顶点的离开时间。 步骤2：选择具有最晚离开时间的顶点，对反向图进行深度优先遍历，并标记能够遍历到的顶点，这些顶点构成一个强连通分量。 步骤3：如果还有顶点没有遍历过，则继续进行步骤2，否则算法结束。 hdu1269（Kosaraju算法）代码： #include #include const int M=10005; struct node { int vex; node *next; }; node *edge1[M],*edge2[M]; bool mark1[M],mark2[M]; int T[M],Tcnt,Bcnt; void DFS1(int x)

数据结构课程设计报告 合并果子问题

合肥学院 计算机科学与技术系 课程设计报告 2011 ～2012 学年第二学期 课程数据结构与算法 课程设计名称合并果子问题 学生姓名杜双双 学号1004013037 专业班级计算机科学与技术10级3班 指导教师李红陈艳平王竹婷 2012 年2 月

课程设计报告 一、问题分析和任务定义 此程序需要完成如下要求：在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力3+12=15。可以证明15为最小的体力耗费值。 实现本程序需要解决以下几个问题： 1、要使每次合并的体力消耗最小应该选择数目最小的两堆果子，那么如何选择出两堆最小的呢？ 2、选择出了两堆果子如何进行合并？ 3、如何计算最小的体力耗费值？ 本问题的关键和难点在于数据结构的选择，找出最优的方法，在此选择哈夫曼树数据结构。 示例：三种果子，果子数目分别为1,2，3 哈夫曼树 最小体力消耗值：3+6=9 二、数据结构的选择和概要设计 上面采用哈夫曼树，则其存储就是哈夫曼树的存储结构。采用数组顺序存储结点信息。每一个结点包括四个域：存放该结点的weight 域、分别存放其左右孩子结点在数组中下标的lchild 域和rchild 域，以及记录该结点的父结点信息的parent 域。 只需用一个主函数就能解决问题。 三、详细设计和编码 数据结构： typedef struct {

数据结构实验报告--图实验

图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif MGraph.cpp #include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e)

{ int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: "; cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } } template void MGraph::DFSTraverse(int v) { cout << vertex[v]; visited[v] = 1; for(int j = 0; j < vertexNum; j++) if(arc[v][j] == 1 && visited[j] == 0) DFSTraverse(j); } template void MGraph::BFSTraverse(int v) { int Q[MaxSize]; int front = -1, rear = -1; cout << vertex[v]; visited[v] = 1; Q[++rear] = v; while(front != rear) { v = Q[++front]; for(int j = 0;j < vertexNum; j++) if(arc[v][j] == 1 && visited[j] == 0){ cout << vertex[j]; visited[j] = 1;

求强连通分量tarjan算法讲解

求强连通分量的tarjan算法 强连通分量：是有向图中的概念，在一个图的子图中，任意两个点相互可达，也就是存在互通的路径，那么这个子图就是强连通分量。（如果一个有向图的任意两个点相互可达，那么这个图就称为强连通图）。 如果u是某个强连通分量的根，那么： （1）u不存在路径可以返回到它的祖先。 （2）u的子树也不存在路径可以返回到u的祖先。 ?例如： ?强连通分量。在一个非强连通图中极大的强连通子图就是该图的强连通分量。比如图中子图{1,2,3,5}是一个强连通分量，子图{4}是一个强连通分量。 tarjan算法的基础是深度优先搜索，用两个数组low和dfn，和一个栈。low数组是一个标记数组，记录该点所在的强连通子图所在搜索子树的根节点的dfn值，dfn数组记录搜索到该点的时间，也就是第几个搜索这个点的。根据以下几条规则，经过搜索遍历该图和对栈的操作，我们就可以得到该有向图的强连通分量。

算法规则： ?数组的初始化：当首次搜索到点p时，Dfn与Low数组的值都为到该点的时间。 ?堆栈：每搜索到一个点，将它压入栈顶。 ?当点p有与点p’相连时，如果此时（时间为dfn[p]时）p’不在栈中，p 的low值为两点的low值中较小的一个。 ?当点p有与点p’相连时，如果此时（时间为dfn[p]时）p’在栈中，p的low值为p的low值和p’的dfn值中较小的一个。 ?每当搜索到一个点经过以上操作后（也就是子树已经全部遍历）的low 值等于dfn值，则将它以及在它之上的元素弹出栈。这些出栈的元素组成一个强连通分量。 ?继续搜索（或许会更换搜索的起点，因为整个有向图可能分为两个不连通的部分），直到所有点被遍历。 算法伪代码： tarjan(u) { DFN[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值 Stack.push(u) // 将节点u压入栈中 for each (u, v) in E // 枚举每一条边 if (！dfn[v]) // 如果节点v未被访问过 { tarjan(v) // 继续向下找 Low[u] = min(Low[u], Low[v]) } else if (v in S) // 如果节点v还在栈内 Low[u] = min(Low[u], DFN[v]) if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根 do{ v = S.pop // 将v退栈，为该强连通分量中一个顶点}while(u == v); } 演示算法流程；