图论
zhx
图
• 图的定义：
• 图G是一个有序二元组(V,E)，其中V称为点集(Vertices Set)，E称为
边集(Edges set。
• 有向图、无向图：如果给图的每条边规定一个方向，那么得到的
图称为有向图。在有向图中，与一个节点相关联的边有出边和入
边之分。相反，边没有方向的图称为无向图。
图的概念
• 度（Degree）：一个顶点的度是指与该顶点相关联的边的条数，顶点v的度
记作d(v)。
• 入度（In-degree）和出度（Out-degree）：对于有向图来说，一个顶点的
度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中，以其为
终点的边数；出度则是相对的概念，指以该顶点为起点的边数。
• 自环（Loop）：若一条边的两个顶点为同一顶点，则此边称作自环。
• 路径（Path）
特殊的图
• 没有环的无向图：树
• 有向图的树：外向树、内向树
• 树的扩展：
• 章鱼图
• 仙人掌图：边仙人掌、点仙人掌
• DAG(Directed Acyclic Graph)：有向无环图
• 二分图
图的存储方法
• 邻接矩阵边表
评论0