图算法小结(并查集)

（0）目录

图算法小结(prime与dijkstra对照)

图算法小结(并查集)

哈夫曼树 之 建树和编解码

1：起因

（1）关于图的算法1般是比较复杂的，自己在这方面也是比较弱的，首先是图的存储问题 和 遍历问题：

存储分为两种，邻接矩阵 和 临街表；遍历分为DFS 和 BFS两种，非常类似于2叉树的先跟遍历和层次遍历。

（2）图在实际利用中是非常广泛的，这与万物归1，万物相连的理论是1致的，两个物体之间有着千丝万缕的联系，我们成这类联系建立的网络为图（带权图）；联系的强弱为边的权重。

（3）图的1些复杂的算法，也是建立在两种遍历图的思想的基础上进行的，所以我们先从简单的谈起。

（4）图的相干知识：

图的定义：
       很简单，G(V,E)， V、E分别表示点和边的集合。       

图的表示：
       主要有两种，邻接矩阵和邻接表，前者空间复杂度，O(V2），后者为O(V+E)。因此，除非非常稠密的图(边非常多），1般后者优越于前者。

图的遍历：
       宽度遍历BFS(start):    (1) 队列Q=Empty，数组bool visited[V]={false...}. Q.push(start);
                                             (2) while (!Q.empty()){
                                                       u = Q.pop();  visited[u] = true;   //遍历u结点
                                                       foreach (u的每个邻接结点v) Q.push(v);
                                                    }   
       深度遍历DFS(start):     (1) 栈S=Empty, 数组bool visited[V]={false...}. S.push(start);
                                               (2) while (!S.empty()){
                                                       u = S.pop();
                                                       if (!visited[u]) visited[u] = true;   //遍历u结点
                                                       foreach (u的每个邻接结点v) S.push(v);
                                                    }
      两个算法很相似，主要区分在于1个使用队列，1个使用栈。队列是先入先出，所以访问u以后接下来就访问u中未访问过的邻接结点；而栈的落后先出，当访问u后，压入了u的邻接结点，在后面的循环中，首先访问u的第1个临接点v，接下来又将v的邻接点w压入S，这样接下来要访问的自然是w了。

最小生成树：
       (1)Prime算法:    (1) 集合MST=T=Empty，选取G中1结点u，T.add(u)
                                  (2) 循环|V|⑴次：
                                        选取1条这样的边e=min{(x,y) | x in T, y in V/T}
                                        T.add(y); MST.add(e);
                                  (3) MST即为所求
       (2) Kruskal算法   (1) 将G中所有的边排序并放入集合H中，初始化集合MST=Empty,初始化不相交集合T={{v1}, {v2}...}}，也即T中每一个点为1个集合。
                                    (2)  顺次取H中的最短边e(u,v)，如果Find-Set(u)!=Find-Set(v)（也即u、v是不是已在1棵树中），那末Union(u,v) （即u,v合并为1个集合)，MST.add(e);
                                    (3) MST即为所求

       这两个算法都是贪心算法，区分在于每次选取边的策略。证明该算法的关键在于1点：如果MST是图G的最小生成树，那末在子图G'中包括的子生成树MST' 也必定是G'的最小生成树。这个很容易反正，假定不成立，那末G'有1棵权重和更小的生成树，用它替换掉MST'，那末对G我们就找到了比MST更小的生成树，明显这与我们的假定(MST是最小生成树)矛盾了。
       理解了这个关键点，算法的正确性就好理解多了。对Prime，T于V/T两个点集都会各自有1棵生成树，最后要连起来构成1棵大的生成树，那末明显要选二者之间的最短的那条边了。对Kruskal算法，如果当前选取的边没有引发环路，那末正确性是明显的（对给定点集顺次选最小的边构成1棵树固然是最小生成树了），如果致使了环路，那末说明两个点都在该点集里，由于已构成了树（否则也不可能致使环路）并且1直都是挑尽量小的，所以肯定是最小生成树。

最短路径:
       这里的算法基本是基于动态计划和贪心算法的，经典算法有很多个，主要区分在于：有的是通用的，有的是针对某1类图的，例如，无负环的图，或无负权边的图等。
       单源最短路径（1） 通用（Bellman-Ford算法）：
                               （2） 无负权边的图(Dijkstra算法)：
                               （3） 无环有向图(DAG) ：
       所有结点间最短路径：
                               （1） Floyd-Warshall算法：
                               （2） Johnson算法：

关键路径 和 拓扑排序:

