锐客网

  1. 首页 > it技术 > >

最小生成树|NOIP大纲整理（（十一）图论详解）

知识点罗列：
1、图的存储： 1.1 邻接矩阵1.2 邻接表
2、树的遍历： 2.1 bfs2.2 dfs
3、无根树变有根树
4、并查集
5、最小生成树5.1 k算法5.2 p算法5.3 最小生成树计数问题
6、最短路径6.1 floyd6.2 d算法 6.3 spfa6.4 bellmanford算法
7、拓扑排序
8、联通分量
9、欧拉回路与哈密顿路径
-----------------------------------------------------------------------------------------------------------------------------------------------------------
以下是正文
-----------------------------------------------------------------------------------------------------------------------------------------------------------
一、图的存储
1、邻接矩阵：邻接矩阵很方便，但是在n过大或者为稀疏图时，就会很损耗时空，不建议使用！
假设有n个节点，建立一个n×n的矩阵，第i号节点能到达第j号节点就将[i][j]标记为1（有权值标记为权值），
样例如下图：

最小生成树|NOIP大纲整理（（十一）图论详解）
文章图片

暂时代码是转载的，以后有机会会更新，看不懂请跳过

/*无向图，无权值*/ int a[MAXN][MAXN]; //邻接矩阵 int x,y; //两座城市 for(int i=1; i<=n; i++) { for(intj=1; j<=n; j++) { scanf("%d%d",&x,&y); //能到达，互相标记为1 a[x][y]=1; a[y][x]=1; } } /*无向图，有权值*/ int a[MAXN][MAXN]; //邻接矩阵 int x,y,w; //两座城市，路径长度 for(int i=1; i<=n; i++) { for(intj=1; j<=n; j++) { scanf("%d%d%d",&x,&y,&w); //能到达，互相标记为权值w a[x][y]=w; a[y][x]=w; } } /*有向图，无权值*/ int a[MAXN][MAXN]; //邻接矩阵 int x,y; //两座城市 for(int i=1; i<=n; i++) { for(intj=1; j<=n; j++) { scanf("%d%d",&x,&y); //能到达，仅仅是x到y标记为1 a[x][y]=1; } } /*有向图，有权值*/ int a[MAXN][MAXN]; //邻接矩阵 int x,y,w; //两座城市，路径长度 for(int i=1; i<=n; i++) { for(intj=1; j<=n; j++) { scanf("%d%d%d",&x,&y,&w); //能到达，仅仅是x到y标记为权值w a[x][y]=w; } }

2.邻接表
邻接表是一个二维容器，第一维描述某个点，第二维描述这个点所对应的边集们。
邻接表由表头point，链点构成，如下图是一个简单无向图构成的邻接表：

最小生成树|NOIP大纲整理（（十一）图论详解）
文章图片

我们可以用指针来创建链表，当然，这是很复杂也很麻烦的事情，下面来介绍一种用数组模拟链表的方法：
暂时代码是转载的，以后有机会会更新，看不懂请跳过
//有向图邻接表存储 const int N=1005; const int M=10050; int point[N]={0}; //i节点所对应链表起始位置（表头） int to[M]={0}; int next[M]={0}; //i节点下一个所指的节点 int cc=0; //计数器（表示第几条边） void AddEdge(int x,int y)//节点x到y { cc++; to[cc]=y; next[cc]=point[x]; point[x]=cc; } void find(int x) { int now=point[x]; while(now) { printf("%d\n",to[now]); now=next[now]; } } int main() {}

如果要加强记忆的话可以用我所给的例子模拟一下point[],to[],next[]，然后再调用函数find(x)来输出x这个节点能到的点，大概就能YY到数组是怎么存储邻接表的了。 还是不理解的话，推一个blog，这里面说的和我这里给出的思路很相似：http://developer.51cto.com/art/201404/435072.htm


