**
** 图论
一、图的存储：
1、邻接矩阵： 假设有n个节点，建立一个n×n的矩阵，第i号节点能到达第j号节点就将[i][j]标记为1（有权值标记为权值）， 样例如下图：
/无向图，无权值/ int a[MAXN][MAXN];//邻接矩阵 int x,y;//两座城市 for(int i=1;i<=n;i++) { for(int j=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(int j=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(int j=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(int j=1;j<=n;j++) { scanf("%d%d%d",&x,&y,&w);//能到达，仅仅是x到y标记为权值w a[x][y]=w; } }
邻接矩阵很方便，但是在n过大或者为稀疏图时，就会很损耗时空，不建议使用！
2.邻接表： 邻接表是一个二维容器，第一维描述某个点，第二维描述这个点所对应的边集们。 邻接表由表头point，链点构成，如下图是一个简单无向图构成的邻接表：
我们可以用指针来创建链表，当然，这是很复杂也很麻烦的事情，下面来介绍一种用数组模拟链表的方法： //有向图邻接表存储 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：运用队列，一开始队列中有一个点， 将一个点出队，将它的子结点全都入队。 算法会在遍历完一棵树中每一层的每个结点之后，才会转到下一层继续，在这一基础上，队列将会对算法起到很大的帮助：
//广度优先搜索 void BreadthFirstSearch(BitNode root) { queue<BitNode> nodeQueue; 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：运用栈，递归到一个点时，依次递归它的子结点。 还可以利用堆栈的先进后出的特点，现将右子树压栈，再将左子树压栈，这样左子树就位于栈顶，可以保证结点的左子树先与右子树被遍历：
//深度优先搜索 //利用栈，现将右子树压栈再将左子树压栈 void DepthFirstSearch(BitNode root) { stack<BitNode> nodeStack; nodeStack.push(root);//将根节点压栈 while (!nodeStack.empty())//栈不为空，继续压栈 { BitNode *node = nodeStack.top();//引用栈顶 cout << node->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, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）； b.将v加入集合Vnew中，将<u, v>边加入集合Enew中； 4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。
#include<stdio.h>//普里姆算法 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<n;k++) { int mind,minz=123456789; for(i=1;i<=m;i++)//开始！ { if(black[edge[i].a]!=black[edge[i].b]&&edge[i].c<minz)//如果这个点未被找过并且权值比当前最优值还要小，更新之 { mind=i;//记录当前最优点 minz=edge[i].c;//记录当前最小边权 } } ////将这最优点归入 ans+=minz;//答案加上 black[edge[mind].a]=1;//染黑两个节点 black[edge[mind].b]=1; // } printf("%d\n",ans);//输出答案 return 0; }
2.kruskal算法（适用于稀疏图）：
算法描述： 克鲁斯卡尔算法从另一途径求网的最小生成树。 假设连通网N=（V，{E}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{∮}），图中每个顶点自成一个连通分量。 在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。 依次类推，直至T中所有顶点都在同一连通分量上为止。
#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<y.c); } int getf(int x)//寻找x的最原始祖先（并查集） { if(fa[x]!=x) fa[x]=getf(fa[x]); return fa[x];//返回最原始祖先 } int main() { int i,j; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].c); sort(edge+1,edge+m+1,cmp);//从小到大排序边数组 for(i=1;i<=n;i++) fa[i]=i;//初始值，每个节点的父亲就是自己 for(i=1;i<=m;i++) { int a=edge[i].a; int b=edge[i].b; a=getf(a);//寻找a的最原始祖先 b=getf(b);//寻找b的最原始祖先 if(a!=b)//如果两个的最终祖先不相同（不会构成回路） { ans+=edge[i].c;//加入 fa[a]=b;//加入当前父亲的儿子们中（合并并查集） } } printf("%d\n",ans); return 0; }
经典例题：繁忙的都市（Luogu 2330） 城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求： 1．改造的那些道路能够把所有的交叉路口直接或间接的连通起来。 2．在满足要求1的情况下，改造的道路尽量少。 3．在满足要求1、2的情况下，改造的那些道路中分值最大的道路分值尽量小。 任务：作为市规划局的你，应当作出最佳的决策，选择那些道路应当被修建。 这题是经典的最小瓶颈生成树问题：只用边权小于等于x的边，看看能不能构成最小生成树。 在kruskal算法中，我们已经对边从小到大排过序了，所以只要用≤x的前若干条边即可。
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<y.zhi); } int getf(int x) { if(fa[x]!=x) fa[x]=getf(fa[x]); return(fa[x]); } int getlian(int x) { if(lian[x]x) return x; return ( getlian(lian[x]) ); } int dfs(int now,int end,int last) { if(nowend) { if(last0) return 1; return 0; } int res=dfs(now+1,end,last); int s=getlian(xu[now].a); int t=getlian(xu[now].b); if(s!=t) { lian[s]=t; res+=dfs(now+1,end,last-1); lian[s]=s; } return res; } int main() { int i,j,k; int s,t; int now; int sum=0; scanf("%d%d",&n,&m); for(i=1;i<=n;i++)//初始化，每个节点的父亲就是自己 fa[i]=i; for(i=1;i<=m;i++) scanf("%d%d%d",&xu[i].a,&xu[i].b,&xu[i].zhi); sort(xu+1,xu+m+1,cmp);//从小到大排序边数组 for(i=1;i<=m;) { for(j=1;j<=n;j++) lian[j]=j; k=i; while(i<=m&&xu[i].zhixu[k].zhi) { xu[i].a=getf(xu[i].a); xu[i].b=getf(xu[i].b); i++; } now=sum; for(j=k;j<i;j++) { s=getf(xu[j].a); t=getf(xu[j].b); if(s!=t) { sum++; fa[s]=t; } } ans*=dfs(k,i,sum-now); ans%=MOD;//防止溢出 } if(sum!=n-1) ans=0; printf("%d\n",ans); return 0; }
