福特-福克森算法用于检测给定图中从起始顶点到汇点顶点的最大流。在此图中，每条边都有容量。提供两个名为源和汇的顶点。源顶点具有所有向外边，没有向内边，而汇点将具有所有向内边，没有向外边。有一些约束条件：边的流量不超过该图的给定容量。除了源和汇之外，每个边的流入流和流出流也将相等。输入和输出输入：邻接矩阵：0 10 0 10 0 0 0 0 4 ... 阅读更多

有向无环图的拓扑排序是顶点的线性排序。对于有向图的每条边 U-V，顶点 u 将在排序中出现在顶点 v 之前。众所周知，源顶点将在目标顶点之后出现，因此我们需要使用堆栈来存储先前的元素。完成所有节点后，我们可以简单地从堆栈中显示它们。输入和输出输入：0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 ... 阅读更多

Tarjan 算法用于查找有向图的强连通分量。它只需要一次 DFS 遍历即可实现此算法。使用 DFS 遍历，我们可以找到森林的 DFS 树。从 DFS 树中，找到强连通分量。当找到此类子树的根时，我们可以显示整个子树。该子树是一个强连通分量。输入和输出输入：图的邻接矩阵。 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 输出：以下是在给定... 阅读更多

我们了解著名的蛇梯游戏。在这个游戏中，棋盘上有一些房间，带有房间号。一些房间通过梯子或蛇连接。当我们得到梯子时，我们可以爬到一些房间以接近目的地，而无需依次移动。类似地，当我们得到一些蛇时，它会将我们送到一个较低的房间，从该房间重新开始旅程。在此问题中，我们必须找到到达起点到目的地的最小骰子投掷次数。输入和输出输入：起点和... 阅读更多

如果一个有向图中每个顶点对之间都存在一条路径，则称该有向图是强连通的。为了解决此算法，首先使用 DFS 算法获取每个顶点的完成时间，现在找到转置图的完成时间，然后根据拓扑排序按降序对顶点进行排序。输入和输出输入：图的邻接矩阵。 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 输出：以下是给定... 阅读更多

提供一个有向图，其中包含每对顶点之间的权重，并且还提供了两个顶点 u 和 v。我们的任务是找到从顶点 u 到顶点 v 的最短距离，且恰好有 k 条边。为了解决此问题，我们将从顶点 u 开始并转到所有相邻顶点，并使用 k 值作为 k - 1 对相邻顶点进行递归。输入和输出输入：图的成本矩阵。 0 10 3 2 ∞ 0 ∞ 7 ∞ ∞ 0 6 ∞ ∞ ∞ 0 输出：最短... 阅读更多

二分匹配是指以这样一种方式选择图中的一组边，即该集中没有两条边共享端点。最大匹配是匹配最大数量的边。当找到最大匹配时，我们不能再添加另一条边。如果向最大匹配图中添加一条边，它将不再是匹配。对于二分图，可能存在多个最大匹配。输入和输出输入：邻接矩阵。 0 1 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 ... 阅读更多

给定一个加权有向无环图。还提供了另一个源顶点。现在我们必须找到从起始节点到图中所有其他顶点的最短距离。为了检测较小的距离，我们可以使用另一种算法，例如 Bellman-Ford 用于具有负权重的图，对于正权重，Dijkstra 算法也有帮助。这里对于有向无环图，我们将使用拓扑排序技术来降低复杂度。输入和输出输入：图的成本矩阵。 0 5 3 -∞ -∞ -∞ -∞ 0 2 6 -∞ -∞ -∞ -∞ 0 7 4 2 -∞ ... 阅读更多

如果一个图的顶点可以分成两个独立的集合，使得图中的每条边要么从第一个集合开始并在第二个集合结束，要么从第二个集合开始，连接到第一个集合，换句话说，我们可以说在同一个集合中找不到任何边，则称该图是二分图。可以使用顶点着色来检查二分图。当一个顶点在同一个集合中时，它具有相同的颜色，对于另一个集合，颜色将发生变化。输入和输出输入：... 阅读更多

给定一个加权有向无环图。还提供了另一个源顶点。现在我们必须找到从起始节点到图中所有其他顶点的最长距离。我们需要对节点进行拓扑排序，并将拓扑排序后的结果存储到堆栈中。之后反复从堆栈中弹出并尝试为每个顶点找到最长距离。输入和输出输入：图的成本矩阵。 0 5 3 -∞ -∞ -∞ -∞ 0 2 6 -∞ -∞ -∞ -∞ 0 7 4 2 -∞ -∞ ... 阅读更多