二、树的遍历
1.BFS
运用队列，一开始队列中有一个点，将一个点出队，将它的子结点全都入队。
算法会在遍历完一棵树中每一层的每个结点之后，才会转到下一层继续，在这一基础上，队列将会对算法起到很大的帮助：

最小生成树|NOIP大纲整理（（十一）图论详解）
文章图片

暂时代码是转载的，以后有机会会更新，看不懂请跳过
//广度优先搜索 void BreadthFirstSearch(BitNode *root) { queuenodeQueue; nodeQueue.push(root); //将根节点压入队列 while(!nodeQueue.empty())//队列不为空，继续压入队列 { BitNode *node =nodeQueue.front(); nodeQueue.pop(); //弹出根节点 if(node->left)//左儿子不为空 { nodeQueue.push(node->left); //压入队列 } if(node->right)//右儿子不为空 { nodeQueue.push(node->right); //压入队列 } } }

2.DFS
运用栈，递归到一个点时，依次递归它的子结点。
还可以利用堆栈的先进后出的特点，现将右子树压栈，再将左子树压栈，这样左子树就位于栈顶，可以保证结点的左子树先与右子树被遍历：

最小生成树|NOIP大纲整理（（十一）图论详解）
文章图片

暂时代码是转载的，以后有机会会更新，看不懂请跳过
//深度优先搜索 //利用栈，现将右子树压栈再将左子树压栈 void DepthFirstSearch(BitNode *root) { stacknodeStack; nodeStack.push(root); //将根节点压栈 while(!nodeStack.empty())//栈不为空，继续压栈 { BitNode *node =nodeStack.top(); //引用栈顶 cout <data << ' '; nodeStack.pop(); //弹出根节点 if(node->right)//优先遍历右子树 { nodeStack.push(node->right); } if (node->left) { nodeStack.push(node->left); } } }

三、无根树变成有根树
选择一个点作为根结点，开始遍历。
遍历到一个点时，枚举每一条连接它和另一个点的边。若另一个点不是它的父结点，那就是它的子结点。递归到子结点。
我们可以更加形象的比喻为：抓住一个点，把它拎起来构成一棵新的树。

四、并查集
这是我学OI这么久以来觉得性价比最高的算法（简单又实用啊！！）,用来处理不相交合并和查询问题。
给大家推个超超超超级易懂的blog，保证一看就懂，这里我就不再详解了：http://blog.csdn.net/dellaserss/article/details/7724401

五、最小生成树
1.Prim算法（适用于稠密图）
算法描述：
1).输入：一个加权连通图，其中顶点集合为V，边集合为E；
2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
3).重复下列操作，直到Vnew = V：
a.在集合E中选取权值最小的边，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
b.将v加入集合Vnew中，将边加入集合Enew中；
4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。

最小生成树|NOIP大纲整理（（十一）图论详解）
文章图片

暂时代码是转载的，以后有机会会更新，看不懂请跳过
#include//普里姆算法 const int N=1050; const int M=10050; struct Edge//定义图类型结构体，a到b权值为c { int a,b,c; }edge[M]; int n,m; //n个点，m条边 bool black[N]; //染黑这个点，表示这个点已经被选过了 int ans=0; //最小生成树权值和 int main() { int i,j,k; scanf("%d%d",&n,&m); for(i=1; i<=m; i++) scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].c); black[1]=1; //把第一个点染黑 for(k=1; k


2.kruskal算法（适用于稀疏图）
算法描述：
克鲁斯卡尔算法从另一途径求网的最小生成树。
假设连通网N=（V，{E}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{∮}），图中每个顶点自成一个连通分量。
在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。
依次类推，直至T中所有顶点都在同一连通分量上为止。

最小生成树|NOIP大纲整理（（十一）图论详解）
文章图片

暂时代码是转载的，以后有机会会更新，看不懂请跳过
#include//克鲁斯卡尔算法 #include #include using namespace std; const int N=1050; const int M=10050; struct Edge//定义图类型结构体 { int a,b,c; //a到b的权值为c }edge[M]; int fa[N]; //父亲数组 int n,m; //n个节点，m条边 int ans=0; //最小生成树权值和 bool cmp(Edge x,Edge y)//比较权值大小 { return (x.c

