20162304 2017-2018-1 《程序设计与数据结构》第十周学习总结

松鼠的窝 2017-11-12

20162304 2017-2018-1 《程序设计与数据结构》第十周学习总结

教材学习内容总结

  1. 有向图和无向图；

  2. 带权图的学习；
    20162304 2017-2018-1 《程序设计与数据结构》第十周学习总结

  3. 定义生成最小树；
    20162304 2017-2018-1 《程序设计与数据结构》第十周学习总结

  4. 常用的图算法（遍历，测试连通性，最小生成树）

    教材学习中的问题和解决过程

  • 问题1：最小生成树Prim算法的理解。
  • 一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。其中Prim算法我们书上已经给出，我又查了一下另外一个算法，想要知道得更多。
  • Kruskal算法流程
  • 具体流程：
  1. 将图G看做一个森林，每个顶点为一棵独立的树
  2. 将所有的边加入集合S，即一开始S = E
  3. 从S中拿出一条最短的边(u,v)，如果(u,v)不在同一棵树内，则连接u,v合并这两棵树，同时将(u,v)加入生成树的边集E'
  4. 重复3.直到所有点属于同一棵树，边集E'就是一棵最小生成树

代码托管

20162304 2017-2018-1 《程序设计与数据结构》第十周学习总结

点评过的同学博客和代码

  • 本周结对学习情况
    • 20162318
    • 结对照片
    • 结对学习内容

      • 图的学习

        上周考试错题总结

  • 上周无考试

    其他（感悟、思考等，可选）

    图的这块个人觉得有点难搞，希望可以通过进一步的学习加深理解吧。

学习进度条

代码行数（新增/累积）博客量（新增/累积）学习时间（新增/累积）重要成长
目标5000行30篇400小时
第一周0/01/110/10
第二周0/01/210/20
第三周163/1631/312/32
第四周207/3701/311/43
第五周931/13011/412/55
第六周391/16922/615/70
第七周760/24522/813/83
第八周1178/36302/813/83
第九周1199/48291/911/94
第十周727/55562/1113/94

  • 计划学习时间:15小时

  • 实际学习时间:13小时

参考资料

  • 《Java程序设计与数据结构教程（第二版）》

  • 《Java程序设计与数据结构教程（第二版）》学习指导

松鼠的窝

松鼠的窝

相关推荐

图的最小生成树，Kruskal算法

最小生成树 kruskal 算法，适用于边稀疏的图，　　先按照边进行排序。　　选出小的，判断边的两个顶点是否是同一连通分量。如果是则继续取出下一个边。　　需要注意的是一开始需要一个辅助数组来记录连通分量，初始化所有顶点自己是一个连通分量。if contin

lixiaotao / 0评论 2020-06-06

克鲁斯卡尔算法（Kruskal算法）（最小生成树算法）-贪心

克鲁斯卡尔算法：Kruskal算法是一种用来查找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪心算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图

从零开始 / 0评论 2020-05-31

数据结构（构造连通网的最小生成树）

int min , i , j , k;int lowcost[MAXVEX];//连接到下标对应顶点的边的最小权。//既然说是目前为止，是因为以后连接到其他顶点，还会添加可选择的边；在这些新加的边中可能会刷新连接它的边的权最小记录。//只有所属不同树时才

niushao / 0评论 2020-05-10

Prim计算最小生成树权值 C语言

现在，你被委托在一个广阔区域里面为某些确定的结点设计连接网络。对于每条可能使用的线路，你能得到铺设该线路所需要的线缆长度。需要注意的是，在两个给定的结点之间可能存在许多路径。每个测试的第一个包含2个整数：第一个整数P给定区域内结点的数目，第二个整数R给出了

sillion / 0评论 2020-05-08

最小生成树算法

修路问题本质就是最小生成树问题，先介绍一下最小生成树，简称MST。1）给定一个带权的无向连通图，如何选择一颗生成树，使树上所有边上权的总和为最小，这叫最小生成树。作为一名电力建设者，小明正在帮助一带一路上的国家通电。　　在上式中 sqrt 表示取括号内的平

Oudasheng / 0评论 2020-04-20

prim算法和kruskal算法--解最小生成树问题

1）以某一个点开始，寻找当前该点可以访问的所有的边；2）在已经寻找的边中发现最小边，这个边必须有一个点还没有访问过，将还没有访问的点加入我们的集合，记录添加的边；3）寻找当前集合可以访问的所有边，重复2的过程，直到没有新的点可以加入；4）此时由所有边构成的

从零开始 / 0评论 2020-03-03

Kruskal算法

给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为

wulaxiaohei / 0评论 2020-01-28

Prim算法

形似dijsktra算法， 但是不同于dijsktra算法，prim算法是找到当前集合最近的点， 而dij算法是找距离当前起点最近的点。给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。求最小生成树的树边权重之和，如果最小生成树不存在则

路漫 / 0评论 2020-01-28

最小生成树的两种方法（Kruskal算法和Prim算法）

一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。

ustbfym / 0评论 2020-01-04

《算法导论（原书第3版）》第23章部分题目解答

对于任意一个被e横跨的割，我们知道，它必然会被另一个与e在同一个环上的边横跨。而“e为连通图\的某条环路上权重最大的边”，如果e是唯一最大的，那么所以任意时刻e不会成为一个安全边，所以图G中必然存在一棵不包含边e的最小生成树；如果在环上存在与e权重相同的边

yuanran0 / 0评论 2020-01-01

Prim算法求最小生成树

