数据结构07-图

7.1概念性质和实现

7.1.1 定义

该图形可以被定义为一个有序对G=(V,E)，其中顶点集合为V、边集合为E；
该图形可分为有向图与无向图，在本讨论中使用<>表示有向边、()表示无向边；
对于一个有向元素< a, b >：我们称a为起始端、b为目标端；
在该图形中称为相邻的概念：b被称为与a相邻的对象，在无向图中这种相邻关系是相互的；
对于一个元素< a, b >而言，则被称为与该节点相关的关联于其两端的一条特定边上；
值得注意的是，在本讨论范围内我们排除了自环结构（self-loop edges）的存在；
此外，在当前上下文中假设任意一对不同节点之间至多只存在一条这样的特定连接路径。

7.1.2 图的一些概念和性质

完全图 ：任何两个顶点之间都有边；n个顶点的图边数：
有向图 : n*(n-1)
无向图 : n*(n-1)/2

度 :: 某个顶点连接的边的数量，在有向图中每个顶点都有出度和入度；而这些基本元素之间的关系则由下式体现：
总边数等于所有顶点的度之和的一半（适用于无向图与有