经典例题：繁忙的都市

3.最小生成树计数问题
题目：现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。
解法：按边权排序，先选小的，相同边权的暴力求出有几种方案，将边按照权值大小排序，将权值相同的边分到一组，统计下每组分别用了多少条边。然后对于每一组进行dfs，判断是否能够用这一组中的其他边达到相同的效果。最后把每一组的方案数相乘就是答案。
换句话说：就是不同的最小生成树方案，每种权值的边的数量是确定的，每种权值的边的作用是确定的, 排序以后先做一遍最小生成树，得出每种权值的边使用的数量x然后对于每一种权值的边搜索，得出每一种权值的边选择方案。
#include #include #define N 105 #define M 1005 #define MOD 31011 using namespace std; struct node//定义图类型结构体 { int a,b; //节点a，b int zhi; //a到b的权值 }xu[M]; int n,m; int fa[N]; int lian[N]; int ans=1; int cmp(struct node x,struct node y)//从小到大排序函数 { return(x.zhi

六、最短路径
1.Floyd算法（插点法）
通过一个图的权值矩阵求出它的每两点间的最短路径（多源最短路）。
算法描述：
一个十分暴力又经典的DP，假设i到j的路径有两种状态：
①i和j直接有路径相连：最小生成树|NOIP大纲整理（（十一）图论详解）
文章图片

②i和j间接联通，中间有k号节点联通：最小生成树|NOIP大纲整理（（十一）图论详解）
文章图片

假设dis[i][j]表示从i到j的最短路径，对于存在的每个节点k，我们检查一遍dis[i][k]+dis[k][j]。
//Floyd算法，时间复杂度：O(n^3) int dis[MAXN][MAXN]; for(k=1; k<=n; k++)//枚举 { for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); //DP } } }

2.Dijkstra算法（无向图，无负权边）

算法描述：
多源最短路！
a. 初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则正常有权值，若u不是v的出边邻接点，则权值为∞。
b. 从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
c. 以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
d. 重复步骤b和c直到所有顶点都包含在S中。
还是举个例子吧！如下图！

最小生成树|NOIP大纲整理（（十一）图论详解）
文章图片

我们假设1号节点为原点。
第一轮，我们可以算出2,3,4,5,6号节点到原点1的距离为[7,9,∞,∞,14]，∞表示无穷大（节点间无法直接连通），取其中最小的7，就确定了1->1的最短路径为0，1->2的最短路径为7，同时去最短路径最小的2节点为下一轮的前驱节点。
第二轮，取2节点为前驱节点，按照前驱节点到原点的最短距离 + 新节点到前驱节点的距离来计算新的最短距离，可以得到3,4,5,6号节点到原点1的距离为[17,22,∞,∞]（新节点必须经过2号节点回到原点），这时候需要将新结果和上一轮计算的结果比较，3号节点：17>9，最短路径仍然为9；4号节点：22<∞，更新4号节点的最短路径为22,；5号节点：仍然不变为∞；6号节点：14<∞，更新6号节点的最短路径为14。得到本轮的最短距离为[9,22,∞,14]，1->3的最短路径为9，同时取最短路径最小的3节点为下一轮的前驱节点。
第三轮：同理上，以3号节点为前驱节点，可以得到4,5,6号节点到原点1的距离为[20,∞,11]，根据最短路径原则，和上一轮最短距离比较，刷新为[20,∞,11]，1->3->6的最短路径为11，同时取最短路径最小的6节点为下一轮的前驱节点。
第四轮：同理，得到4,5号节点最短距离为[20,20]，这两个值相等，运算结束，到达这两个点的最短距离都是20，如果这两个值不相等，还要进行第五轮运算！
#include #include const int N=100500; const int M=200500; int point[N]={0},to[M]={0},next[M]={0},len[M]={0},cc=0; int dis[N]; //最短路长度 bool ever[N]; //当前节点最短路有没有确定 int n,m; void AddEdge(int x,int y,int z)//添加新的边和节点：x到y边长z { cc++; next[cc]=point[x]; point[x]=cc; to[cc]=y; len[cc]=z; //len记录x到y的边长 } int main() { int i,j,k; scanf("%d%d",&n,&m); for(i=1; i<=m; i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); AddEdge(a,b,c); //无向图，要加两遍 AddEdge(b,a,c); } memset(dis,0x3f,sizeofdis); //用极大值来初始化 dis[1]=0; //1号节点到自己最短距离为0 for(k=1; k<=n; k++) { intminp,minz=123456789; for(i=1; i<=n; i++) { if(!ever[i]) { if(dis[i]dis[minp]+len[now]) dis[tox]=dis[minp]+len[now]; now=next[now]; } } for(i=1; i<=n; i++) printf("%d\n",dis[i]); return 0; }


