Python数据结构与算法笔记(5)

problem-solving-with-algorithms-and-data-structure-using-python 中文版 7 图和图的算法

顶点 边 权重 路径 循环 

没有循环的图形称为非循环图

没有循环的有向图称为有向无环图或DAG。

图抽象数据类型如下:

  • graph()创建一个新的空图
  • addVerter(vert)向图中添加一个顶点实例
  • addEdge(fromVert,toVert)向链接两个顶点的图加一个新的有向边
  • addEdge(fromVert,toVert,weight)向连接两个顶点的图添加一个新的加权的有向边
  • getVertex(vertKey)在图中找到名为vertKey的顶点
  • getVertices()返回图中所有顶点的列表
  • in返回True 如果vertex in graph,否则返回False

实现图的两种方式:邻接矩阵和邻接表

邻接矩阵:

邻接矩阵优点是简单,对于小图,很容易看到哪些节点连接到其他节点。但是大多数单元格是空的,即稀疏。

邻接表:是实现稀疏连接图更空间高效的方法。在邻接表实现中,我们保存Graph对象中所有顶点的主列表,然后图中每个顶点对象维护连接到它的其它顶点的列表。

邻接表实现的优点是允许我们紧凑地表示稀疏图。邻接表还允许我们容易找到直接连接到特定顶点的所有链接。

广度优先搜索BFS

深度优先搜索DFS

拓扑排序是深度优先搜索的简单但有用的改造。

拓扑排序采用有向无环图,并且产生所有其顶点的线性排序,使得如果图 G 包含边(v,w),则顶点 v 在排序中位于顶点 w 之前。定向非循环图在许多应用中使用以指示事件的优先级。

可以帮助找到图中高度互连的顶点的集群的一种图算法被称为强连通分量算法(SCC)。我们正式定义图 G 的强连通分量 C 作为顶点 C⊂V 的最大子集,使得对于每对顶点 v,w∈C,我们具有从 v 到 w 的路径和从 w 到 v 的路径。

一旦确定了强连通分量,我们就可以通过将一个强连通分量中的所有顶点组合成一个较大的顶点来显示该图的简化视图。

最短路径的算法:“Dijkstra算法”

Prim生成树算法

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Small Code

MATLAB绘制平行六面体

如果给出一个平行六面体(甚至其他多面体)的各个顶点坐标,如何画出这个平行六面体。 在网上找了找方法,可以参考这篇博客 matlab中patch函数详解。然后我具...

30880
来自专栏猿人谷

斐波那契额数列及青蛙跳台阶问题

题目:写一个函数,输入n,求斐波那契(Fibonacci)数列的第n项。  斐波那契(Fibonacci)数列定义如下: ? 效率很低的解法:...

25780
来自专栏数据结构与算法

tarjan算法详解

tarjan算法讲解。 tarjan算法,一个关于 图的联通性的神奇算法。基于DFS算法,深度优先搜索一张有向图。!注意!是有向图。根据树,堆栈,打标记等种种神...

49740
来自专栏机器学习算法工程师

Tarjan算法

tarjan算法 一个关于有向图的联通性的神奇算法。 基于DFS(迪法师)算法,深度优先搜索一张有向图。 名词的储备,有备无患 强连通(strongly con...

410100
来自专栏数据结构与算法

4768 跳石头

4768 跳石头 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 一年一度的“...

284100
来自专栏温安适的blog

最小生产树Prim和Kruskal

487120
来自专栏用户画像

5.2 图的存储及基本操作

图的存储必须要完整、准确地反映顶点集和边集的信息。根据不同图的结构和算法,可以用不同的存储方式,但不同的存储方式将对程序的效率产生很大的影响,因此,所选的存储结...

10730
来自专栏Hadoop数据仓库

HAWQ + MADlib 玩转数据挖掘之(十)——图算法之单源最短路径

一、图算法简介 1. 定义         在计算中,常将运算方程或实验结果绘制成由若干有标尺的线条所组成的图,称为“算图”。计算时根据已知条件,从有关线段上一...

25160
来自专栏云霄雨霁

加权有向图----单点最短路径问题(Dijkstra算法)

27500
来自专栏编程理解

数据结构(十二):最短路径(Dijkstra算法)

Dijkstra 算法使用贪心策略计算从起点到指定顶点的最短路径,通过不断选择距离起点最近的顶点,来逐渐扩大最短路径权值,直到覆盖图中所有顶点。

37820

扫码关注云+社区

领取腾讯云代金券