知识卡片
图用顶点和边表达关系
图 G=(V,E) 以顶点表示对象、以边表示关系;应用可使用有向或无向、加权或无权模型。建模前要明确自环、平行边和权重语义,因为这些约束会影响表示和算法。
148区分单源最短路径、所有顶点对最短路径以及最小生成树。最小生成树针对连通无向加权图,连接所有顶点且总边权最小;图不连通时相应结果是最小生成森林。最短路径树与最小生成树目标不同。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 图用顶点和边表达关系
- · 问题
原书出处 · 2 处
- · 查看原书依据
顶点),以及元素两两之间的关系(也就是边)。由于应用范围所限,本章我们仅仅讨论简单图,简单图并不会如(a)那样有一个顶点的一条边是自己指向自己,以及不会如(b)那样一对顶点之间存在多条边。
- · 查看原书依据
最小生成树(MST),最小生成树是一个无向有权图,是原图边的一个子集,但是,原图的顶点仍然是连通的,而边的权值总和最小。在本章稍后部分,“最小生成树算法”一节,我们将会描述如何高效地解决这个问题。 我们首先从如何探索图开始讨论。两个最常使用的搜索方法是深度优先搜索(DFS)和广度优先搜索(BFS)。
参考来源
- 位置:《算法技术手册》第6章《概述》(spine1561;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1524.html;u143-ch06-001)。
- 结论依据:143全文与03275家族、航线、网络示意实读。
- 原始内容:顶点),以及元素两两之间的关系(也就是边)。由于应用范围所限,本章我们仅仅讨论简单图,简单图并不会如(a)那样有一个顶点的一条边是自己指向自己,以及不会如(b)那样一对顶点之间存在多条边。
- 位置:《算法技术手册》第6章《问题》(spine1565;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1528.html;u148-ch06-001)。
- 结论依据:148区分单源最短路径、所有顶点对最短路径以及最小生成树。最小生成树针对连通无向加权图,连接所有顶点且总边权最小;图不连通时相应结果是最小生成森林。最短路径树与最小生成树目标不同。
- 原始内容:最小生成树(MST),最小生成树是一个无向有权图,是原图边的一个子集,但是,原图的顶点仍然是连通的,而边的权值总和最小。在本章稍后部分,“最小生成树算法”一节,我们将会描述如何高效地解决这个问题。 我们首先从如何探索图开始讨论。两个最常使用的搜索方法是深度优先搜索(DFS)和广度优先搜索(BFS)。