3.SPFA算法（有负权边，无负圈，能检测负圈但不能输出）
SPFA和Dijkstra极为相似，只是加了个队列优化来检测负圈和负权边。
算法描述：
建立一个队列，初始时队列里只有起始点，再建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点作为起始点去刷新到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。
判断有无负环：
如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）
#include #include const int N=100500; const int M=200500; int point[N]={0},to[M]={0},next[M]={0},len[M]={0},cc=0; int dis[N]; //最短路长度 int queue[N],top,tail; //双向队列queue，队头，队尾 bool in[N]; //记录这个点在不在队列中，1表示在，0表示不在 int n,m; //n个节点，m条边 void AddEdge(int x,int y,int z)//x到y边长为z { cc++; next[cc]=point[x]; point[x]=cc; to[cc]=y; len[cc]=z; } int main() { int i,j; scanf("%d%d",&n,&m); for(i=1; i<=m; i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); AddEdge(a,b,c); //因为是双向队列，左边加一次，右边加一次 AddEdge(b,a,c); } memset(dis,0x3f,sizeofdis); //用极大值来初始化 dis[1]=0; //1号节点到自己最短距离为0 top=0; tail=1; queue[1]=1; in[1]=1; //初始化，只有原点加入 while(top!=tail) { top++; top%=N; intnow=queue[top]; in[now]=0; int ed=point[now]; while(ed) { inttox=to[ed]; if(dis[tox]>dis[now]+len[ed]) { dis[tox]=dis[now]+len[ed]; if(!in[tox]) { tail++; tail%=N; queue[tail]=tox; in[tox]=1; } } ed=next[ed]; } } for(i=1; i<=n; i++) printf("%d\n",dis[i]); return 0; }


4.BellmanFord算法（有负权边，可能有负圈，能检测负圈并输出）
算法描述：
1.初始化：将除源点外的所有顶点的最短距离估计值 d[all]=+∞, d[start]=0;
2.迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）
3.检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 d[v]中。
简单的说，如下图所示：

最小生成树|NOIP大纲整理（（十一）图论详解）
文章图片

松弛计算之前，点B的值是8，但是点A的值加上边上的权重2，得到5，比点B的值（8）小，所以，点B的值减小为5。这个过程的意义是，找到了一条通向B点更短的路线，且该路线是先经过点A，然后通过权重为2的边，到达点B
如果出现了以下情况：

最小生成树|NOIP大纲整理（（十一）图论详解）
文章图片

松弛操作后，变为7,7>6，这样就不修改（Bellman Frod算法的高妙之处就在这），保留原来的最短路径就OK，代码实现起来非常简单。
int n,m; //n个点，m条边 struct Edge//定义图类型结构体 { int a,b,c; //a到b长度为c }edge[]; int dis[]; memset(dis,0x3f,sizeof dis); dis[1]=0; for(int i=1; idis[edge[j].a]+edge[j].c) { dis[edge[j].b]=dis[edge[j].a]+edge[j].c; } } }


