数据结构——图

图是对结点的前趋和后继个数不加限制的数据结构
较之线性表和树形结构,图是一种更为复杂的非线性数据结构
图中各数据元素之间的关系可以是任意的
描述的是"多对多"的关系
图 (Graph) 的概念
图的结构定义
图是由顶点集V和顶点间的关系集合E(边的集合)组成的一种数据结构,可以用二元组定义为:G=(V,E)
其中
V(G)是顶点的非空有限集
E(G)是边的有限集合,边是顶点的无序对或有序对
例如: G=(V,E)
V={1,2,3,4}
E={(1,2), (1,3),(1,4),(2,4),(3,4)}
1
2
3
4
图的基本术语
有向图
有向图G是由两个集合V(G)和E(G)组成的
其中
V(G)是顶点的非空有限集
E(G)是有向边(也称弧)的有限集合,弧是顶点的有序对,记为,v,w是顶点,v为弧尾,w为弧头
在图中,用箭头标明了边是有方向性的
例G1中
V(G1)={1,2,3,4,5,6}
E(G1)={, , , , , , }
2
4
5
1
3
6
G1