本文概述
- 1.顺序表示
- 链接表示
有两种方法可以将Graph存储到计算机的内存中。在本教程的这一部分中, 我们将详细讨论其中的每一个。
1.顺序表示 在顺序表示中, 我们使用邻接矩阵来存储由顶点和边表示的映射。在邻接矩阵中, 行和列由图形顶点表示。具有n个顶点的图的尺寸为n x n。
【图论（图Graph的表示方法）】如果在Vi和Vj之间存在边, 则无向图G的邻接矩阵表示中的条目Mij将为1。
下图显示了无向图及其邻接矩阵表示。
文章图片
在上图中, 我们可以看到顶点（A, B, C, D, E）之间的映射是通过使用图中也显示的邻接矩阵来表示的。
有向图和无向图存在不同的邻接矩阵。在有向图中, 仅当存在从Vi到Vj的边时, 条目Aij才为1。
下图显示了有向图及其邻接矩阵表示。
文章图片
加权有向图的表示形式有所不同。不是用1填充条目, 而是通过各个边的权重表示邻接矩阵的非零条目。
下图显示了加权有向图以及邻接矩阵表示。
文章图片
链接表示 在链接的表示中, 使用邻接表将图形存储到计算机的内存中。
考虑下图所示的无向图, 并检查邻接表的表示形式。
文章图片
为图中存在的每个节点维护一个邻接表, 该列表存储该节点值和指向各个节点的下一个相邻节点的指针。如果遍历所有相邻节点, 则将NULL存储在列表的最后一个节点的指针字段中。邻接表长度的总和等于无向图中存在的边数的两倍。
考虑下图所示的有向图, 并检查该图的邻接表表示形式。
文章图片
在有向图中, 所有邻接表的长度之和等于图中存在的边数。
对于加权有向图, 每个节点包含一个额外的字段, 称为节点的权重。下图显示了有向图的邻接表表示。
文章图片
