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

Question

我试图使用DFS在C ++中实现拓扑排序，但是为此我陷入了将邻接表转换为邻接矩阵的困境。我遇到的问题是，对于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将完成。

现在，将邻接矩阵创建为方形2D数组，并将所有元素初始初始化为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倍。