提高组精英班 2017清北学堂集训笔记——图论( 二 ) _最小生成树

文章插图
1 //深度优先搜索 2 //利用栈，现将右子树压栈再将左子树压栈 3 void DepthFirstSearch(BitNode *root) 4 { 5stack nodeStack; 6nodeStack.push(root);//将根节点压栈7while (!nodeStack.empty())//栈不为空，继续压栈8{ 9BitNode *node = nodeStack.top();//引用栈顶 10cout << node->data << ' ';11nodeStack.pop();//弹出根节点 12if (node->right)//优先遍历右子树 13{14nodeStack.push(node->right);15}16if (node->left)17{18nodeStack.push(node->left);19}20}21 }
三、无根树变成有根树：
选择一个点作为根结点，开始遍历。
遍历到一个点时，枚举每一条连接它和另一个点的边。若另一个点不是它的父结点，那就是它的子结点。递归到子结点。
我们可以更加形象的比喻为：抓住一个点，把它拎起来构成一棵新的树。
四、并查集：
这是我学OI这么久以来觉得性价比最高的算法（简单又实用啊！！）,用来处理不相交合并和查询问题。
给大家推个超超超超级易懂的blog，保证一看就懂，这里我就不再详解了：
五、最小生成树：
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来描述所得到的最小生成树。
提高组精英班 2017清北学堂集训笔记——图论

文章插图
1 #include//普里姆算法 2 const int N=1050; 3 const int M=10050; 4 struct Edge//定义图类型结构体，a到b权值为c 5 { 6int a,b,c; 7 }edge[M]; 8 int n,m;//n个点，m条边9 bool black[N];//染黑这个点，表示这个点已经被选过了 10 int ans=0;//最小生成树权值和11 int main()12 {13int i,j,k;14scanf("%d%d",&n,&m);15for(i=1;i<=m;i++)16scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].c);17black[1]=1;//把第一个点染黑（从第一个点找起）18for(k=1;k
2.算法（适用于稀疏图）：
算法描述：
克鲁斯卡尔算法从另一途径求网的最小生成树。
假设连通网N=（V，{E}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{∮}），图中每个顶点自成一个连通分量。
在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。
依次类推，直至T中所有顶点都在同一连通分量上为止。
提高组精英班 2017清北学堂集训笔记——图论

文章插图
1 #include//克鲁斯卡尔算法 2 #include 3 #include 4 using namespace std; 5 const int N=1050; 6 const int M=10050; 7 struct Edge//定义图类型结构体 8 { 9int a,b,c;//a到b的权值为c10 }edge[M];11 int fa[N];//父亲数组12 int n,m;//n个节点，m条边13 int ans=0;//最小生成树权值和14 bool cmp(Edge x,Edge y)//比较权值大小 15 {16return (x.c