图论基础

一、图论的基础概念

以下概念不是定义，也不一定完全，只是一些常用的概念，比较通俗化。在以后具体的算法中再适当加入概念。

图： 由点和线组成的图形。 顶点： 图中的结点。

无向图： 边没有正反方向。

完全图： 在N个顶点的无向图中，边最大为n*（n-1）/2称为无向完全图 度： 与结点相连的边数。 有向图： 边有正反方向。

入度（出度）：连入（出）的边数。（对于有向图来说） 奇顶点：结点的度是奇数的点。

路径：如果从a到b可达（包括直接到达或者中间有其他结点）那么从a到b就有一条路径。一条路径就

是一种走法，路径的边数叫做路径长度。一条路径上的n个顶点的集合叫做连通集。

回路（环）：从a?b????a

简单路径：存在从a?b???e此条路径中每个结点不同。

有根图：有结点到其他任意结点连通，则此结点为根，一个图可以有多根。 连通图：若图中任意两个结点可以连通，则此图为连通图（无向图）。 强连通图：任意i到j都有从i到j的路径。（有向图） 强连通分支：强连通的最大子图。

道路：可以一笔画成的图，并且不重不漏。

*充分必要条件：图是连通的，且奇顶点的个数等于0或2

并且当且仅当奇顶点的个数为0时，图是一条回路（包括一个孤立的点） 二分图（应该是超纲的内容） 充要条件：图中无奇顶点。 具体算法以后补充。 Hamilton回路：经过图中每一个顶点一次的回路。

欧拉回路：图的一个回路,若它通过图中每条边一次且仅一次。

（有关问题：七桥问题，一笔画问题）

对于一个无向图，如果它每个点的度都是偶数，那么它存在一条欧拉回路；如果有且仅有2个点的度为奇数，那么它存在一条欧拉路；如果超过2个点的度为奇数，那么它就不存在欧拉路了。

图的存储结构

只总结了常用的存储结构

有相邻矩阵和邻接表两种，只介绍相邻矩阵的内容，邻接表运用了动态指针链表数据结构 实现起来比较麻烦。

无向图：

A[I，J] = 1 当I与J两个结点相邻时

= 0 当I与J两个结点不相邻时，或I=J （1=

且有：A[I，J]=A[J，I]，即邻接矩阵是对称的。

1

如上图（A）的邻接矩阵如下：

0 1 1 1 A = 1 0 1 1 1 1 0 0 1 1 0 0

有向图：

A[I，J] = P[I，J] 当I与J两个结点相邻，且权值为P[I，J]时 = 0 或∞ 当I与J两个结点不相邻时，或I=J

如上图（B）和（C）的邻接矩阵分别如下：

0 1 1 ∞ 5 8 ∞ 3

A = 0 0 1 A = 5 ∞ 2 ∞ 6

0 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;

{x[i],y[i]为第i条边的前一个顶点和后一个顶点} For i：=1 to n do Begin

Readln(x[i],y[i]);

{如果是无向图，那么将每一条边拆成两条边，分成第i条边和第i+n条边} x[i+n]:=y[i]; y[i+n]:=x[i]; end;

三、图的遍历

概念：从图中某一结点出发系统地访问图中所有结点，使每个结点恰好被访问一次，这种运算被图的遍历。

为了避免重复访问某个结点，可以设一个标志数组f[I]，未访问时值为FALSE，访问一次后就改

为TRUE。

分类：深度优先遍历和广度优先遍历。

重要性：DFS和BFS在图的遍历中和搜索算法中有很重要很重要的地位。必须灵活掌握。

深度优先遍历

从图中某个结点V0出发，访问此结点，然后依次访问从V0的未被访问的邻接点出发进行深度优先遍历，直到图中所有和V0有路径相通的结点均被访问到。若此时图中尚有结点未被访问，则另选图中一个未被访问的结点V1作为起点，重复上述过程，直至图中所有结点都被访问到为止。 如下面两个图的深度优先遍历结果分别为：a，b，c，d，e，g，f。

V1，V2，V4，V8，V5，V3，V6，V7。

2

通俗点 就是先顺着一条路走到底，访问完了这条路之后再回溯到最近的那个岔路口，走另一条路，依此

类推，直到访问完了所有的结点。

深度优先遍历的递归过程如下： procedure dfs(i:integer);

begin

write(i); {访问此结点，对结点进行操作，不一定是write}

f[i]:=true; {设置已访问标志} for j:=1 to n do

if (not f[j]) and (a[i,j]=1) then dfs(j); {j没有访问过，并且i和j相连}

end;

图如果连通，那么一次 dfs(1) 就可以遍历所有结点。图如果不连通，通过多次调用dfs访问所有的结点：

for i:=1 to n do if not f[i] then dfs(i);

在图论的那本黄皮书上，有一种非递归的dfs，感觉不是很简洁。代码如下： procedure dfs(s:integer); begin

