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 ... 阅读更多