763
个编辑
更改
→图论数据结构
== 图论数据结构 ==
== 图论数据结构 ==
在计算机系统中存储图形有不同的方法。所使用的数据结构取决于图的结构和操作图的算法。理论上可以区分列表结构和矩阵结构，但在具体应用中，最佳结构往往是两者的结合。列表结构往往应用于'''稀疏图 sparse graphs'''，因为他们对内存需求较低。而矩阵结构对某些应用访问速度较快，但可能会消耗大量内存。高效稀疏矩阵结构在现代并行计算机体系结构上的实现是当前研究的一个课题。<ref>{{Cite book | last1 = Kepner | first1 = Jeremy| last2 = Gilbert | first2 = John| title = Graph Algorithms in the Language of Linear Algebra| date = 2011| pages = 1171458|isbn=978-0-898719-90-1| publisher = SIAM | url = https://my.siam.org/Store/Product/viewproduct/?ProductId=106663}}</ref>
在计算机系统中存储图形有不同的方法。所使用的数据结构取决于图的结构和操作图的算法。理论上可以区分列表结构和矩阵结构，但在具体应用中，最佳结构往往是两者的结合。列表结构往往应用于'''稀疏图 sparse graphs'''，因为他们对内存需求较低。而矩阵结构对某些应用访问速度较快，但可能会消耗大量内存。高效稀疏矩阵结构在现代并行计算机体系结构上的实现是当前研究的一个课题。<ref>{{Cite book | last1 = Kepner | first1 = Jeremy| last2 = Gilbert | first2 = John| title = Graph Algorithms in the Language of Linear Algebra| date = 2011| pages = 1171458|isbn=978-0-898719-90-1| publisher = SIAM | url = https://my.siam.org/Store/Product/viewproduct/?ProductId=106663}}</ref>
列表结构包括'''关联表 incidence list'''——顶点对数组，及'''邻接表 adjacency list'''，它分别列出每个顶点的邻接点: 就像关联表一样，每个顶点都有一个邻接顶点的列表。
列表结构包括'''关联表 incidence list'''——顶点对数组，及'''邻接表 adjacency list'''，它分别列出每个顶点的邻接点: 就像关联表一样，每个顶点都有一个邻接顶点的列表。
矩阵结构包括'''关联矩阵 incidence matrix'''——一个由0和1组成的矩阵，其中行代表顶点，列代表边; 及'''邻接矩阵 adjacency matrix'''，其中的行和列都按顶点进行索引。在这两种情况下，1表示两个对象相邻，0表示两个对象不相邻。'''度矩阵 degree matrix'''表示顶点的度数。'''拉普拉斯矩阵 Laplacian Matrix'''是邻接矩阵的一种改进形式，它包含了关于顶点度的信息，并且在一些计算中很有用，例如基尔霍夫 Kirchhoff 关于图的'''生成树 spanning tree'''的定理。'''距离矩阵 distance matrix'''（如邻接矩阵）的行和列都由顶点索引，但每个单元格内不是0或1而是两个顶点之间'''最短路径 shortest path'''的长度。
矩阵结构包括'''关联矩阵 incidence matrix'''——一个由0和1组成的矩阵，其中行代表顶点，列代表边; 及'''邻接矩阵 adjacency matrix'''，其中的行和列都按顶点进行索引。在这两种情况下，1表示两个对象相邻，0表示两个对象不相邻。'''度矩阵 degree matrix'''表示顶点的度数。'''拉普拉斯矩阵 Laplacian Matrix'''是邻接矩阵的一种改进形式，它包含了关于顶点度的信息，并且在一些计算中很有用，例如基尔霍夫 Kirchhoff 关于图的'''生成树 spanning tree'''的定理。'''距离矩阵 distance matrix'''（如邻接矩阵）的行和列都由顶点索引，但每个单元格内不是0或1而是两个顶点之间'''最短路径 shortest path'''的长度。