图论 基础概念

1、一、图论的基础概念以下概念不是定义，也不一定完全，只是一些常用的概念，比较通俗化。在以后具体的算法中再适当加入概念。图： 由点和线组成的图形。顶点： 图中的结点。无向图： 边没有正反方向。完全图： 在N个顶点的无向图中，边最大为n*（n-1）/2称为无向完全图度： 与结点相连的边数。有向图： 边有正反方向。入度（出度）：连入（出）的边数。（对于有向图来说）奇顶点：结点的度是奇数的点。路径：如果从a到b可达（包括直接到达或者中间有其他结点）那么从a到b就有一条路径。一条路径就是一种走法，路径的边数叫做路径长度。一条路径上的n个顶点的集合叫做连通集。回路（环）：从aba简单路径：存在从abe此条路

2、径中每个结点不同。有根图：有结点到其他任意结点连通，则此结点为根，一个图可以有多根。连通图：若图中任意两个结点可以连通，则此图为连通图（无向图）。强连通图：任意i到j都有从i到j的路径。（有向图）强连通分支：强连通的最大子图。道路：可以一笔画成的图，并且不重不漏。 *充分必要条件：图是连通的，且奇顶点的个数等于0或2 并且当且仅当奇顶点的个数为0时，图是一条回路（包括一个孤立的点）二分图（应该是超纲的内容） 充要条件：图中无奇顶点。 具体算法以后补充。Hamilton回路：经过图中每一个顶点一次的回路。欧拉回路：图的一个回路,若它通过图中每条边一次且仅一次。（有关问题：七桥问题，一笔画问题）对

3、于一个无向图，如果它每个点的度都是偶数，那么它存在一条欧拉回路；如果有且仅有2个点的度为奇数，那么它存在一条欧拉路；如果超过2个点的度为奇数，那么它就不存在欧拉路了。图的存储结构只总结了常用的存储结构有相邻矩阵和邻接表两种，只介绍相邻矩阵的内容，邻接表运用了动态指针链表数据结构 实现起来比较麻烦。无向图：AI，J = 1 当I与J两个结点相邻时 = 0 当I与J两个结点不相邻时，或I=J（1=I，J=图中结点数） 且有：AI，J=AJ，I，即邻接矩阵是对称的。如上图（A）的邻接矩阵如下： 0 1 1 1A = 1 0 1 1 1 1 0 0 1 1 0 0有向图：AI，J = PI，J 当I与

4、J两个结点相邻，且权值为PI，J时 = 0 或 当I与J两个结点不相邻时，或I=J如上图（B）和（C）的邻接矩阵分别如下： 0 1 1 5 8 3 A = 0 0 1 A = 5 2 60 0 1 8 2 10 4 10 11相应的数据结构定义如下： const maxn=20; type adj=0.1;graph=array 1.maxn,1.maxn of adj;还有一种是纪录一条边的两个端点，做边表。const maxn=20;type adj=0.1;x,y=array 1.maxn of adj;xi,yi为第i条边的前一个顶点和后一个顶点For i：=1 to n do Beg

5、in Readln(xi,yi); 如果是无向图，那么将每一条边拆成两条边，分成第i条边和第i+n条边 xi+n:=yi; yi+n:=xi; end;三、图的遍历概念：从图中某一结点出发系统地访问图中所有结点，使每个结点恰好被访问一次，这种运算被图的遍历。为了避免重复访问某个结点，可以设一个标志数组fI，未访问时值为FALSE，访问一次后就改为TRUE。分类：深度优先遍历和广度优先遍历。重要性：DFS和BFS在图的遍历中和搜索算法中有很重要很重要的地位。必须灵活掌握。深度优先遍历从图中某个结点V0出发，访问此结点，然后依次访问从V0的未被访问的邻接点出发进行深度优先遍历，直到图中所有和V0有

6、路径相通的结点均被访问到。若此时图中尚有结点未被访问，则另选图中一个未被访问的结点V1作为起点，重复上述过程，直至图中所有结点都被访问到为止。如下面两个图的深度优先遍历结果分别为：a，b，c，d，e，g，f。V1，V2，V4，V8，V5，V3，V6，V7。通俗点 就是先顺着一条路走到底，访问完了这条路之后再回溯到最近的那个岔路口，走另一条路，依此类推，直到访问完了所有的结点。深度优先遍历的递归过程如下：procedure dfs(i:integer); begin write(i); 访问此结点，对结点进行操作，不一定是writefi:=true; 设置已访问标志for j:=1 to n d

