知识卡片

普通读书笔记卡 · 5654.d.1.f.4 · 生成模型:未记录

图用顶点和边表达关系

理解等级:中级

图 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)。