二分图匹配与最短路径问题

1、 什么是二分图？设G=(V,E)是一个无向图。如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。也就是说在二分图中，顶点可以分为两个集合X和Y，每一条边的两个顶点都分别位于X和Y集合中。如下图所示：二分图的基本性质 顶点可以分成A、B两个集合，每条边的两个顶点分别位于A、B集合中的图被称为二分图。 二分图中不含奇环。二分图的判定方法：用DFS对二分图进行黑白染色。如果某个点染成黑色，那么与这个点相连的所有点都必须染成白色，反之同理，如果染色过程中不出现矛盾，那么这就是一个二分图。怎样判定一个图是不是二分图？程序主要部分：int color

2、maxn;/判定节点u所在的连通分量是否为二分图bool bipartite(int u) for(int i = 0; i Gu.size(); i+) int v = Gui;/枚举每条边(u, v) if(colorv = coloru) return false;/结点v已着色，且和结点u的颜色冲突 if(!colorv) colorv = 3 coloru;/给结点v着与结点u相反的颜色 if(!bipartite(v) return false; return true;图的连通性问题无向图的连通分量（1）连通图 在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优

3、先搜索或广度优先搜索，便可访问到图中所有结点。（2）非连通图 在对无向图进行遍历时，对于非连通图，需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。 有向图的连通性 设D=为有向图， 对于任意的u, vV，如果存在从u到v的通路，则称u可达v，记为uv ，并规定任何顶点到自身总是可达的。 若D中任意两结点相互可达，则称D是强连通的。SCC的概念有向图中, u可达v不一定意味着v可达u. 相互可达则属于同一个强连通分量(Strongly Connected Component, SCC)有向图和它的转置的有向图和它的转置的强连通分

4、量相同强连通分量相同所有SCC构成一个DAG(有向无环图) 求强连通分量使用 Kosaraju算法 一、Kosaraju算法步骤： Step1、对有向图G做dfs（深度优先遍历），记录每个结点结束访问的时间(即节点出栈顺序，后出栈的点第二次先扫描) Step2、将图G逆置，即将G中所有弧反向。 Step3、按Step1中记录的结点结束访问时间从大到小对逆置后的图做dfs Step4、得到的遍历森林中每棵树对应一个强连通分量。二、Kosaraju算法求解过程实例下面结合实例说明Kosaraju算法的基本策略。图1给出了一个有向图G。ACBDEFGH图1 有向图GStep1：假设从DFS在遍历时按

5、照字母顺序进行，根据Kosaraju算法，在步骤1中我们得到的遍历顺序可以表达为A,C,B,D,D,B,C,AE,F,G,H,H,G,F,E 越后出栈的点先访问 第一步所得到的顺序即为：EFGHACBDStep2：根据算法第2步，将图G逆置，得到对应的反向图G如图2所示。AC图2 逆置图GGHBDEFACBDEFGH图1 有向图G Step3：根据步骤1得到的遍历序列，按照结点结束访问时间递减排序后的结果 EFGHACBD 下面，按照该结点序列顺序对逆置图G所深度优先遍历，得到的深度优先遍历森林如图3所示。森林中共有4棵树，其中(a)和(d)只有一个结点，这里认为单结点也是一个强联通分量（在实

6、际应用中可以根据实际需要将这种情况过滤掉）。AC图2 逆置图GGHBDEF图3 逆置图G的DFS生成森林GEFHBACD (a) (b) (c) (d) kasaraju 算法代码 #includeconst int MAXN = 100 + 10, INF = 1000000000;int visMAXN, orderMAXN, idMAXN; /是否遍历、第二次遍历的顺序、个点所属的强连通分量int n,m,number; /点数、边数、计数器int mapmaxmax; /图int net = 0;void init() /初始化 int i, j; scanf(%d%d, &n

7、, &m); for(i = 1; i = n; i+)for(j = 1; j = n; j+) mapij = INF; for(i=1;i=n;i+) mapii=0;void read() /读取数据 int i, a, b; number = n; for(i = 1; i = m; i+) scanf(%d%d, &a, &b); mapab = 1; void dfs1(int v) /第一次遍历确定点的顺序 int i; visv=1; for(i = 1; i = n; i+)if(mapviINF & visi!=1) dfs1(i);ord

