有向图
介绍
有向图(Directed Graph,也称为Digraph)是图论中的一种基本图类型,其中每条边都有明确的方向。在有向图中,边由一个顶点(称为起点或源点)指向另一个顶点(称为终点或目标点)。这种有方向性的连接让有向图特别适合表示具有单向关系的各种现实问题。
有向图中的关键概念:
- 顶点(Vertex):图中的节点,通常用数字或字母标识。
- 有向边(Directed Edge):从一个顶点指向另一个顶点的带方向连接,通常表示为有序对(u,v),表示从顶点u到顶点v的边。
- 入度(In-degree):指向某个顶点的边的数量。例如,如果有3条边指向顶点v,则顶点v的入度为3。
- 出度(Out-degree):从某个顶点出发的边的数量。例如,如果从顶点u出发有2条边,则顶点u的出度为2。
- 路径(Path):从一个顶点到另一个顶点经过的边的序列。
- 环(Cycle):一条起点和终点相同的路径,表示可以从某顶点出发最终回到同一顶点。
核心特性
- 方向性:每条边都有明确的方向,从一个顶点指向另一个顶点
- 入度和出度:顶点的连接关系分为指入和指出两种
- 可能存在环:有向图中可能存在从一个顶点出发最终回到该顶点的路径
- 可达性:从一个顶点到另一个顶点可能存在路径,也可能不存在
- 强连通性:在强连通的有向图中,任意两点之间都存在相互可达的路径
- 拓扑排序:对于无环有向图(DAG),可以将所有顶点排列成一个线性序列,使得所有边都从序列的前面指向后面
...