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

我们进入一个新的模块——图论！
这个专题更出来可能有点慢别介意，原因是要划的图和要给代码加的注释比较多，更重要的就是。。。这几个晚上我在追剧！！我们的少年时代超级超级超级好看，剧情很燃啊！！咳咳，好吧下面回归正题。
一、图的存储：
1、邻接矩阵：
假设有n个节点，建立一个n×n的矩阵，第i号节点能到达第j号节点就将[i][j]标记为1（有权值标记为权值），
样例如下图：

文章插图
1 /*无向图，无权值*/ 2 int a[MAXN][MAXN];//邻接矩阵3 int x,y;//两座城市4 for(int i=1;i<=n;i++) 5 { 6for(int j=1;j<=n;j++) 7{ 8scanf("%d%d",&x,&y);//能到达，互相标记为19a[x][y]=1;10a[y][x]=1;11}12 }13 /*无向图，有权值*/14 int a[MAXN][MAXN];//邻接矩阵 15 int x,y,w;//两座城市，路径长度 16 for(int i=1;i<=n;i++)17 {18for(int j=1;j<=n;j++)19{20scanf("%d%d%d",&x,&y,&w);//能到达，互相标记为权值w 21a[x][y]=w;22a[y][x]=w;23}24 }25 /*有向图，无权值*/26 int a[MAXN][MAXN];//邻接矩阵 27 int x,y;//两座城市 28 for(int i=1;i<=n;i++)29 {30for(int j=1;j<=n;j++)31{32scanf("%d%d",&x,&y);//能到达，仅仅是x到y标记为1 33a[x][y]=1;34}35 }36 /*有向图，有权值*/37 int a[MAXN][MAXN];//邻接矩阵 38 int x,y,w;//两座城市，路径长度 39 for(int i=1;i<=n;i++)40 {41for(int j=1;j<=n;j++)42{43scanf("%d%d%d",&x,&y,&w);//能到达，仅仅是x到y标记为权值w 44a[x][y]=w;45}46 }
邻接矩阵很方便，但是在n过大或者为稀疏图时，就会很损耗时空，不建议使用！
2.邻接表：
邻接表是一个二维容器，第一维描述某个点，第二维描述这个点所对应的边集们。
邻接表由表头point，链点构成，如下图是一个简单无向图构成的邻接表：

文章插图
我们可以用指针来创建链表，当然，这是很复杂也很麻烦的事情，下面来介绍一种用数组模拟链表的方法：
1 //有向图邻接表存储2 const int N=1005; 3 const int M=10050; 4 int point[N]={0};//i节点所对应链表起始位置（表头）5 int to[M]={0}; 6 int next[M]={0};//i节点下一个所指的节点7 int cc=0;//计数器（表示第几条边）8 void AddEdge(int x,int y)//节点x到y 9 {10cc++;11to[cc]=y;12next[cc]=point[x];13point[x]=cc;14 }15 void find(int x)16 {17int now=point[x];18while(now)19{20printf("%d\n",to[now]);21now=next[now];22}23 }24 int main()25 {2627 }
具体的过程我也不是很懂怎么描述，反正如果要加强记忆的话可以用我所给的例子模拟一下point[],to[],next[]，然后再调用函数find(x)来输出x这个节点能到的点，大概就能YY到数组是怎么存储邻接表的了。
还是不理解的话，推一个blog，这里面说的和我这里给出的思路很相似：
二、树的遍历：
1.BFS：运用队列，一开始队列中有一个点，将一个点出队，将它的子结点全都入队。
算法会在遍历完一棵树中每一层的每个结点之后，才会转到下一层继续，在这一基础上，队列将会对算法起到很大的帮助：

文章插图
1 //广度优先搜索 2 void BreadthFirstSearch(BitNode *root) 3 { 4queue nodeQueue; 5nodeQueue.push(root);//将根节点压入队列6while (!nodeQueue.empty())//队列不为空，继续压入队列7{ 8BitNode *node = nodeQueue.front(); 9nodeQueue.pop();//弹出根节点 10if (node->left)//左儿子不为空 11{12nodeQueue.push(node->left);//压入队列 13}14if (node->right)//右儿子不为空 15{16nodeQueue.push(node->right);//压入队列 17}18}19 }
2.DFS：运用栈，递归到一个点时，依次递归它的子结点。
还可以利用堆栈的先进后出的特点，现将右子树压栈，再将左子树压栈，这样左子树就位于栈顶，可以保证结点的左子树先与右子树被遍历：