在 C++ 中将邻接列表转换为有向无环图的邻接矩阵

Question

我试图在 C++ 中使用 DFS 实现拓扑排序，但我被困在将邻接列表转换为邻接矩阵的过程中。我遇到的问题是，对于 DAG，每个节点可能没有传出边，所以我不能简单地创建一个邻接列表，它具有这样一个对无向图有效的函数：-

void addEdge(list <int> l,int u,int v)
{
        l[u].push_back(v);
        l[v].push_back(u);
}

因此，如果您能提供一种为 DAG 实现邻接列表的方法并建议将其转换为邻接矩阵的代码，那将是非常有帮助的。高度赞赏避免使用结构和类的实现。

Answer 1

在这种情况下，您只需要添加一条边。

void addEdge (vector <list <int>> l, int u, int v)
{
    l[u].emplace_back (v); // u directs to v 
}

运行这个函数对所有的边对，你的邻接表l就完成了。

现在，创建一个邻接矩阵作为二维方形数组，将所有元素初始化为 0。

int mat[V][V] = {}; // V is the total number of vertices in the graph

现在，只需遍历邻接表并为每条边 (u, v) 设置 mat[u][v] = 1，表示顶点 u 指向顶点 v.

for (int u = 0; u < V; ++u)
    for (auto v: l[u])
        mat[u][v] = 1;

确保 l 已预先分配至少 V 个元素的内存，以免出现分段错误：

vector <list <int>> l(V);

Answer 2

实际上，您可以根据邻接表实现 DFS（以及拓扑排序）。事实上，邻接表是表示 DFS 图的最有效方式（见下文）。

DFS 所需要的只是能够查看哪些顶点与当前顶点相邻：

vector<list<int>> graph;
vector<bool> visited;

void dfs(int current) {
  visited[current] = true;

  // iterating over adjacent vertices
  for (int other : graph[current])
    if (not visited[other])
      dfs(other);
}

所以你的拓扑排序看起来像这样：

enum class status { unseen, entered, left };

vector<list<int>> graph;
vector<status> visited;
vector<int> topsorted;

void topsort_impl_dfs(int current) {
  visited[current] = status::entered;

  // iterating over adjacent vertices
  for (int other : graph[current]) {
    if (visited[other] == status::unseen) {
      dfs(other);
    } else if (visited[other] == status::entered) {
      // found a loop, not a DAG
    }
    // ignoring vertices with status::left, because they're already processed
  }

  topsorted.push_back(current);
  visited[current] = status::left;
}

void topsort() {
  fill(visited.begin(), visited.end(), status::unseen);

  topsorted.clear();
  topsorted.reserve(VERTEX_COUNT);

  for (int v = 0; v < VERTEX_COUNT; ++v) {
    if (visited[v] == status::unseen) {
      topsort_impl_dfs(v);
    }
  }

  // vertices are added to topsorted in an inverse order
  reverse(topsorted.begin(), topsorted.end());
}

如果我们将 DFS 的实现与邻接矩阵和列表进行比较，就会得到（V 是顶点数，E 是边数）：

对于邻接矩阵：在每次调用dfs(v)时（每个顶点调用一次，总共V）我们将迭代相应的矩阵行（V 迭代）。所以我们得到 O(V*V) 复杂度。
对于邻接列表：对于每个顶点，我们只迭代相邻的顶点。从那个角度分析这个更难，因为顶点的相邻顶点数不同。但我们可以这样看：对于每个顶点，我们迭代所有出边。每条边只有一个起点，因此，我们总共进行 E 次迭代，复杂度为 O(E)。它并不比第一种方式差，因为在最坏的情况下（完整图表）我们将有 E = O(V*V).

因此，如果您的图表有 V=1000 E=1000，那么第二种方式将快约 1000 倍。

在 C++ 中将邻接列表转换为有向无环图的邻接矩阵

Converting an Adjacency List to a an Adjacency Matrix for a Directed Acyclic Graph in C++

c++

graph-theory

depth-first-search

directed-acyclic-graphs

topological-sort