有向图和无向图及邻接矩阵和邻接表
1.有向图和无向图
图(Graph)是一种较线性表和树更为复杂的数据结构。在图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。
我们可以把图分为有向图和无向图。
我们可以用两组数据对图进行表示。一组是图的顶点，一组是图的边。
G1 = (V1, { A1 })
其中:
V1 = {v1, v2, v3, v4}
A1 = {<v1, v2>, <v1, v3>, <v3, v4>, <v4, v1>}
G2 = (V2, { E2 })
其中:
V2 = {v1, v2, v3, v4, v5}
E2 = {(v1, v2), (v1, v4), (v2, v3), (v2, v5), (v3, v4), (v3, v5)}
2.邻接矩阵
以二维数组表示有n个顶点的图时，需存放n个顶点信息和n2个弧信息的存储量。下图分别是G1和G2的邻接矩阵。
3.邻接表
邻接表(Adjacency List)是图的一种链式存储结构。在邻接表中,对图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点vi的边(对有向图是以顶点vi为尾的弧)。如下图所示: