图
graph的定义:
- 顶点（vertex）：图中的元素
- 边（edge）：图中的顶点与其他任意顶点建立连接的关系，每条边都是顶点对，表示为 \((v,w)\)
- 图（graph）： \(G=(V, E)\) ，图由顶点的集合 \(V\) 和边的结合 \(E\) 组成
- 有向图（digraph）：如果顶点对是有序的，则图是有方向的，否则为无向图
- 权（weight）/值（cost）：边除了顶点对外，还可以有权重属性
- 路径（path）：一条路径是一个顶点序列，路径的长是该路径上的边数
- 环（loop）： 顶点含有一条连通自己的边，例如 \((v,v)\) ，那么路径 \((v,v)\) 是一个环
- 圈（cycle）： 有向图中圈是满足起始点等于结束点且边长至少为1的路径，无向图中则要求边长至少为2
- DAG：有向无圈图
- 稀疏图/稠密图：当边数量很少时是稀疏图，反之则为稠密图，这两者之间没有明确的区分
图的表示
邻接矩阵
适合稠密图
邻接表
适合稀疏图