7、o if (not fj) and (ai,j=1) then dfs(j);j没有访问过，并且i和j相连 end;图如果连通，那么一次 dfs(1) 就可以遍历所有结点。图如果不连通，通过多次调用dfs访问所有的结点：for i:=1 to n do if not fi then dfs(i);在图论的那本黄皮书上，有一种非递归的dfs，感觉不是很简洁。代码如下：procedure dfs(s:integer); begin i:=0; v:=s; repeat inc(i); lv.k：=i; repeat u:=1; while u=n and gv,u=false do inc(u);

8、 gv,u:=false; gu,v:=false; until (u=n+1) or (lu.k=0); if un+1 then begin v:=u; 对u进行访问 lu.f:=v; if lv.k1 then v:=lv.f; until lv.k=1; end;因为我觉得这没什么大用，所以没打注释。看起来有点麻烦，如果你觉得这对你用，那么可以看那本黄色的图论专题，上面有详细的讲解。广度优先遍历从图中某个结点V0出发，访问此结点，然后依次访问与V0邻接的、未被访问过的所有结点，然后再分别从这些结点出发进行广度优先遍历，直到图中所有被访问过的结点的相邻结点都被访问到。若此时图中还有结点尚

9、未被访问，则另选图中一个未被访问过的结点作为起点，重复上述过程，直到图中所有结点都被访问到为止。如上面两个图的广度优先遍历结果分别为：a，b，d，e，f，c，g。 V1，V2，V3，V4，V5，V6，V7，V8。通俗点： 广度优先遍历就是按层搜索，对于BFS网络上有一个很形象的比喻，“就像一滴墨水落在水面上，并慢慢扩散”这一滴墨水就是BFS进行的第一个顶点i ，扩散的过程就是一个搜索的过程。广度优先遍历的过程如下：Procedure bfs(i:integer); Begin 访问i结点； Fi:=true; While 队列非空 do i 点进入队列 Begin 从队列中移出队首元素v； F

10、or j:=1 to n do If (not fi) and (av,j=1) then Begin 访问结点j； fj:=true; 顶点j进入队列； End; End; End;运用到队列的数据结构，很简单。就是用一个数组模拟，一共有两个指针，队首指针和队尾指针，对于数组中的元素进入之后就不变了，通过队首与队尾指针变化实现入队出队。入队： inc(队尾)； a队尾：=数据；出队： inc(队首)； 数据：=a队首由于此过程中，出队的元素虽然已经出队，但仍是保留的，所以数据量大的时候很容易造成内存浪费，因此有一种优化，循环队列，很简单，加一个mod m就可以，我感觉一般可能用不到，所以就不

11、打代码了。代码可以到王建德的那本紫皮上去找。种子染色法 种子染色法是DFS和BFS的一种应用。可以求得图中连通子图的个数，一般用于无向图中。既可以用BFS也可以用DFS实现。 初始时，每一个结点标号为0，color:=0; color为编号 For i:=1 to n do If fi=0 then begin inc(color); DFS(i)/BFS(i); 过程中的fi=ture 改成 fi:=colorend;最后color的值为连通子图的个数。每一个连通子图中各个结点的标号都是相同的。在实际应用中种子染色法中对于color的设计，和如果进行染色是很灵活的。我讲的只是一种做题思路。我

12、感觉种子染色法还是很有用的。 关于DFS和BFS在搜索中应用，可以找刘麟汉搜索的那一节。End.四、图论的经典算法图的经典算法是必须掌握的，背也要背过。联赛中考图论也是在经典算法的基础上，考的是灵活应用。所以经典算法是必要的工具。图的经典算法有 求单源最短路径的迪杰斯特拉算法，SPFA算法，求负权回路的BELLMAN算法，多源最短路径的FLOYD算法，拓扑排序，最小生成树的prim和kruskal算法，求图的关键路径下面给出各个算法的基础思想和源代码。迪杰斯特拉算法基本思想：贪心。 运用前提：所有的边不能是负数。 作用：求单源最短路径过程：先假设有一个集合，存储已经确定的顶点。显然，最开始只有

13、一个源点v1,再选择与v1路径最短的点加入集合，更新最短路的权。直到所有的顶点加入集合。program dijkstra;var v:array1.1000 of boolean; v布尔数组用来设定顶点是否已经访问 a:array1.1000,1.1000 of integer;存储图 i,j,n,min,k:integer;begin v1:=true; readln(n); for i:=1 to n do for j:=1 to n do begin read(ai,j);end;读入图 for j:=2 to n do begin min:=10000;设置最大值 for i:=1

