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

Question

I was trying to implement topological sort in C++ using DFS but I got stuck with the conversion of an adjacency list to an adjacency matrix for the purpose. The problem I am encountering is that for a DAG every node might not have an outgoing edge so I can't simply create an adjacency list with a function like this which is valid for an undirected graph:-

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

So it would be of great help if you could provide a way to implement an adjacency list for a DAG and suggest the code to convert it into an adjacency matrix. An implementation avoiding the use of structs and classes is highly appreciated.

Answer 1

You would only require to add a single edge in that case.

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

Run this function for all the edge pairs, and your adjacency list l will be completed.

Now, create an adjacency matrix as a square 2D array, initialising all the elements initially to 0.

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

Now, simply traverse the adjacency list and for every edge (u, v), set mat[u][v] = 1, denoting that vertex u directs to vertex v.

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

Make sure that l has memory allocated beforehand till atleast V elements so as to not get a Segmentation Fault:

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