图 ​

​

图（graph）是由顶点（Vertex）集合和顶点之间的边（Edge）的集合组成

• 顶点(Vertex)：图中的节点，表示实体
• 边(Edge)：连接两个顶点的关系，表示实体之间的连接
• 路径(Path)：由边连接的顶点序列，表示顶点之间的连续关系
• 环(Cycle)：在有向图中，形成回路的路径称为环
• 连通图(Connected Graph)：在无向图中，如果任意两个顶点之间都存在路径，则称为连通图
• 子图(Subgraph)：由图中的一部分顶点和边组成的图称为子图
• 出度(Out-degree)：有向图中顶点的出边数目
• 入度(In-degree)：有向图中顶点的入边数目

方向 ​

边是否有方向 分为无向图、有向图

无向图 有向图

权重 ​

边是否有权重 分为带权图和不带权图

带权无向图

带权有向图

邻接矩阵 ​

邻接矩阵，空间复杂度V^2，访问时间复杂度O(1) 带权邻接矩阵

邻接表 ​

邻接表 带权邻接表

E << V^2 ​

• 边远小于 节点的平方，称为稀疏图
• 边接近于 节点的平方，称为稠密图

一般使用邻接表表示稀疏图，因为邻接矩阵空间复杂度为V^2