数据结构-图 All In One

在计算机科学中，图（Graph）是一种抽象数据类型，用于实现数学中图论的无向图和有向图的概念。

图的数据结构包含一个有限（可能是可变的）的集合作为节点集合，以及一个无序对（对应无向图）或有序对（对应有向图）的集合作为边（有向图中也称作弧）的集合。
节点可以是图结构的一部分，也可以是用整数下标或引用表示的外部实体。

图的数据结构还可能包含和每条边相关联的数值（edge value），例如一个标号或一个数值（即权重，weight；表示花费、容量、长度等）。

图的常见数据结构

邻接表:
节点存储为记录或对象，且为每个节点创建一个列表。
这些列表可以按节点存储其余的信息；例如，若每条边也是一个对象，则将边存储到边起点的列表上，并将边的终点存储在边这个的对象本身。

邻接矩阵:
一个二维矩阵，其中行与列分别表示边的起点和终点。
顶点上的值存储在外部。矩阵中可以存储边的值。

关联矩阵:
一个二维矩阵，行表示顶点，列表示边。
矩阵中的数值用于标识顶点和边的关系（是起点、是终点、不在这条边上等）。

非线性数据结构

图解算法数据结构 All In One

https://www.cnblogs.com/xgqfrms/p/16366896.html

refs

https://zh.wikipedia.org/wiki/图_(数据结构)

©xgqfrms 2012-2020

www.cnblogs.com/xgqfrms 发布文章使用：只允许注册用户才可以访问！

原创文章，版权所有©️xgqfrms, 禁止转载

原创文章，作者：，如若转载，请注明出处：https://blog.ytso.com/269291.html