/ 写在前面的话 /

苏世机试小课堂，考研机试不再慌！

公主号:苏世学社考研 苏世计算机考研

图是计算机科学中常用的一类数据结构，有关图的算法也是计算机科学中重要的图和图算法。有许多有趣的计算问题都是用图来定义的。在本文中，要介绍一些更为重要的图和图算法。

1.并查集

  1.1 概念

并查集是一种树形的数据结构，用于处理一些不交集的合并及查询问题。联合-查找算法定义了两个用于此数据结构的操作：

Find：确定元素属于哪一个集合。它可以被用来确定两个元素是否属于同一个子集。

Union：将两个子集合并成同一个集合。

并查集主要运用在合并元素以及查询两个元素是否在同一集合的问题。

  1.2  典型例题

题目描述

今天是小苏的生日，小苏邀请了很多朋友，现在该吃晚饭了,小苏想知道他至少需要多少张桌子。你必须注意到并不是所有的朋友都认识对方，而且所有的朋友都不想和陌生人待在一起。这个问题的一个重要规则是如果我告诉你A认识B, B认识C，这意味着A, B, C互相认识，所以它们可以在一个表中。例如:如果我告诉你A认识B, B认识C, D认识E，那么A, B, C可以在一个表中，D, E必须在另一个表中，小苏至少需要两张表。

输入描述

输入以一个整数T(1<=T<=25)开始，它表示测试用例的数量。然后是T组测试用例，每个测试用例都以两个整数N和M开始(1<=N,M<=1000)。N表示朋友的数量，朋友的数量从1到N进行标记，然后是M行。每一行由两个整数A和B(A!=B)组成，这意味着朋友A和朋友B互相认识。两种情况之间会有一条空行。

输出描述

对于每个测试用例，只输出小苏至少需要多少个表，不要打印任何空格。

思路

将认识的人归到一个集合里，然后计算集合的数量，用并查集即可。

代码实现

2.最小生成树

  2.1 概念

给定一张边带权的无向图G=(V,E)，其中V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。由V中的全部n个顶点和E中的n-1条边构成的无向连通图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为无向图G的最小生成树。

简而言之：

一棵树：无回路，V个顶点V-1条边。

生成树：包含全部顶点，V-1条边都在图里

边的权重最小。

  2.2算法介绍

（1）prim算法

①步骤

1.用两个集合A{},B{}分别表示找到的点集合和未找到的点集。

2.以A中的点为起点a，在B中找一个点为终点b，这两个点构成的边(a,b)的权值是其余边中最小的，将b加入集合A。

3.重复上述步骤2’，直至B中的点集为空，A中的点集为满。

（2）图文表示

先将源点0加入集合A，然后遍历A中的点外接的所有边，找到最小的那条边

发现最小边对应的集合B里面的点是2，将结点2加入集合A中，然后继续找长度最小的边

发现集合B里的结点3离A最近，将它加入到集合A里，继续找

发现结点1到集合A的距离为13，将结点1加入A中，继续找

发现节点4到1的距离为13最短，此时发现所有顶点已经都在集合A里面了，满足题目条件，终止寻找

经典例题

题目描述

某佛大学要进行用电线路改造，现在校长要求设计师设计出一种布线方式，该布线方式需要满足以下条件：
1、把所有的楼都供上电。
2、所用电线花费最少。

输入

第一行是一个整数n表示有n组测试数据。(n<5) 
每组测试数据的第一行是两个整数v,e. v表示学校里楼的总个数(v<=500) 随后的e行里，每行有三个整数a,b,c表示a与b之间如果建铺设线路花费为c(c<=100)。（哪两栋楼间如果没有指明花费，则表示这两栋楼直接连通需要费用太大或者不可能连通） 随后的1行里，有v个整数,其中第i个数表示从第i号楼接线到外界供电设施所需要的费用。( 0<e<v*(v-1)/2 ) （楼的编号从1开始），由于安全问题，只能选择一个楼连接到外界供电设备。
数据保证至少存在一种方案满足要求。

输出

每组测试数据输出一个正整数,表示铺设满足校长要求的线路的最小花费。

样例输入

1

4 6

1 2 10

2 3 10

3 1 10

1 4 1

2 4 1

3 4 1

1 3 5 6

样例输出

4

示例代码

3.Kruskal算法

  3.1 思想和步骤

从prim算法我们可以知道，它是从“顶点”这个角度来思考的，然后采用“贪心思想”，一步一步扩大化，最后形成总体最优解。而Kruskal是站在“边”这个角度来考虑的，使用并查集，先初始化为孤立集合，再按权值大小排序，把权值小的边加入集合，直到点全部在集合中。

  3.2图文表示

初始化，选择结点0作为原点

找到最小的边权值为2，将它加入到集合中

接着找到最小的边权值为4将加入到集合中

同样权值为4的边因为两个结点都在集合里了，所以选择下一个最小边权值为6，加入到集合中

还有权值为6的边，继续加入集合中

边数已经是顶点数-1了，剩下的边连接的两个顶点都在集合中，所以不用加入了，流程结束。

代码实现

4.最短路径

  4.1概念

最短路径问题旨在寻找图中两结点的最短路径。算法具体形式包括：

（1）确定起点的最短路径问题-即已知起始结点，求最短路径的问题。

（2）确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

（3）确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。

（4）全局最短路径问题 - 求图中所有的最短路径。

Dijkstra算法

 

4.2概念

Dijkstra算法（迪杰斯特拉）是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。可以用堆优化。

 4.3实现步骤

①将所有的顶点分为两个部分，已知最短路径的顶点集合P和未知的顶点集合Q，初始时，P中只有一个源顶点1号。这里用book数组来标记顶点是否在P中，1表示在P中，0表示在Q中。

dis数组来记录最短路径，数组下标来表示顶点的下标。

设置源点1到到其他顶点的路径值，放置到dis中。

②在dis中找到源点s到其他顶点的最短路径u顶点，将其加入P集合，并考察以x顶点为起点的出边，然后对dis 进行更新。即：如果存在一条从u到v的边，那么可以拓展一条从s到u再到v的边，路径长度为dis[u]+edge[u] [v] ,如果这个值比目前的值dis[v]小，那么就进行更新。

③重复第2步，直到Q为空，即book都被标记，此时dis数组中就是源点到各个顶点的最短路径。

代码实现

Floyd算法

4.4概念

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。

 4.5核心思路

①从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

②对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。

把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i][j]=d，d表示该路的长度；否则G[i][j]=无穷大。定义一个矩阵D用来记录所插入点的信息，D[i][j]表示从Vi到Vj需要经过的点，初始化D[i][j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，G[i][j] = min( G[i][j], G[i][k]+G[k][j] )，如果G[i][j]的值变小，则D[i][j]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。

代码实现

苏世学社旗下品牌，专注于计算机考研

计算机考研一手资讯，原创高质量干货

深度的学习分享丨咨询前辈丨个性化指导