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

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

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

图着色问题是图标记的一个特例。在这个问题中，每个节点都涂上某种颜色。但是着色有一些约束。我们不能对任何相邻的顶点使用相同的颜色。为了解决这个问题，我们需要使用贪婪算法，但这并不能保证使用最少颜色。输入和输出输入：图的邻接矩阵。0 0 1 0 1 0 0 1 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 1 0 输出：节点：0，分配颜色：0 节点：1，分配颜色：0 ... 阅读更多

Fleury 算法用于从给定图中显示欧拉路径或欧拉回路。在这个算法中，从一条边开始，它试图通过移除之前的顶点来移动其他相邻顶点。使用这种技巧，图在每个步骤中都变得更简单，以便找到欧拉路径或回路。为了获得路径或回路，我们必须检查一些规则-图必须是欧拉图。当有两条边时，一条是桥，另一条是非桥，我们必须首先选择非桥。起始顶点的选择也很棘手，我们不能使用任何顶点作为... 阅读更多

欧拉路径是一条路径，通过它我们可以精确地访问每条边一次。我们可以多次使用相同的顶点。欧拉回路是一种特殊的欧拉路径。当欧拉路径的起始顶点也与该路径的结束顶点连接时，则称为欧拉回路。为了检测路径和回路，我们必须遵循以下条件-图必须是连通的。当恰好有两个顶点具有奇数度时，它是一条欧拉路径。现在，当无向图的任何顶点都没有奇数度时，它就是一个... 阅读更多

欧拉路径是一条路径，通过它我们可以精确地访问每条边一次。我们可以多次使用相同的顶点。欧拉回路是一种特殊的欧拉路径。当欧拉路径的起始顶点也与该路径的结束顶点连接时，则称为欧拉回路。要检查图是否是欧拉图，我们必须检查两个条件-图必须是连通的。每个顶点的入度和出度必须相同。输入和输出输入：图的邻接矩阵。0 1 0 0 0 ... 阅读更多

使用深度优先搜索 (DFS) 遍历算法，我们可以检测有向图中的环。如果任何节点中存在任何自环，则将其视为一个环，否则，当子节点有另一条边连接其父节点时，它也将是一个环。对于不连通图，可能存在不同的树，我们可以称它们为森林。现在我们必须检测森林所有树的环。在这种方法中，我们将使用不同的集合来分配节点以执行 DFS 遍历。有三个不同的集合：白色、灰色和黑色。... 阅读更多

为了检测无向图中是否存在任何环，我们将对给定图使用 DFS 遍历。对于每个已访问的顶点 v，当我们找到任何相邻顶点 u 时，如果 u 已经被访问，并且 u 不是顶点 v 的父节点，则检测到一个环。我们将假设任何一对顶点都没有平行边。输入和输出：邻接矩阵 0 1 0 0 0 1 0 1 1 0 0 1 0 0 1 0 1 ... 阅读更多

深度优先搜索 (DFS) 是一种图遍历算法。该算法从一个起始顶点开始，当找到一个相邻顶点时，它会首先移动到该相邻顶点，并尝试以相同的方式遍历。它会尽可能深入地遍历整个深度，之后回溯到之前的顶点以查找新的路径。要迭代地实现 DFS，我们需要使用栈数据结构。如果要递归地实现它，则不需要外部栈，可以使用递归调用的内部栈来实现。输入和……阅读更多