2：代码示例

（1）最简单的图的遍历问题

Lake Counting

Sample Input

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
Sample Output

3

要求输出图中连通分支的个数，最简单的图遍历问题。

图的常见遍历方式有两种：深度优先遍历和广度优先遍历，他们的作用是将图中的每一个点都访问1遍，只不过是顺序不同。

如果把图中的每条边长都相等（比如都是1）的话，深度优先遍历进程就是尽量深的去访问节点，具体进程为：

1.任意选定1个点p0作为遍历的出发点

2.当访问到某1个节点p1时，如果p1下面有未被遍历的子节点，我们就接着访问p1的某1个未被遍历子节点，并标记该子节点被访问过，

3.如果p1不存在未被访问的子节点，我们就退回到p1的父节点，并履行第2步

4.履行第2、3步，直到所有节点被访问过。

大家也看出来了，深度优先遍历的是1个递归的进程，因此很容易想到要用到栈这类数据结构，具体实现的时候可以用递归，也能够用栈。看个人习惯了。
广度优先遍历实现就要用到队列了。以下是poj2386不同实现方式的代码

（2）最小生成树 ---- prime实现 O(N2)

题意：北极有1些村落，现需要在这些村落间建立起通讯，有s个卫星频道，任何两个具有卫星频道的村落都可以直接通过卫星进行通讯而疏忽距离，没有卫星的村落通过无线电进行通讯，并且这两个村落的距离不能超过D，D值取决于无线电收发器的功率，功率越大，D值越大，但价格也越高，出于购买费用和保护费用的斟酌，所有村落的无线电收发器都相同，即D值相同，现要求在保证任意两个村落间都能直接或间接通讯，并且D值最小，输出这个最小值。就是输出最小生成树最大边的权值，但是卫星频道是不肯定因素。这道题有个很好的解法及证明。
其实题目意思是将1棵最小生成树转化成1个森林，森林里有S棵树，每棵树配1个卫星频道，并且使得森林里所有边中最长的边的长度最小
其实意思就是可以删除最小生成树中的S⑴条边，问剩下的边中最长的是多少
由于建图时每两个点之间都有边，是稠密图，故用Prim法比较好 ---- 有的题目也略微复杂1点，首先得判断是不是联通，再求最小生成树

#include <iostream> #include<cmath> #include<algorithm> using namespace std; const int INF = 1000000; const int MAX_SIZE = 501; double map[MAX_SIZE][MAX_SIZE]; double path[MAX_SIZE]; struct node { int x; int y; }point[MAX_SIZE]; //记录从顶点集U到V-U的代价最小的边的辅助数组定义 struct { int adjvex; double lowcost; }closedge[MAX_SIZE]; bool cmp(double a,double b)//从大到小偏序 { return a>b; } // 求距离 inline double CalDist(struct node &a, struct node &b) { double xx = (a.x-b.x); double yy = (a.y-b.y); return sqrt(xx*xx + yy*yy); } //用普里姆算法从第k个顶点动身构造网G的最小生产树T,N个顶点的图 void prim(int k,int n) { int i,j; for(j=1;j<=n;j++)//辅助数组初始化 { if(j!=k) { closedge[j].adjvex=k; closedge[j].lowcost=map[k][j]; } } closedge[k].lowcost=0; //初始，U={u},这里将0作为访问过的标志 int l=0; for(i=1;i<n;i++)//选择其余n⑴个顶点，这个i不无任何实际意义，仅仅是选取n⑴个点，记录次数而已 { double min=INF; for(j=1;j<=n;j++)//求出T的下1个结点：第k顶点，最小的，不成环（即未访问过） { if(closedge[j].lowcost!=0&&min>closedge[j].lowcost) { k=j; min=closedge[j].lowcost; } } closedge[k].lowcost=0; //第k顶点并入U集 path[l++]=map[k][closedge[k].adjvex]; //保存该边，要是求最小生成树的本钱，就得改成加和了，要是求最小生成树的最大边权值，就得比较最大值了 for(j=1;j<=n;j++) //新顶点并入U后重新选择最小边 { if(map[k][j]<closedge[j].lowcost) { closedge[j].adjvex=k; closedge[j].lowcost=map[k][j]; } }// end of for }// end of for } int main() { int t,m,n; int i,j; cin>>t; while(t--) { cin>>m>>n; // input for(i=1;i<=n;i++) { cin>>point[i].x>>point[i].y; } // init dist for(i=1;i<=n;i++) //求出

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