i:=0; v:=s;

repeat

inc(i); l[v].k：=i; repeat u:=1;

while u<=n and g[v,u]=false do inc(u); g[v,u]:=false; g[u,v]:=false;

until (u=n+1) or (l[u].k=0);

if u<>n+1 then begin v:=u; 对u进行访问 l[u].f:=v; if l[v].k<>1 then v:=l[v].f; until l[v].k=1; end;

因为我觉得这没什么大用，所以没打注释。看起来有点麻烦，如果你觉得这对你用，那么可以看那本黄色的图论专题，上面有详细的讲解。

广度优先遍历

从图中某个结点V0出发，访问此结点，然后依次访问与V0邻接的、未被访问过的所有结点，然后再分别从这些结点出发进行广度优先遍历，直到图中所有被访问过的结点的相邻结点都被访问到。若此时图

3

中还有结点尚未被访问，则另选图中一个未被访问过的结点作为起点，重复上述过程，直到图中所有结点都被访问到为止。

如上面两个图的广度优先遍历结果分别为：a，b，d，e，f，c，g。

V1，V2，V3，V4，V5，V6，V7，V8。

通俗点： 广度优先遍历就是按层搜索，对于BFS网络上有一个很形象的比喻，“就像一滴墨水落在水面上，

并慢慢扩散”这一滴墨水就是BFS进行的第一个顶点i ，扩散的过程就是一个搜索的过程。

广度优先遍历的过程如下： Procedure bfs(i:integer); Begin

访问i结点； F[i]:=true;

While 队列非空 do {i 点进入队列} Begin

从队列中移出队首元素v； For j:=1 to n do

If (not f[i]) and (a[v,j]=1) then Begin

访问结点j； f[j]:=true; 顶点j进入队列； End; End;

End;

运用到队列的数据结构，很简单。就是用一个数组模拟，一共有两个指针，队首指针和队尾指针，对于数组中的元素进入之后就不变了，通过队首与队尾指针变化实现入队出队。 入队： inc(队尾)； a[队尾]：=数据； 出队： inc(队首)； 数据：=a[队首]

由于此过程中，出队的元素虽然已经出队，但仍是保留的，所以数据量大的时候很容易造成内存浪费，因此有一种优化，循环队列，很简单，加一个mod m就可以，我感觉一般可能用不到，所以就不打代码了。代码可以到王建德的那本紫皮上去找。

种子染色法

种子染色法是DFS和BFS的一种应用。可以求得图中连通子图的个数，一般用于无向图中。 既可以用BFS也可以用DFS实现。

初始时，每一个结点标号为0，color:=0; {color为编号} For i:=1 to n do If f[i]=0 then

begin

4

inc(color);

DFS(i)/BFS(i); {过程中的f[i]=ture 改成 f[i]:=color} end;

最后color的值为连通子图的个数。

每一个连通子图中各个结点的标号都是相同的。

在实际应用中种子染色法中对于color的设计，和如果进行染色是很灵活的。我讲的只是一种做题思路。 我感觉种子染色法还是很有用的。 关于DFS和BFS在搜索中应用，可以找刘麟汉搜索的那一节。 End.

四、图论的经典算法

图的经典算法是必须掌握的，背也要背过。联赛中考图论也是在经典算法的基础上，考的是灵活应用。所以经典算法是必要的工具。

图的经典算法有 求单源最短路径的迪杰斯特拉算法，SPFA算法，求负权回路的BELLMAN算法，多源最短路径的FLOYD算法，拓扑排序，最小生成树的prim和kruskal算法，求图的关键路径 下面给出各个算法的基础思想和源代码。 迪杰斯特拉算法

基本思想：贪心。 运用前提：所有的边不能是负数。

作用：求单源最短路径

过程：先假设有一个集合，存储已经确定的顶点。显然，最开始只有一个源点v1,再选择与v1路径最短的点加入集合，更新最短路的权。直到所有的顶点加入集合。 program dijkstra;

var v:array[1..1000] of boolean; ｛v布尔数组用来设定顶点是否已经访问｝ a:array[1..1000,1..1000] of integer;｛存储图｝ i,j,n,min,k:integer; begin

v[1]:=true; readln(n);

for i:=1 to n do for j:=1 to n do begin

read(a[i,j]);

end;

｛――――――读入图――――――――｝ for j:=2 to n do begin

min:=10000;｛设置最大值｝ for i:=1 to n do

if (not v[i]) and (a[1,i]<>0) and (a[1,i]

min:=a[1,i]; k:=i; end;

v[k]:=true;｛设置以访问标志｝ for i:=1 to n do

if (a[1,k]<>0) and (a[k,i]<>0) then

if (a[1,k]+a[k,i]

5

找到距离最短的顶点 更新最短权值

本文来源：https://www.bwwdw.com/article/xbnv.html