七、拓扑排序
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。
打个比喻：我们要做好一盘菜名字叫做红烧茄子，那么第一步得买茄子和配料，第二步就是要洗茄子，第三步就是要开始倒油进锅里啊什么七七八八的，第四步…，你不可能先洗茄子再买茄子和配料，这样的一些事件必须是按照顺序进行的，这些依次进行的事件就构成了一个拓扑序列。
算法描述：
我们需要一个栈或者队列，两者都可以无所谓，只是找个容器把入度为0的元素维护起来而已。
①从有向图中选择一个入度为0（无前驱）的顶点，输出它。
②从网中删去该节点，并且删去从该节点出发的所有有向边。
③重复以上两步，直到剩余的网中不再存在没有前驱的节点为止。
具体操作过程如下：
若栈非空，则在栈中弹出一个元素，然后枚举这个点能到的每一个点将它的入度-1（删去一条边），如果入度=0，则压入栈中。
如果没有输出所有的顶点，则有向图中一定存在环
//拓扑排序，时间复杂度：O(n+m) #include #include const int N=100500; const int M=200500; int point[N]={0},to[M]={0},next[M]={0},cc=0; int xu[N]={0}; //栈，初始值为空，xu[0]表示栈的大小 int in[N]={0}; //入度，a可以到达b，in[b]++ int ans[N]={0}; //ans[0]整个拓扑序列的大小 int n,m; void AddEdge(int x,int y)//邻接表a到b { cc++; next[cc]=point[x]; point[x]=cc; to[cc]=y; } int main() { int i,j; scanf("%d%d",&n,&m); for(i=1; i<=m; i++) { int a,b; scanf("%d%d",&a,&b); in[b]++; //统计每个节点的入度 AddEdge(a,b); } for(i=1; i<=n; i++) { if(in[i]==0)//这个节点入度为0，压入栈 xu[++xu[0]]=i; } while(xu[0]) { int now=xu[xu[0]]; //出栈 xu[0]--; ans[++ans[0]]=now; int ed=point[now]; while(ed) { inttox=to[ed]; in[tox]--; if(!in[tox]) xu[++xu[0]]=tox; ed=next[ed]; //找下一个相邻节点 } } if(ans[0]

八、联通分量

强连通：有向图中，从a能到b并且从b可以到a，那么a和b强连通。
强连通图：有向图中，任意一对点都满足强连通，则这个图被称为强连通图。
强联通分量：有向图中的极大强连通子图，就是强连通分量。
一般用Tarjan算法求有向图强连通分量：
推一个蛮容易理解的blog：http://www.cnblogs.com/uncle-lu/p/5876729.html

九、欧拉路径与哈密顿路径

1.欧拉路径：从某点出发一笔画遍历每一条边形成的路径。
欧拉回路：在欧拉路径的基础上回到起点的路径（从起点出发一笔画遍历每一条边）。
欧拉路径存在：
无向图：当且仅当该图所有顶点的度数为偶数或者除了两个度数为奇数外其余的全是偶数。
有向图：当且仅当该图所有顶点出度=入度或者一个顶点出度=入度+1，另一个顶点入度=出度+1，其他顶点出度=入度
欧拉回路存在：
无向图：每个顶点的度数都是偶数，则存在欧拉回路。
有向图：每个顶点的入度都等于出度，则存在欧拉回路。
求欧拉路径/欧拉回路算法常常用Fleury算法：
再推一个蛮容易理解的blog：http://www.cnblogs.com/Lyush/archive/2013/04/22/3036659.html

2.哈密顿路径：每个点恰好经过一次的路径是哈密顿路径。
哈密顿回路：起点与终点之间有边相连的哈密顿路径是哈密顿回路。
【最小生成树|NOIP大纲整理（（十一）图论详解）】

    推荐阅读


    上一篇：3D球体一个（纪念第一个opengl程序～～）

    下一篇：论文|【论文学习】3D Convolutional Neural Networks for Human Action Recognition