0.图

图

• 定义：
  • 图（graph）是一种非线性数据结构，由顶点（vertex）和边（edge）组成。
  • 我们可以将图G抽象地表示为一组顶点V和一组边E的集合
    • G = { V , E}
    • V = {1,2,3,4,5}
    • E = {(1,2),(2,3),(2,4),(3,5)}
  • 图代表的是网络关系，自由度更高

图的分类：

• 根据边是否具有方向分类：
  • 有向图
  • 无向图
  • 
• 根据顶点是否连通：
  • 连通图
  • 非连通图
  • 
• 根据边是否有权重：
  • 有权图
  • 无权图
  • 

图相关概念：

• 邻接（adjacency）：当两顶点之间存在边相连时，称这两顶点“邻接”。在图 9-4 中，顶点 1 的邻接顶点为顶点 2、3、5。
• 路径（path）：从顶点 A 到顶点 B 经过的边构成的序列被称为从 A 到 B 的“路径”。在图 9-4 中，边序列 1-5-2-4 是顶点 1 到顶点 4 的一条路径。
• 度（degree）：一个顶点拥有的边数。对于有向图，入度（in-degree）表示有多少条边指向该顶点，出度（out-degree）表示有多少条边从该顶点指出。