14、to n do if (not vi) and (a1,i0) and (a1,imin) then找到距离最短的顶点 begin min:=a1,i; k:=i; end;vk:=true;设置以访问标志 for i:=1 to n do更新最短权值 if (a1,k0) and (ak,i0) then if (a1,k+ak,idisu+au,v，那么disvdisu+disu,v。program BELLMAN;const maxp= 800; 最大点数 maxc= 1450; 最大边数 max= 300000;type edge= record 边 a, b, d: integer;

15、 end;var pa: array1.maxpof integer; e: array1.maxcof edge; 边表 dis: array1.maxpof longint; n, p, c, i, j, s: integer; tot, min: longint; flag: boolean;procedure relax(a, b, d: integer); 松弛操作var z: longint;begin z:= disa+d; if zdis then begin dis:= z; flag:= false;end;end;beginfillchar(pa, sizeof(pa),

16、 0);readln(p, c); C为边数 p为点数for i:= 1 to c do readln(e.a, e.b, e.d); a点和b点相通，长度为d s:=1; 单源最短的源for i:= 1 to p do disi:= max; 初始化diss:= 0;主程序repeat flag:= true; for i:= 1 to c do with e do begin relax(a, b, d); relax(b, a, d); end;until flag;for I:=1 to n do writeln(disi);end.SPFA算法初始时将源加入队列.每次从队列中取出一个

17、元素,并对所有与他相邻的点进行松弛,若某个相邻的点松弛成功,则将其入队.直到队列为空时算法结束.SPFA算法的效率 时间复杂度一般认为是O(kE) 其中k是一个较大的常数,不好估计,但是可以看出SPFA算法效率应当是很高的经验表明Dijkstra算法的堆优化要比SPFA快,但SPFA比普通的Dijkstra算法快.而SPFA算法可以处理负权的问题,而且比Dijkstra算法的堆优化的代码要容易实现,因此SPFA是一个很好的算法.SPFA在处理稀疏图时效果比较不错 在处理稠密图时可能没有Floyd好program SPFA;const maxn=800; 最大点 maxq=maxn；最大边var

18、 n,p,c:integer; map:array1.maxn,1.maxnof integer; 图 dis:array1.maxn,1.maxn of longint; 距离 connect:array1.maxn,0.maxn of integer; 存图procedure init;var i,x,y,distance:integer;begin 初始化 fillchar(connect,sizeof(connect),0); fillchar(map,sizeof(map),255); readln(p,c); p为点 C为边 for i:=1 to c do 读入 begin re

19、adln(x,y,distance); if (mapx,y=1) or (distancemapx,y) then begin mapx,y:=distance; mapy,x:=distance; end; inc(connectx,0); connectx,connectx,0:=y; inc(connecty,0); connecty,connecty,0:=x; end; for i:=1 to p do begin mapi,i:=0; disi,i:=0; end;end;procedure spfa(v0:integer); vo源点var i,now,open,close:i

20、nteger; queue:array1.maxq of integer; 队列 inqueue:array1.maxn of boolean; 是否入队begin fillchar(inqueue,sizeof(inqueue),0); 初始化 fillchar(queue,sizeof(queue),0); fillchar(disv0,sizeof(disv0),255); disv0,v0:=0; queue1:=v0; vo入队 inqueuev0:=true; open:=0; 队首 close:=1; 队尾 while closeopen do begin inc(open);

21、now:=queueopen; 出队 inqueuenow:=false; for i:=1 to connectnow,0 doif (disv0,connectnow,i=-1)or(disv0,now+mapnow,connectnow,idisv0,connectnow,i) then 松弛操作 begin disv0,connectnow,i:=disv0,now+mapnow,connectnow,i; if not inqueueconnectnow,i then 入队 begin inc(close); queueclose:=connectnow,i; inqueueconn

22、ectnow,i:=true; end; end; end;end;procedure work;var i,j:integer;begin for i:=1 to cowin0 do spfa(cowini); for i:=1 to p do begin for j:=1 to p do write(disi,j, ); writeln; end; end;begin init; work;end.*弗洛伊德算法基本思想：*传递闭包。也算是一种动态规划。作用：求任意两点最短路径。过程：枚举中间结点k，首结点i和尾结点jprogram floyd;var a:array1.1000,1.10

23、00 of integer;存储图 i,j,k,n:integer;begin readln(n); for i:=1 to n do for j:=1 to n do begin read(ai,j); if (ij) and (ai,j=0) then ai,j:=maxint;end;数据初始化 for k:=1 to n do for i:=1 to n do begin if ki then for j:=1 to n do if (kj) and (ij) and (ai,jai,k+ak,j) then ai,j:=ai,k+ak,j;end; writeln(任意两点最短路径)

24、;end.对于floyd算法有很重要的应用。在王建德的紫皮书上有传递闭包的很多用处。在这里略过，但是一定要看一下，用传递闭包预处理数据是很有用，很重要的。求拓扑序列定义：我自己不好说，看王建德的紫皮（P118）。不懂定义就看不懂算法。特点：一个有向图结点的拓扑序列不是唯一的。有环图不能拓扑排序。作用：求一个图的拓扑序列，判断有无回路。欲处理时候很有用，有的搜索前很必要，比如神经网络前提：有向图过程：预处理数据的时候记下每一个点的入度，每次找出一个入度为0的点，删掉这个点，更新与它相邻的点的入度（入度减一）。program tppv;const maxn=100;var map:array1.m

25、axn,1.maxn of byte;存储图 into:array1.maxn of byte;每个结点的入度 n,i,j,k:byte;procedure init;读入数据var i,j:integer;beginreadln(n); fillchar(map,sizeof(map),0); fillchar(into,sizeof(into),0); while not(seekeof(input) do begin readln(I,j); mapI,j:=1; inc(intoj);有一条边连入，那么入度加1 end;end;begin init;输入数据 for i:=1 to n

26、 do begin j:=1; while (j=n)and(intoj0) do inc(j);找到一个入度为0的点 if j=n then判断有无回路 begin write(j, ); intoj:=255;删掉此点 for k:=1 to n do if mapj,k=1 then dec(intok);更新与j点连结的点的入度 end else begin writeln(存在回路，没有拓扑序列)；halt；end； end.最小生成树Prim算法前提：无向图 或者 强连通的有向图。上图（B）和（C）都是（A）的生成树，生成树中各边的权值之和称为这棵生成树的代价，代价最小的生成树称为

27、“最小代价生成树”。作用：已知所有边的权值，用最小的代价将所有的结点连起来。过程：设图的顶点集合V共有n个顶点，则算法如下：1、 设置一个顶点的集合S1和一个边的集合TE，S1和TE的初始状态均为空集；2、 选定图中的一个顶点K，从K开始生成最小代价生成树，将K加入到集合S1；3、 重复下列操作，直到选取了n-1条边： 选取一条权值最小的边（X，Y），其中XS1，not(YS1)。将顶点Y加入集合 S1，边（X，Y）加入集合TE。下图给出了上图（A）的最小代价生成树的生成过程：下面的程序代码是蓝皮书数据结构与算法设计的源程序。对于Minclosd和closd数组的设计，可以参考此书，讲的还算明

28、白。program prim;var minclosd,closd:array1.1000 of integer;设置minclosd,closd数组 a:array1.1000,1.1000 of integer;存储图 i,j,min,n,k:integer;begin readln(n); for i:=1 to n do for j:=1 to n do begin read(ai,j); if (ij) and (ai,j=0) then ai,j:=maxint; end;读入图 注意数据的预处理 for i:=1 to n do begin minclosdi:=a1,i; cl

29、osdi:=1; end;两数组初始化 for j:=2 to n do begin min:=maxint;主要部分 for i:=1 to n do if (minclosdi0) then begin min:=minclosdi; k:=i end; minclosdk:=0; for i:=1 to n do if (ak,iminclosdi) and (minclosdi0) then begin minclosdi:=ak,i; closdi:=k; end; end; for j:=2 to n do writeln(j,closdj); end.Kruskal算法作用：也是

30、求最小生成树。过程：设置一个b数组为已加入的顶点集合，每次找最小的一条边加入，直到所有的顶点加入集合。与PRIM的不同： Kruskal算法在森林中的两棵树之间 添安全边；Prim算法在单棵树上添安全边。 时间复杂度上要比PRIM低个常数，因为PRIM对点而KRUSKAL对边。对于一个稠密的完全图，边要比点多。相同点： 贪心，选择边权最小的安全边优化：并查集program Kruskal;var a:array1.150,1.150 of integer;b:array1.150 of set of byte;一个集合最多只有255个，可以自己写数组i,j,k,l,n,min:integer;

31、=init=procedure init;beginreadln(n);for i:=1 to n do begin for j:=1 to n do read(ai,j); readln;读入图 end;end;=find=procedure find;beginfor i:=1 to n do bi:=i;repeat min:=maxint; for i:=1 to n do for j:=1 to n do if (ai,j0) and (ai,j,l);until b1=1.n;end;=main=Begin init; find; end.求图的的关键路径此块内容我到现在也没有搞多清楚，大家一起看看，谁明白了交流一下（王建德紫皮书上有专门的一节）。下面给出一种讲解。关键路径问题利用AOV网络，对其进行拓扑排序能对工程中活动的先后顺序作出安排。但一个活动的完成总需要一定的时间，为了能估算出某个活动的开始时间，找出那些影响工程完成时间的最主要的活动，我们可以利用带权的有向网，图中的顶点表示一个活动结束（开始）的事件，图中的边表示