强连通分量与模拟链表
强联通分量与模拟链表
作者：逸水之寒
1.强连通分量
强连通分量的定义是：在有向图中，u可以到达v，但是v不一定能到达u，如果u,v 到达，则他们就属于一个强连通分量。
求强连通分量最长用的方法就是Kosaraju算法，比较容易理解而且效率很高，本文对强连通分量的求法均采用Kosaraju算法。
其主要思想：首先对原图G进行深搜形成森林（树），然后选择一棵树进行第二次深搜，注意第一次是要判断节点A能不能通向节点B，而第二次要判断的是节点B能不能通向A，能遍历到的就是一个强连通分量。（附录给出伪代码）
Kosaraju算法如果采用了合适的数据结构，它的时间复杂度是O(n)的。相关题目有很多，例如USACO 5.3.3，2009NOIP Senior No.3。下面将以USACO 5.3.3 schlnet 举例说明。
Preblem 1. Network of Schools (USACO 5.3.3 schlnet\IOI96 No.3)
A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the "receiving schools"). Note that if
B is in the distribution list of school A, then A does not necessarily appear in the list of school B.
You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school.
INPUT FORMAT
The first line of the input file contains an integer N: the number of schools in the network (2<=N<=100). The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.
SAMPLE INPUT (file schlnet.in)
5
2 4
3 0
4 5 0
1 0
OUTPUT FORMAT
Your program should write two lines to the output file. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of subtask B.
SAMPLE OUTPUT (file schlnet.out)
1
2
分析：
本题需要将强连通分量进行缩点，具体做法可以先求出所有的强连通分量，然后重新建立图，将一个强连通分量用一个点在新图中表示出来。子任务A是求出所有需要得到软件的，需要得到软件的另一种理解就可以认为本节点在新构成的图中入度为0。子任务B是要求通过任意一个学校即可让全部学校都收到软件，也就是说题目要求再添加多少条边就可以使整个图成为一个大的强连通分量。我们知道，如果一个图中存在一个节点，他的出度或入度为0，那么整个图一定不是一个强联通分量，那么我们添加边的策略就可以变成添加最少的边，使得不出现入度或出度为0的节点，添加的边数=max(sum(出度为0的点)，sum （入度为0的点）)。此外有一个特殊情况，就是如果整个图原本就是一个强联通，那么第一问应该输出1，第二问应该输出0。（附录给出AC代码）
2.模拟链表
PASCAL中数组的功能很少，如果使用数组很多时候时间复杂度很高，这个时候链表的作用就显示出来了。如下表：
上表说明，如果我们的程序在进行添加或删除元素的时候，链表的时间复杂度是非常低的，而经常有题目需要添加和删除元素，这就是链表的使用范围很广泛。例如Problem1中，n<=100，如果使用数组，由于n很小，O(n^2)甚至O(n^3)程序都能承受，如果简单的修改一下题目，如下题：
Problem 2. 改编
Problem1 中n<=100000 边m<=100000
这样的题目，如果采用O(n^2)，程序必定TEL，我们必须优化数据结构使得时间复杂度降成O（n）即可。
由于个人比较厌倦PASCAL中的指针链表，故下面程序采用数组模拟链表来实现。模拟链表方法1：
先开足够大的数组，这个数组有两个域，一个是data域，一个是next域，data域存放的是数据，next域存放的是下一个数据的标号（这里等于起到了一个指针的作用），下面为参考代码（PASCAL）：
Type node=record
Data:longint; //存放数据
Next:longint; //存放下一个数据的标号
A:array[0..maxn] of longint //这里要开的足够大，保证不会被溢出
当我们需要一个节点的时候，可以进行如下操作
Inc(top); //a[top]就是你需要的节点
A[top].data=你的数据
A[pre].next=top //需要修改top上一个连接的next域，表示连接到了top 这样的链表虽然写起来简单，也非常好理解，但是却有一个致命的弱点，链表只能表示A节点连接到了B，但是如果我们要统计B节点的入度，就必须要耗费每次查询O(n)的代价，显然这个时候上面的数据结构不够用了，我们需要扩展这个数据结构。这个时候我们可以再开一个数组B（有两个域data,next），同样也需要一个指向B数组的指针( top)，但是这个时候我们并不知道这个链表的尾在什么地方，所以我们必须再添加一个数组en用来表示这个链表的尾，以后添加的时候，只需要查看en数组即可。（附录给出o(n)的problem1的程序）
自己的实践证明，如果只统计出度的话，这种方法的代码复杂度还能承受，但是如果需要同时统计入度，代码就会变得很累赘。建议如果同时统计入度和出度的时候，不要使用这种模拟链表的方法。
模拟链表方法2：
这个方法在OI界广泛流传，代码如下
last[点]=边记录和这个点相连的最后一条边
pre[边]=边记录和同一点相连的上一条边
other[边]=点记录的这条边的另一个点
如果需要建图，则：
readln(x,y); //表示x可以到y
inc(e); //边数加一
pre[e]:=last[x]; //e这条边的上一条边是x这个点的最后一条边
last[x]:=e; //x的最后一条边是现在的e
other[e]:=y; //e的另一条边是y
如果需要知道x这个点能连接的全部节点，则：
P:=last[x];
While p<>0 do
Begin
处理Other[p]
p:=pre[p];
End;
如果您采用了模拟链表方法1，如果你要统计入度的点，写起来会很复杂，但是如果您使用模拟链表方法2，统计入度的点只需要在新建立三个数组pre,other,last，原先的x连接y变成了y连接x即可。（附录给出模拟链表方法2的程序）
附录：
(1)强连通分量伪代码procedure kosaraju;
var i:longint;
procedure forthdfs(u:longint);
var i:longint;
begin
v[u]:=true;
for i:=1 to n do
if (not v[i]) and g[u,i] then
forthdfs(i);
inc(time);
order[time]:=u;
end;
procedure backdfs(u:longint);
var i:longint;
begin
v[u]:=true;
for i:=1 to n do
if (not v[i]) and (g[i,u]) then
backdfs(i);
fill[u]:=col;
end;
begin
fillchar(v,sizeof(v),0);
for i:=1 to n do
if not v[i] then
forthdfs(i);
fillchar(v,sizeof(v),0);
col:=0;
for i:=time downto 1 do
if not v[order[i]] then
begin
inc(col);
backdfs(order[i]);
end;
end;
(2)USACO 5.3.3 O(N^2)
var
n,c,i,j,time,tot,asum,bsum:longint;
map:array[0..100,0..100] of boolean; bool:array[0..100] of boolean; out,cor:array[0..100] of longint; new:array[0..100,0..100] of boolean; ru,chu:array[0..100] of longint;
procedure firstdfs(k:longint);
var i:longint;
begin
bool[k]:=true;
for i:=1 to n do
if (not bool[i]) and (map[k,i]) then firstdfs(i);
inc(time);
out[time]:=k;
end;
procedure seconddfs(k:longint);
var i:longint;
begin
bool[k]:=true;
for i:=1 to n do
if (not bool[i]) and (map[i,k]) then seconddfs(i);
cor[k]:=tot;
end;
begin
assign(input,'schlnet.in');
reset(input);
assign(output,'schlnet.out'); rewrite(output);
readln(n);
for i:=1 to n do
while true do
begin
read(c);
if c<>0 then map[i,c]:=true;
if c=0 then break;
end;
fillchar(bool,sizeof(bool),false);
for i:=1 to n do
if not(bool[i]) then
firstdfs(i);
fillchar(bool,sizeof(bool),false);
tot:=0;
for i:=n downto 1 do
if not(bool[out[i]]) then
begin
inc(tot);
seconddfs(out[i]);
end;
//writeln(tot);
for i:=1 to n do
for j:=1 to n do
if (cor[i]<>cor[j]) and (map[i,j]) then new[cor[i],cor[j]]:=true;
for i:=1 to tot do
for j:=1 to tot do
begin
if (i<>j) and (new[i,j]) then begin inc(ru[j]);inc(chu[i]); end;
end;
for i:=1 to tot do
begin
if ru[i]=0 then inc(asum);
if chu[i]=0 then inc(bsum);
end;
writeln(asum);
if tot=1 then begin writeln('0');halt; end;
if asum>bsum then writeln(asum) else writeln(bsum);
close(input);
close(output);
end.
(3)USACO 5.3.3 O(N) 模拟链表方法1
type
txt=record
data:longint;
next:longint;
end;
var
map,out,cor,map2,end2,nmap,endnew,ru,chu:array[0..100] of longint; a,b,new:array[0..10000] of txt;
bool:array[0..100] of boolean;
i,j,n,index,c,time,tot,point,asum,bsum:longint;
procedure firstdfs(k:longint);
var i,point:longint;
begin
bool[k]:=true;
point:=map[k];
while point<>0 do
begin
if bool[a[point].data]=false then firstdfs(a[point].data); point:=a[point].next;
end;
inc(time);
out[time]:=k;
end;
procedure seconddfs(k:longint);
var i,point:longint;
begin
bool[k]:=true;
point:=map2[k];
while point<>0 do
begin
if bool[b[point].data]=false then seconddfs(b[point].data); point:=b[point].next;
end;
cor[k]:=tot;
end;
begin
assign(input,'schlnet.in');
reset(input);
assign(output,'schlnet.out');
rewrite(output);
readln(n);
for i:=1 to n do //chu du chu li
while true do
begin
read(c);
if c=0 then break;
if map[i]=0 then
begin
inc(index);
a[index].data:=c;
map[i]:=index;
end
else
begin
inc(index);
a[index].data:=c;
a[index-1].next:=index;
end;
end;
index:=0;
for i:=1 to n do
begin
point:=map[i];
while point<>0 do
begin
if map2[a[point].data]=0 then
begin
inc(index);
map2[a[point].data]:=index;
b[index].data:=i;
end2[a[point].data]:=index;
end
else
begin
inc(index);
b[index].data:=i;
b[end2[a[point].data]].next:=index;
end2[a[point].data]:=index;
end;
point:=a[point].next;
end;
end;
fillchar(bool,sizeof(bool),false);
for i:=1 to n do
if not(bool[i]) then
firstdfs(i);
fillchar(bool,sizeof(bool),false);
tot:=0;
for i:=n downto 1 do
if not(bool[out[i]]) then
begin
inc(tot);
seconddfs(out[i]);
end;
//writeln(tot);
// SCC
// count
index:=0; // new map
for i:=1 to n do
begin
point:=map[i];
while point<>0 do
begin
if cor[a[point].data]<>cor[i] then
begin
if nmap[cor[i]]=0 then
begin
inc(index);
nmap[cor[i]]:=index;
new[index].data:=cor[a[point].data];
endnew[cor[i]]:=index;
end
else
begin
inc(index);
new[index].data:=cor[a[point].data];
new[endnew[cor[i]]].next:=index;
endnew[cor[i]]:=index;
end;
end;
point:=a[point].next;
end;
end;
for i:=1 to tot do
begin
point:=nmap[i];
while point<>0 do
begin
inc(chu[i]);
inc(ru[new[point].data]);
point:=new[point].next;
end;
end;
for i:=1 to tot do
begin
if ru[i]=0 then inc(asum);
if chu[i]=0 then inc(bsum);
end;
writeln(asum);
if tot=1 then begin writeln(0);halt; end;
if asum>bsum then writeln(asum) else writeln(bsum); close(input);
close(output);
end.
(4)USACO 5.3.3 O(N) 模拟链表方法2
var
//out
pre:array[0..10000] of longint;
last:array[0..100] of longint;
other:array[0..10000] of longint;
//in
preb:array[0..10000] of longint;
lastb:array[0..100] of longint;
otherb:array[0..10000] of longint;
//new map
npre:array[0..10000] of longint;
nlast:array[0..100] of longint;
nother:array[0..10000] of longint;
bool:array[0..100] of boolean;
out,cor,ru,chu:array[0..100] of longint;
i,n,c,e,eb,time,tot,p,asum,bsum:longint;
procedure firstdfs(k:longint);
var i,p:longint;
begin
bool[k]:=true;
p:=last[k];
while p<>0 do
begin
if bool[other[p]]=false then firstdfs(other[p]);
p:=pre[p];
end;
inc(time);
end;
procedure seconddfs(k:longint);
var i,p:longint;
begin
bool[k]:=true;
p:=lastb[k];
while p<>0 do
begin
if bool[otherb[p]]=false then seconddfs(otherb[p]); p:=preb[p];
end;
cor[k]:=tot;
end;
begin
assign(input,'schlnet.in');
reset(input);
assign(output,'schlnet.out');
rewrite(output);
//scc
readln(n);
for i:=1 to n do
while true do
begin
read(c);
if c=0 then break;
if c<>0 then
begin
inc(e); //out
pre[e]:=last[i];
last[i]:=e;
other[e]:=c;
inc(eb); //in
preb[eb]:=lastb[c];
lastb[c]:=eb;
otherb[eb]:=i;
end;
end;
fillchar(bool,sizeof(bool),false);
for i:=1 to n do
if not(bool[i]) then
tot:=0;
fillchar(bool,sizeof(bool),false); for i:=n downto 1 do
if not(bool[out[i]]) then
begin
inc(tot);
seconddfs(out[i]);
end;
//new map
e:=1;
for i:=1 to n do
begin
p:=last[i];
while p<>0 do
begin
if cor[i]<>cor[other[p]] then
begin
inc(e);
npre[e]:=nlast[cor[i]];
nlast[cor[i]]:=e;
nother[e]:=cor[other[p]];
end;
p:=pre[p];
end;
end;
//count
for i:=1 to tot do
begin
p:=nlast[i];
while p<>0 do
begin
inc(chu[i]);
inc(ru[nother[p]]);
p:=npre[p];
end;
end;
for i:=1 to tot do
begin
if ru[i]=0 then inc(asum);
if chu[i]=0 then inc(bsum); end;
if tot=1 then begin writeln(0);halt; end;
if asum>bsum then writeln(asum) else writeln(bsum); close(input);
close(output);
end.
图的连通性总结
图的连通性总结 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] 08-图论-离散数学讲义-海南大学(共十一讲) 8.图论Topics in Graph Theory §8.1 图Graphs G= 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 浅谈强连通分量与拓扑排序的应用 浙江唐文斌摘要 强连通分量与拓扑排序是图论中最基础的算法之一。本文选取了两个简单但富有代表性的例子，说明这两个算法在一类图论问题中的应用。 [例一]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) 第7章图 一、单项选择题 1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。 A．l/2 B．1 C．2 D．4 2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。 A．l/2 B．1 C．2 D．4 3．一个具有n个顶点的无向图最多包含______条边。 A．n B．n＋1 C．n-1 D．n(n-1)/2 4．一个具有n个顶点的无向完全图包含______条边。 A．n(n-l) B．n(n+l) C．n(n-l)/2 D．n(n-l)/2 5．一个具有n个顶点的有向完全图包含______条边。 A．n(n-1) B．n(n+l) C．n(n-l)/2 D．n(n+l)/2 6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。 A．n B．n×n C．n-1 D．(n-l) ×(n-l) 7．无向图的邻接矩阵是一个______。 A．对称矩阵B．零矩阵 C．上三角矩阵D．对角矩阵 8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。 A．n B．e C．2n D．2e 9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。 A．n B．e C．2n D．2e 10．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是入边也不是出边 11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是人边也不是出边 12．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。 A．完全图B．连通图 C．有回路D．一棵树 13．采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 连通图的割点、割边(桥)、块、缩点，有向图的强连通分量 一、基本概念 无向图 割点：删掉它之后(删掉所有跟它相连的边)，图必然会分裂成两个或两个以上的子图。 块：没有割点的连通子图 割边：删掉一条边后，图必然会分裂成两个或两个以上的子图，又称桥。 缩点：把没有割边的连通子图缩为一个点，此时满足任意两点间都有两条路径相互可达。 求块跟求缩点非常相似，很容易搞混，但本质上完全不同。割点可以存在多个块中(假如存在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;i 7.4.1无向图的连通分量和生成树。 void DFSForest(Graph G,CSTree &T) //建立无向图G的深度优先生成森林的 //（最左）孩子（右）兄弟链表T。 { T=NULL; for(v=0;v 《数据结构》实验报告 实验内容：（一）判断一个图有无回路 （二）求一个无向图G的连通分量的个数 一、目的和要求（需求分析）： 1、了解图的定义和图的存储结构。 2、熟悉掌握图的邻接矩阵和邻接表。 3、理解图的遍历算法---深度优先搜索和广度优先搜索。 4、学会编程处理图的连通性问题。 二、程序设计的基本思想，原理和算法描述： （包括程序的结构，数据结构，输入/输出设计，符号名说明等） 判断一个图有无回路： 在程序设计中，先必须确定所要创建的图是有向还是无向，是图还是网，其次再根据各自的特点，用连接表来实现创建。 在有向图中，先找出入度为0的顶点，删除与这个顶点相关联的边（出边），将与这些边相关的其它顶点的入度减1，循环直到没有入度为0的顶点。如果此时还有未被删除的顶点，则必然存在环路，否则不存在回路。 无向图则可以转化为： 如果存在回路，则必然存在一个子图，是一个回路。因此回路中所有定点的度>=2。 第一步：删除所有度<=1的顶点及相关边，并将另外与这些边相关的其它顶点的度减1。 第二步：将度数变为1的顶点排入队列，并从该队列中（使用栈）取出一个顶点，并重复步骤一。 如果最后还有未删除的顶点，则存在回路，否则没有。 求一个无向图G的连通分量的个数： 用连接表创建图，对于非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。所以在设计中，为了统计出无向图中的连通分量个数，则因在其深度优先所搜无向图时对函数DFSTraverse(ALGraph G)调用DFS次数进行统计，其结果便为无向图中连通分量个数。 三、调试和运行程序过程中产生的问题及采取的措施： 在调试和运行求一个无向图G的连通分量的个数程序时，由于执行语句块 void DFSTraverse(ALGraph G)先于void DFS(ALGraph G,int v)， 而void DFSTraverse(ALGraph G)内调用了DFS( )，因此计算机无法正确运行，将两者顺序进行了交换，程序便实现了其功能，且运行正常。 四、源程序及注释： 求强连通分量的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 有向图的强连通分量 分类：C/C++程序设计2009-04-15 16:50 2341人阅读评论(1) 收藏举报最关键通用部分：强连通分量一定是图的深搜树的一个子树。 一、Kosaraju算法 1.算法思路 基本思路： 这个算法可以说是最容易理解，最通用的算法，其比较关键的部分是同时应用了原图G和反图G T。(步骤1)先用对原图G进行深搜形成森林(树)，（步骤2）然后任选一棵树对其进行深搜(注意这次深搜节点A能往子节点B走的要求是E AB存在于反图G T)，能遍历到的顶点就是一个强连通分量。余下部分和 原来的森林一起组成一个新的森林，继续步骤2直到没有顶点为止。7 改进思路： 当然，基本思路实现起来是比较麻烦的(因为步骤2每次对一棵树进行深搜时，可能深搜到其他树上去，这是不允许的，强连通分量只能存在单棵树中(由开篇第一句话可知))，我们当然不这么做，我们可以巧妙的选择第二深搜选择的树的顺序，使其不可能深搜到其他树上去。想象一下，如果步骤2是从森林里选择树，那么哪个树是不连通(对于G T来说)到其他树上的 呢？就是最后遍历出来的树，它的根节点在步骤1的遍历中离开时间最晚，而且可知它也是该树中离开时间最晚的那个节点。这给我们提供了很好的选择，在第一次深搜遍历时，记录时间i离开的顶点j，即numb[i]=j。那么，我们每次只需找到没有找过的顶点中具有最晚离开时间的顶点直接深搜(对于G T来说)就可以了。每次深搜都得到一个强连通分量。 隐藏性质: 分析到这里，我们已经知道怎么求强连通分量了。但是，大家有没有注意到我们在第二次深搜选择树的顺序有一个特点呢？如果在看上述思路的时候，你的脑子在思考，相信你已经知道了！！！它就是：如果我们把求出来的每个强连通分量收缩成一个点，并且用求出每个强连通分量的顺序来标记收缩后的节点，那么这个顺序其实就是强连通分量收缩成点后形成的有向无环图的拓扑序列。为什么呢？首先，应该明确搜索后的图一定是有向无环图呢？废话，如果还有环，那么环上的顶点对应的所有原来图上的顶点构成一个强连通分量，而不是构成环上那么多点对应的独自的强连通分量了。然后就是为什么是拓扑序列，我们在改进分析的时候，不是先选的树不会连通到其他树上（对于反图GT来说），也就是后选的树没有连通到先选的树，也即先出现的强连通分量收缩的点只能指向后出现的强连通分量收缩的点。那么拓扑序列不是理所当然的吗？这就是Kosaraju算法的一个隐藏性质。 求强连通分量的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); } 演示算法流程； 图 1. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。 《数据结构》实验报告 ◎实验题目:无向图的存储和遍历 ◎实验目的：1、掌握使用Visual C++6.0上机调试程序的基本方法； 2、掌握图的邻接表存储结构和深度优先遍历的非递归算法。 3、提高自己分析问题和解决问题的能力，在实践中理解教材上的理论。 ◎实验内容：建立有10个顶点的无向图的邻接表存储结构，然后对其进行深度优先遍历，该无向图可以是无向连通图或无向非连通图。 一、需求分析 1、输入的形式和输入值的范围：根据提示，首先输入图的所有边建立邻接表存储结构，然后输入遍历的起始顶点对图或非连通图的某一连通分量进行遍历。 2、输出的形式：输出对该图是连通图或非连通图的判断结果，若是非连通图则输出各连通分量的顶点，之后输出队连通图或非连通图的某一连通分量的遍历结果。 3、程序所能达到的功能：输入图的所有边后，建立图的邻接表存储结构，判断该图是连通图或非连通图，最后对图进行遍历。 4、测试数据： 输入10个顶点（空格分隔）:A B C D E F G H I J 输入边的信息（格式为x y）:AB AC AF CE BD DC HG GI IJ HJ EH 该图为连通图,请输入遍历的起始顶点:A 遍历结果为:A F C D B E H J I G 是否继续？（是,输入1;否,输入0）:1 输入10个顶点（空格分隔）:A B C D E F G H I J 输入边的信息（格式为xy）:AB AC CE CA AF HG HJ IJ IG 该图为非连通图,各连通分量中的顶点为: < A F C E B > < D > < G I J H > 输入第1个连通分量起始顶点:F 第1个连通分量的遍历结果为:F A C E B 输入第2个连通分量起始顶点:I 第2个连通分量的遍历结果为:I G H J 输入第3个连通分量起始顶点:D 第3个连通分量的遍历结果为:D 是否继续？（是,输入1;否,输入0）:0 谢谢使用! Press any key to continue 二概要设计 1、邻接表是图的一种顺序存储与链式存储结构结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对图G中的每个顶点Vi，将所有邻接于Vi的顶点Vj链成一个单链表，这个单链表就称为顶点Vi的邻接表，再将所有邻接表的表头放到数组中，就构成了图的邻接表，邻接表表示中的两种结点结构如下所示。 强联通分量与模拟链表 作者：逸水之寒 1.强连通分量 强连通分量的定义是：在有向图中，u可以到达v，但是v不一定能到达u，如果u,v 到达，则他们就属于一个强连通分量。 求强连通分量最长用的方法就是Kosaraju算法，比较容易理解而且效率很高，本文对强连通分量的求法均采用Kosaraju算法。 其主要思想：首先对原图G进行深搜形成森林（树），然后选择一棵树进行第二次深搜，注意第一次是要判断节点A能不能通向节点B，而第二次要判断的是节点B能不能通向A，能遍历到的就是一个强连通分量。（附录给出伪代码） Kosaraju算法如果采用了合适的数据结构，它的时间复杂度是O(n)的。相关题目有很多，例如USACO 5.3.3，2009NOIP Senior No.3。下面将以USACO 5.3.3 schlnet 举例说明。 Preblem 1. Network of Schools (USACO 5.3.3 schlnet\IOI96 No.3) A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the "receiving schools"). Note that if B is in the distribution list of school A, then A does not necessarily appear in the list of school B. You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school. 求无向连通图的生成树 一、实验目的 ⑴掌握图的逻辑结构 ⑵掌握图的邻接矩阵存储结构 ⑶验证图的邻接矩阵存储及其遍历操作的实现 二、实验内容 （1）建立无向图的邻接矩阵存储 （2）对建立的无向图，进行深度优先遍历 （3）对建立的无向图进行广度优先遍历 三、设计与编码 （1）本实验用到的理论知识 （2）算法设计 （3）编码 // 图抽象类型及其实现.cpp : Defines the entry point for the console application. // #include"stdafx.h" #include"Graph.h" #include"iostream.h" int Graph::Find(int key,int &k) { int flag=0; for(int i=0;i if(vertexnum<1)return(-1);//参数vertexnum非法 int i,front,rear,k; Enode *q; //先生成不带边表的顶点表--即顶点为孤立顶点集 A=new Vnode[vertexnum]; if(!A)return(0);//堆耗尽 for(i=0;i 课程设计报告 课程设计名称：数据结构课程设计 课程设计题目：实现求有向图强连通分量的算法 院（系）： 专业： 班级： 学号： 姓名： 指导教师： 沈阳航空航天大学课程设计报告 目录 1 系统分析 (1) 1.1题目介绍 (1) 1.2功能要求 (1) 2 概要设计 (2) 2.1流程图 (2) 2.2结构体说明 (2) 3 详细设计 (3) 3.1遍历函数设计 (3) 3.1.1 Kosaraju算法基本思路： (3) 3.1.2伪代码 (4) 3.2调试分析和测试结果 (6) 3.2.1调试分析 (6) 3.2.2测试结果 (6) 参考文献 (8) 附录（关键部分程序清单） (9) 沈阳航空航天大学课程设计报告 1 系统分析 1.1 题目介绍 在键盘上输入有向图，对任意给定的图（顶点数和边数自定），建立它的邻接表并输出。然后判断该图是否强连通。如果是强连通图，求出该图的所有强连通分量并输出字符。 1.2 功能要求 首先输入图的类型，有向图（因为遍历与权值无关，所以没有涉及带权图）。然后输入图的顶点数、边数和各条边，之后生成该图的邻接表并输出。 再输入要遍历该图的起点，然后从所输入的点深度搜索该图的十字链表，并按遍历顺序输出顶点内容。之后决定是否继续遍历该图或输入另一个需要遍历的图亦或是结束程序。 要求采取简单方便的输入方式。并且系统要求提供观察有向图图形结构和各强连通分量结构的功能。 2 概要设计 2.1 流程图 根据程序要求，设计流程图如下： 图2.1——流程图 2.2 结构体说明 //有向图十字链表存储表示 typedef struct arcbox int tailvex,headvex;//该弧的尾和头顶点的位置 名词解释 数据结构 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 集合 集合是指数据元素之间除了同属一个集合的关系外，别无其他关系。 逻辑结构 数据的逻辑结构是对数据之间关系的描述，它与数据的存储结构无关，同一种逻辑结构可以有多种存储结构。 物理结构(存储结构) 物理结构又称为数据的存储结构,是指数据的逻辑结构在计算机中的表示(又称映像),它包括数据元素的表示和关系的表示。 算法 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 线性表 线性表是最常用且最简单的一种数据结构,是n个数据元素的有限序列。 串 串是由零个或多个字符组成的有限序列。 栈 栈是限定仅在表尾进行插入或删除操作的线性表。 队列 队列是一种先进先出的线性表。 递归 一个直接调用自己或通过一系列的调用语句间接地调用自己的函数。 二叉树 二叉树是一种每个结点至多有两颗子树，并且子树有左右之分，次序不能颠倒的树型结构。 满二叉树 深度为k,且有2k-1个结点的二叉树。 完全二叉树 深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中的编号从1到n的结点一一对应时，称之为完全二叉树。 森林 m棵互相不相交的树的集合,对树中每个节点而言，其子树的集合即为森林。 树的路径长度 树中每个结点到根结点的路径长度之和. 树的带权路径长度(WPL) 树中所有叶子结点的带权路径长度之和. 哈夫曼树（最优二叉树） 设有n个权值的结点构造一棵有n个叶子结点的二叉树,其中WPL最小的那棵树,为哈夫曼树。 哈夫曼编码 一般以N种字符出现的频率做权值,构造哈付曼树,左孩子边做0,右孩子边做1,那么从根到叶子结点经过的0和1序列,构成了哈夫曼编码。 前缀编码 任何一个字符的编码都不是另一个字符编码的前缀,这种编码叫做前缀编码。 线索二叉树 对二叉树以某种次序进行遍历并加上线索的过程叫做线索化。线索化了的二叉树称为线索二叉树。 生成树 一个连通图的生成树是指一个极小连通子图,它含有图中的全部顶点,N-1条边。 最小生成树 在图G的所有生成树中,树权值最小的那棵生成树,称作最小生成树。 目录 1 算法分析 (2) 1.1条件分析 (2) 1.2.1 有向图的存储结构 (2) 1.2.2 深度优先遍历 (2) 1.2.3 求解强连通分量 (2) 2 系统设计 (3) 2.1 设计说明 (3) 2.2 数据结构描述 (4) 2.3 MAIN () 函数 (4) 2.4 邻接表和逆邻接表的建立 (6) 2.5 邻接表的遍历 (6) 2.6 逆邻接表的遍历 (9) 参考文献 (11) 附录（关键部分程序清单）.................................................................................. . (12) 程序设计总结 (15) 1 算法分析 1.1 条件分析 有向图的强连通分量是有向图中的最大强连通子图。而对于一个有向图G，如果对于每一对的Vi和Vj∈V，Vi≠Vj，从Vi到Vj和Vj到Vi都存在路径，则称G是强连通图。 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中一个强连通分量的顶点集。08-图论-离散数学讲义-海南大学(共十一讲)
浅谈强连通分量与拓扑排序的应用
数据结构图习题分解
连通图的割点、割边(桥)、块、缩点,有向图的强连通分量
有向图的强连通分量
7.4.1无向图的连通分量和生成树
求一个无向图G的连通分量的个数
求强连通分量的Kosaraju算法和Tarjan算法的比较 by ljq
有向图的强连通分量算法
求强连通分量tarjan算法讲解
数据结构 第六章 图 练习题及答案详细解析(精华版)
数据结构 无向图的存储和遍历
强连通分量与模拟链表
求无向连通图的生成树
实现有向图强连通分量的算法 数据结构课程设计报告
重要数据结构名词解释
有向图的强连通分量课设报告