1，初始化U={u0},E为空集；　　//E是最小生成树的边集合，U是其顶点集合，选定构造最小生成树的出发点u0；2，重复以下步骤直到U=V；vector<GraphNode<T>>graphNodeArray;

风吹夏天 / 0评论 2019-12-17

查找最小生成树：克鲁斯克尔算法（Kruskal）算法

　　Kruskal算法是一种用来查找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。和Boruvka算法不同的地方是，Kruskal 算法在图中存在相同权值的边时也有效。最小生成树

风吹夏天 / 0评论 2019-12-01

最小生成树之Kruskal算法

对于一个图来说，我们可以选择不同的边而产生不同的树，由于边的选择不一样，每一条边的权值不一样，那我们最后生成出来的树的权值也就不一样，Kruskal算法和prim算法就是来找怎样选择边才可以使产生的树的权值最小。这个时候我们可以使用并查集来判断这个点是否已

yishujixiaoxiao / 0评论 2019-11-03

[图] 最小生成树-Prime算法和Kruskal算法

该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现；并在1957年由美国计算机科学家罗伯特·普里姆独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。

YUAN / 0评论 2019-06-26

解构BERT，揭示其在NLP任务中的最新性能

Transformer体系结构模型，特别是BERT，通过对一个在大型语料库上以非监督方式预先训练的模型进行微调，已经证明在许多NLP任务中非常有效。BERT模型将一系列单词作为输入，并生成一系列跨层的词嵌入向量。(1篇Finding Syntax with

Winifred / 0评论 2019-06-14

MATLAB实现最小生成树（Prim与Kruskal算法）

function [result]=prim(a);a(a==0)=inf;result=[];p=1;tb=2:length(a);temp=a(p,tb);temp=temp(:);d=min(temp);[jb,kb]=find(a(p,tb)==d

standfly / 0评论 2018-08-20

最小生成树prime算法、kruskal算法 最短路径算法floyd、dijkstra

带权图分为有向和无向，无向图的最短路径又叫做最小生成树，有prime算法和kruskal算法；有向图的最短路径算法有dijkstra算法和floyd算法。生成树各边的权 值总和称为生成素的权。最短路径问题旨在寻找图中两节点之间的最短路径，常用的算法有：fl

zonglinzonglin / 0评论 2018-08-02

NetworkX之Prim算法(实例讲解)

Prim算法与Dijkstra的最短路径算法类似，它采用贪心策略。算法开始先把图中权值最小的边添加到树T中，然后不断把权值最小的边E。当没有符合条件的E时算法结束，此时T就是G的一个最小生成树。NetworkX是一款Python的软件包，用于创造、操作复杂

yancey木易的blog / 0评论 2017-12-22

用C语言实现Prim算法及测试用例

qizongshuai / 0评论 2012-10-23

python最小生成树kruskal与prim算法详解

kruskal算法基本思路：先对边按权重从小到大排序，先选取权重最小的一条边，如果该边的两个节点均为不同的分量，则加入到最小生成树，否则计算下一条边，直到遍历完所有的边。直到candidate_node中没有备选节点。if self.maps[i][j]

Python探路者 / 0评论 2019-01-17

POJ-2421-Constructing Roads（最小生成树 普利姆）

Time Limit: 2000MSMemory Limit: 65536KTotal Submissions: 26694Accepted: 11720Description. There are N villages, which are number

你好C / 0评论 2018-05-05

基本模型之图论篇

最短路径问题（给定连接若干城市的公路网，寻找从指定城市到各城市去的最短路线。每一步只考虑一个数据，他的选取应该满足局部优化的条件。该算法常用于路由算法或者作为其他图算法的一个子模块。

BitTigerio / 0评论 2018-05-04

[板子]最小生成树

我们所写的最小生成树主要有两种，分别是Prime和Kluskal。

算法少女 / 0评论 2018-02-16

浅入浅出数据结构（25）——最小生成树问题

而最短路径问题可以说是这样的一个问题：路已经修好了，该怎么从这儿走到那儿？但是在和图有关的问题中，还有另一种有趣的问题：修路的成本已经知道了，该怎么修路才能尽可能节约成本，同时将这些地方都连起来？

松鼠的窝 / 0评论 2018-02-10

学习笔记：最小生成树算法

①初始化新图仅包含原图中的任意一个顶点，不包含任何边。②从原图中选择一条权值最小的边，该边满足有且仅有一个顶点在新图中。③重复直至所有顶点都在新图中，新图即最小生成树。②从小到大遍历原图中所有边，若边中的两个顶点在新图中不存在连通路径，则将其加入新图。

面向工资编程 / 0评论 2018-01-24

应用运筹学基础：组合优化 (6) - 近似算法选讲 (4)

平面上的斯坦纳树平面上的斯坦纳树指的是这样的问题：平面上有 $n$ 个点，要用总长尽量少的线段把它们连通起来。要注意，线段不一定要在给定的 $n$ 个点相交，完全可以在平面上的其它点相交。最优解中，线段在平面上除了给定点外的交点称为斯坦纳点。可以从上图看出

深圳湾 / 0评论 2018-01-09

图解Prim&Kruskal算法

假设以下情景，有一块木板，板上钉上了一些钉子，这些钉子可以由一些细绳连接起来。假设每个钉子可以通过一根或者多根细绳连接起来，那么一定存在这样的情况，即用最少的细绳把所有钉子连接起来。集合T中的边能够形成一颗树，这是因为每个节点都能向上找到它的一个父节点。P

松鼠的窝 / 0评论 2017-12-18