图论

有向图

有向图（Directed Graph），又称为有向图或有向图形，是图论中的一种图的类型，其中图的边具有方向。在有向图中，每条边都有一个指定的起点和终点，表示从一个顶点（起点）指向另一个顶点（终点）的有向关系。这种有向性使得有向图非常适合表示诸如网络流、有向关系、依赖关系等涉及方向性的问题。

有向图的主要特点包括：

有向边：在有向图中，边是有方向的，通常用箭头表示，箭头从起点指向终点。边的方向表示了关系或流动的方向。
顶点（节点）：与无向图类似，有向图也由一组顶点组成。这些顶点之间通过有向边连接，形成了图的结构。
出度和入度：每个顶点都有一个出度（Out-Degree）和一个入度（In-Degree）的概念。出度表示从该顶点发出的边的数量，入度表示指向该顶点的边的数量。
路径和环：有向图中的路径是由一系列顶点和边组成的序列，其中每一条边都从一个顶点指向下一个顶点。有向图中可以存在环，即从一个顶点出发沿着有向边可以回到自身的路径。
强连通性：在有向图中，有向路径的概念引入了强连通性。一个有向图被称为强连通图，如果对于图中的任意两个顶点 u 和 v，存在从 u 到 v 和从 v 到 u 的有向路径。
有向图在许多领域中都有广泛的应用，包括网络路由、编程语言的控制流图、依赖关系图、社交网络中的关注关系、物流和运输网络等。有向图的性质和算法通常不同于无向图，因此在处理有方向性的问题时，有向图是一个重要的概念。