8、ernumber = v;/出栈的时候记录顺序于ORDER数组number-;void dfs2(int v) int i; visv = 1; idv = number;/V点所属的连通分量 for(i =1; i = n; i+) if(mapivinf & visi!=1) dfs2(i);void kosaraju() int i, j; for(i = 1; i = n; i+)/第一次DFS确定第二次DFS顺序 if(!visi) dfs1(i); number = 0; for(i = 1; i = n; i+) visi = 0; for(i = 1; i = n; i

9、+) if(visorderi!=1) number+;/连通分量标记 dfs2(orderi);ACBDEFGH图1 有向图Gint main() int i, j; init(); read(); kosaraju(); for(i = 1; i ,i); for(j=1;jl uW u v( )( , ) 则令l v( )=l uW u v( )( , ),z v( )= u先写出带权邻接矩阵： 03064093021509701608120W因 G 是无向图，故 W是对称阵 TO MATLAB(road1)u1u2u3u4u5u6u7u8218152939763416第0步u2u3u4

10、u5u6u7u82181529397634162(u1)8(u1)1(u1)u1第1步u3u2u3u4u5u6u7u82181529397634162(u1)8(u1)1(u1)u1第2步u310(u1,u3)u2u2u3u4u5u6u7u82181529397634162(u1)8(u1)1(u1)u1第3步u310(u1,u3)u23(u1,u2)u5u2u3u4u5u6u7u82181529397634162(u1)8(u1)1(u1)u1第4步u310(u1,u3)u23(u1,u2)u66(u1,u2, u5)12(u1,u2,u5)u5u2u3u4u5u6u7u8218152939

11、7634162(u1)8(u1)1(u1)u1第5步u310(u1,u3)u23(u1,u2)u66(u1,u2, u5)12(u1,u2,u5)u57(u1,u2,u5,u6)u4u2u3u4u5u6u7u82181529397634162(u1)1(u1)u1第6步u310(u1,u3)u23(u1,u2)u66(u1,u2, u5)12(u1,u2,u5)u57(u1,u2,u5,u6)u49(u1,u2,u5,u6,u4)u7u8u3u4u6u7u1u3u2u6u5u4u7u81243553317284例2 求出点1到其余各顶点的最短有向路的长度？例例3 狼、羊、白菜问题狼、羊、白菜问

12、题狼、羊、白菜过河问题狼、羊、白菜过河问题 猎人要把一只狼、一头羊和一篮白菜从河的左岸带到右岸，但他的渡船太小，一次只能带一样。因为狼要吃羊，羊会吃白菜，所以狼和羊，羊和白菜不能在无人监视的情况下相处。问猎人怎样才能达到目的？ 人、狼、羊、菜四种的任意组合共有16种。其中狼羊菜、狼羊、羊菜三种不允许出现，所以人、人狼、人菜也不允许出现。因此，允许出现的情况共有以下10种情况：人狼羊菜、人狼羊、人狼菜、人羊菜、人羊、狼菜、狼、菜、羊及空。把这10种状态视为10个点，若一种状态通过一次摆渡后可变为另一种状态，则在两种状态（点）之间画一直线 ，得示意图如下：7424613503 将各顶点到“人狼羊菜

13、”的距离标在图中各顶点处，可知有两种最迅速最安全的渡河方案： （1）人狼羊菜狼菜人狼菜狼 人狼羊羊 人羊空； （2）人狼羊菜狼菜人狼菜菜 人羊菜羊 人羊空；每种方案都要七次。 这种“用顶点代表状态，边代表状态间的转移”的状态转移图模型颇具代表性任何具有有限个状态的多步决策问题都可以类似地建立图的模型，利用图论工具来解决 这样摆渡问题就转化成在图中找出以“人狼羊菜”为起点，以“空”为终点的简单路。int gMAXNMAXN, n;void Dijkstra(int s, int t) int i, distMAXN, visMAXN; memset(vis, false, sizeof(vis)

14、; for(i = 1; i = n; i+) disti = INF; dists = 0; while(true) int u = -1, mind = INF;for(i = 1; i = n; i+) if(!visi & distimind) u = i;mind = disti; if(u = -1) break;visu = true;for(i = 1; i distu+gui)disti = distu+gui; return distt;Dijkstra算法的主要部分：二、任意两点间的最短路问题二、任意两点间的最短路问题算法原理算法原理 求距离矩阵的方法求距离矩阵的

15、方法把带权邻接矩阵 W 作为距离矩阵的初值，即 D(0)=)()0(ijd=W（）D(1)= )() 1 (ijd，其中)0(1)0() 1 (,miniijijddd)0(1jd)1(ijd是从 vi到 vj的只允许以 v1作为中间点的路径中最短路的长度（2）D(2)= )()2(ijd，其中) 1 (2) 1 ()2(,miniijijddd)1 (2 jd )2(ijd是从 vi到 vj的只允许以 v1 、 v2作为中间点的路径中最短路的长度（）D()=)()(ijd，其中)1()1()(,miniijijddd)1( jd)(ijd是从 vi到 vj的只允许以 v1、v2、v作为中间点

16、的路径中最短路的长度即是从 vi到 vj中间可插入任何顶点的路径中最短路的长，因此D()即是距离矩阵算法原理算法原理 求路径矩阵的方法求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R ij算法原理算法原理 查找最短路路径的方法查找最短路路径的方法若1)(prij，则点 p1是点 i 到点 j 的最短路的中间点.然后用同样的方法再分头查找若：（） 向点 i 追朔得：2)(1prip,3)(2prip,kipprk)(（） 向点 j 追朔得：1)(1qrjp,2)(1qrjq,jrjqm)(pkp2p1p3q1q2qm则由点i到j的最短路的路径为：jqqqpppimk,21, 12算法步骤算法

17、步骤D(i,j)：i 到 j 的距离R(i,j)：i 到 j 之间的插入点输入: 带权邻接矩阵 w(i,j)例例 求下图中加权图的任意两点间的距离与路径v1v2v4v3v5937422第0步( 0 )( 0 )09312345902712345, 2024123453201234574012345DR(1)(1)09312345902712345, 2024123453201234574012345DR121211第2步( 2 )( 2 )0931234590212712315, 202412345312201134574012345DR111116161919222222(3 )(3 )15

18、3463346331566091131224902123, 112024223453201344035333DR第3步( 4 )( 4 )031402462333, 7594447 2024234534206133436460453343495DR第4步(5 )( 4 )(5 )( 4 ), DDRR TO MATLAB(road2(floyd)由 v4向 v1追朔：141r所以从 v5到 v1的最短路径为：1435.const int INF = 1000000000, MAXN = 1010;int gMAXNMAXN, n;void Floyd() int i, j, k, distMA

19、XNMAXN; for(i = 1; i = n; i+)for(j = 1; j = n; j+) distij = INF; for(k = 1; k = n; k+)for(i = 1; i = n; i+) for(j = 1; j distik + distkj) distij = distik + distkj;Floyd算法的主要部分：例例1 1 某工厂使用一种设备，这种设备在一定的年限内随着某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备，每年需支付购置费用；若继续使用旧否更新。若购置设备，每年需支付购置费用；若继续使用旧设备，需要支付维修与运行费用，而且随着设备的老化会逐设备，需要支付维修与运行费用，而且随着设备的老化会逐年增加。计划期（五年）内中每年的购置费、维