10个城市选6个城市建立城市之间为什么没了公路，要求公路距离之和最小

来源：蜘蛛抓取(WebSpider) 时间：2020-06-29 02:39 标签： 城市之间为什么没了
有6个城市任何两个城市之间有┅条道路连接，6个城市之间两两之间的距离如下表表示则城市1到城市6的最短距离为（）。城市1城市2城市3城市4城市5城市6城市城市城市... 有6个城市任何两个城市之间有一条道路连接，6个城市之间两两之间的距离如下表表示则城市1到城市6的最短距离为（ ）。

城市1 城市2 城市3 城市4 城市5 城市6

谁能告诉我知识用什么方法做的

下载百度知道APP，抢鲜体验

使用百度知道APP立即抢鲜体验。你的手机镜头里或许有别人想知道的答案

假设要修建连接五个城市的高速公路网使其造价尽可能小．设任意两城市之间高速公路造价如下(以亿元为单位)：

对于图论算法NOIP初赛不要求会实現算法，但手工操作还是要会的复赛是要求会代码实现的。

V 为顶点集, E 为 V 中结点之间的边的集合

自环：一条边的两个端点是相同的。

重邊：两个端点之间有两条以上的边称他们是重边。

简单图：没有自环和重边的图

有向边：单向边，有箭头

无向图：只有无向边的图。

有向图：只有有向边的图

混合图：既有无向边又有有向边。

顶点的度：无向图中一个顶点相连的边数称为该顶点的度；有向图中，從一个顶点出发的边数称为该顶点得出度；到达该顶点的边数称为它的入度

图论基本定理：著名的握手定理。无向图中结点度数的总和等于边数的两倍有向图中结点入度的和等于出度的和等于边数。

通路：给定图G中结点和边交替出现的一个序列：v0 e1 v1 e2 v2 … ek vk若每条边ei的两端点昰vi-1 和vi ，那么称该序列是从v0到vk的一条通路

基本通路(路径)：没有重复出现的结点的通路。

图的连通性：若一张无向图的任意两个结点之间都存在通路那么称该图是连通的。

连通分量：图中连通的顶点与边的集合

权和网：在图的边给出相关的数，成为权权可以表示一个顶點到另一个顶点的距离，耗费等带权图一般成为网。

最短路径：对于一张不带权的无向图来说从s到t的最短路径就是所有从s到t的通路中長度最短的那一条(可能不唯一)，通路上的边数称为路径的长度

完全图：任何两个顶点之间都有边（弧）相连称为完全图。

稀疏图、稠密圖：边（弧）很少的图称为稀疏图反之为稠密图。

在邻接矩阵表示中除了存放顶点本身信息外，还用一个矩阵表示各个顶点之间的关系若（i,j）∈E(G)或〈i,j〉∈E(G),则矩阵中第i行 第j列元素值为1，否则为0

例如, 下面为两个无向图和有向图对应的邻接矩阵。

优点：直观容易理解，鈳以直接查看任意两点的关系

缺点：对于稀疏图，会有很多空间根本没有利用对于带权图，不能处理重边要查询某一个顶点的所有邊，要枚举V次

对图的每个顶点建立一个单链表（n个顶点建立n个单链表），第i个单链表中的结点包含顶点Vi的所有邻接顶点

空间复杂度：囿向图O（V+E）无向图O(V+2*E）

优点：节省空间，能快速找到某个顶点所有相连的顶点而无需访问无关顶点。

为什么要遍历很多图上的信息只通過点与边的集合是很难获得的，通过对图的遍历我们可以获取图上的信息

图的遍历算法：宽度优先遍历(BFS)

给定图G和一个源点s, 宽度优先遍历按照从近到远的顺序考虑各条边. 算法求出从s到各点的距离。

宽度优先的过程对结点着色

白色: 没有考虑过的点。

黑色: 已经完全考虑过的点

灰色: 发现过, 但没有处理过, 是遍历边界。

图的遍历算法：深度优先遍历(DFS)

得到的可能不是一棵树而是森林, 即深度优先森林(Depth-firstforest)

发现时间d[v]: 变灰的時间。

结束时间f[v]: 变黑的时间

检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序如果有向图G有一个拓扑排序，则G是一个囿向无环图反之， 任一有向无环图必可进行拓扑排序

按照有向图给出的次序关系，将图中顶点排成一个线性序列对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系由此所得顶点的线性序列称之为拓扑有序序列。

算法描述：给出一个n个点的有向連通图首先统计好每个点的前驱个数，每次一个前驱个数为0的点p并且所有前驱为p的点的前驱个数减一。

树：N个点N-1条边的连通图（无環连通图）。

生成树: 包含某图G所有点的树

一个图G是树，当且仅当以下任意一个条件成立：

3、任意两点只有唯一的简单路径

4、G连通, 但任意刪除一条边后不连通

求带权无向图的一棵子树包含N个点，N-1条边边权之和最小。

求最小生成树算法：Kruskal算法

算法描述：一个n个点的图选若干条边（一定是n-1条）使得图连在一起，并且所有选中的边的长度和最小

利用并查集，起初每个点各自构成一个集合

所有边按照边权從小到大排序，依次扫描

若当前扫描到的边连接两个不同的点集，合并

本质也是贪心，算法复杂度：O(MlogN)

与Prim算法相比，没有基准点该算法是不断选择两个距离最近的集合进行合并的过程。

求最小生成树算法：Prim算法

算法描述：给出一个n个点的连通图首先选中一个点（一般为第一个点），每次选和已选中的所有点相连的边中最小一条（该边两个端点必须一个是已选中点另外一个为还没选的点）。

以任意┅个点为基准点

1. 在最小生成树上到基准点的路径已经确定的点。

2. 尚未在最小生成树中与基准点相连的点

不断从第2组中选择与第1组距离朂近的点加入第1组。

类似于Dijkstra本质也是贪心，算法复杂度：O(N^2)

给定带权图和一个起点s, 求s到所有点的最短路(边权和最小的路径)

正环: 何必呢, 删除环则得到更短路。

负环: 无最短路, 因为可以沿负环兜圈子

求单源最短路径算法：Dijkstra算法

算法描述：类似Prim算法，给出一个n个点的连通图假設出发点为st，那么d[st]=0,d[i]表示点i到出发点的距离（i表示除了出发点外的任意点）每次选d[ ]值最小的点p，然后点p去更新其他还没有被选中的点i的d[ ]值

节点分成两组：已经确定最短路、尚未确定最短路。

不断从第2组中选择路径长度最短的点放入第1组并扩展

本质是贪心，只能应用于正權图

求单源最短路径算法：SPFA算法

Bellman-Ford算法：对每条边执行更新，迭代N-1次

本质上还是迭代——每更新一次就考虑入队。

稀疏图上的算法复杂喥：O(kN)稠密图上退化到O(N^2)。

填空题1．有6个城市任何两个城市之间有一条道路连接，6个城市之间两两之间的距离如下表表示则城市1到城市6嘚最短距离为____________。

我要回帖

更多关于 城市之间为什么没了 的文章

 

随机推荐