编写一个程序来使用深度搜索（DFS）算法解决拓扑排序问题

发布于 2025-01-31 13:18:09 字数 194 浏览 2 评论 0原文

我想使用深度第一次搜索（DFS）来使用拓扑排序以解决给定的问题（下面附加的有向图）。

单击此处查看图像。

您能用任何编程语言为给定问题编写适当的代码来帮助您吗？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

嗫嚅 2025-02-07 13:18:09

回顾：如果图中的所有边缘从较高的顶点到较低数字的顶点（或相反的方式），则图表的排序是拓扑排序。

这意味着，如果拥有一个顶点v，您将能够以某种方式访问所有可从v访问的顶点，并给它们的数字低于您给出的数字代码> v ，然后所有的边缘从v中>> v 将导致编号低于v的顶点，因此它们将符合拓扑排序的定义。

现在，我们的目标是实现上述所有顶点。

回想一下DFS在这里可能很有用，因为DFS访问了可从给定顶点访问的所有顶点。

我们必须为所有顶点运行DFS，但是由于DFS是一种递归算法，因此它将自行运行，以从可从运行DFS的其他顶点访问所有顶点。因此，我们必须为所有顶点运行DFS，以DFS函数的 exit 的顺序编号，因为在DFS函数的末尾，我们知道从给定顶点访问的所有顶点都已访问。

这是C ++中的一些示例代码：

#include <vector> // we'll need vector for an adjacency list graph representation

const maxN = 1'000'000 // maximum number of vertices

vector<int> graph[maxN]; // the adjacency list representation of the graph

bool visited[maxN]; // filled with the value false by default
int postOrder[maxN]; // array with the so-called post-order ordering of the vertices
int counter = 1;

void DFS(int v) {
  visited[v] = true; // mark vertex as visited
  for (int neighbour : graph[v]) { // for each neighbour of v
    if (!visited[neighbour]) { // if the neighbour wasn't already visited
      DFS(neighbour); // run the DFS for that neighbour
    }
  }
  // Finally, after all the vertices accessible from v have been numbered,
  // give v the next number, and increase the counter.
  postOrder[v] = counter;
  counter++;
}

void sortTopologically() {
  // For each unvisited vertex, run the DFS starting in that vertex.
  for (int v = 0; v < maxN; v++) {
    if (!visited[v]) {
      DFS(v);
    }
  }
}

这称为a

祝您大学课程好运！

To recap: an ordering of the vertices of a graph is a topological sorting if all edges in the graph lead from higher-numbered vertices to lower-numbered vertices (or the other way around).

This means, that if, having a vertex V, you'd be able to somehow visit all vertices accessible from V and give them numbers lower than the number you give to V, then all edges going out of V will lead to vertices numbered lower than V, so they will conform to the definition of a topological sorting.

It is now our goal to achieve the above for all vertices.

Recall that a DFS could be useful here, because a DFS visits all vertices accessible from a given vertex.

We must run the DFS for all vertices, but since the DFS is a recursive algorithm, it will run itself for all vertices accessible from other vertices for which the DFS is run. Thus, we must run the DFS for all vertices, numbering the vertices in the order in which we exit from the DFS function, because at the end of the DFS function we know that all vertices accessible from a given vertex have been visited.

Here's some sample code in C++:

#include <vector> // we'll need vector for an adjacency list graph representation

const maxN = 1'000'000 // maximum number of vertices

vector<int> graph[maxN]; // the adjacency list representation of the graph

bool visited[maxN]; // filled with the value false by default
int postOrder[maxN]; // array with the so-called post-order ordering of the vertices
int counter = 1;

void DFS(int v) {
  visited[v] = true; // mark vertex as visited
  for (int neighbour : graph[v]) { // for each neighbour of v
    if (!visited[neighbour]) { // if the neighbour wasn't already visited
      DFS(neighbour); // run the DFS for that neighbour
    }
  }
  // Finally, after all the vertices accessible from v have been numbered,
  // give v the next number, and increase the counter.
  postOrder[v] = counter;
  counter++;
}

void sortTopologically() {
  // For each unvisited vertex, run the DFS starting in that vertex.
  for (int v = 0; v < maxN; v++) {
    if (!visited[v]) {
      DFS(v);
    }
  }
}

This is called a post-order ordering and is a very common way to topologically sort a directed graph. You can then easily check if the topological sorting exists by verifying that all edges lead from a higher-numbered vertex to a lower-numbered vertex.

Good luck with your university course!

回复收藏 0 原文

~没有更多了~