Bellman-Ford 算法用于查找从源顶点到任何其他顶点的最小距离。该算法与 Dijkstra 算法的主要区别在于，在 Dijkstra 算法中，我们无法处理负权重，但在这里我们可以轻松地处理它。Bellman-Ford 算法以自底向上的方式查找距离。首先，它找到路径中只有一条边的那些距离。之后增加路径长度以找到所有可能的解决方案。输入和输出输入：图的成本矩阵：0 6 ∞ 7 ∞ ∞ 0 5 8 -4 ∞ -2 0 ∞ ∞ ∞ ... 阅读更多

给定一个图；我们必须检查给定的图是否为星形图。通过遍历图，我们必须找到度数为 1 的顶点数，以及度数为 n-1 的顶点数。（这里 n 是给定图中的顶点数）。当度数为 1 的顶点数为 n-1 且度数为 (n-1) 的顶点数为 1 时，则它是一个星形图。输入和输出输入：邻接矩阵：0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 输出： ... 阅读更多

传递闭包是图中从顶点 u 到达顶点 v 的可达性矩阵。给定一个图，我们必须找到一个从另一个顶点 u 可达的顶点 v，对于所有顶点对 (u, v)。最终矩阵是布尔类型。当顶点 u 到顶点 v 的值为 1 时，表示从 u 到 v 至少存在一条路径。输入和输出输入：1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 输出：传递闭包矩阵 1 1 1 ... 阅读更多

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