学习笔记26-图的表示方法

图

图是一种数据结构，包括一组顶点和一组边。有几个概念需要了解：
1.无向图——有向图：区别在于边有没有方向。比如《v,w》是有向的，表示从v指向w的边，而(v,w)是无向的，可以从v指向w，也可以从w指向v。
2.连通图：如果从v到w存在一条无向的边(v,w)，则称v和w是连通的。如果图中任意两个顶点均是连通的，则称该图为连通图。
图的构建方法有好几种，如邻接矩阵法，邻接表法，十字链表法，邻接多重表等。

邻接矩阵

图的邻接矩阵存储方式就是用一个二维数组来表示。
比如下图表示一个有四个顶点，四条边的无向图：

邻接表

对于边数相对顶点较少的图，邻接矩阵会造成存储空间的极大浪费。因此我们考虑另外一种存储结构方式：邻接表（Adjacency List），即数组与链表相结合的存储方法。
邻接表的处理方法是这样的。
1、图中顶点用一个一维数组存储，另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。也就是一个结构体数组，结构体包括数据和指针，可能还包括该边的权重。
2、图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图称为顶点vi作为弧尾的出边表。
如下图：