[Solved]: How to Convert a Directed Graph to an Undirected Graph (Adjacency Matrix)

Problem Detail: 

Given an adjacency matrix, what is an algorithm/pseudo-code to convert a directed graph to an undirected graph without adding additional vertices (does not have to be reversable)?

similar question here

Asked By : Ibrahim

Answered By : Irvin Lim

Note that for an undirected graph, the adjacency matrix is symmetric, i.e. A[i,j] == A[j,i].

From this, we can see that we can simply compute the new value of A[i,j] = A[j,i] depending if A[i,j] or A[j,i] is set. Assuming the graph is unweighted, we can do:

for i from 0 to n-1     for j from 0 to i         if A[i,j] == 1 OR A[j,i] == 1             A[i,j] = A[j,i] = 1         else              A[i,j] = A[j,i] = 0 

Note that we only have to consider 1 + 2 + 3 + ... + n-1 entries since the resultant adjacency matrix is symmetric.

If we have a weighted graph, we now have the problem of which edge weight to take as the new undirected graph edge weight. For example, if w(2,5) = 5 but w(5,2) = 10, the resultant edge weight is ambiguous. However, this is enough for you to figure out what else you need from here.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56195

 Ask a Question

 Download Related Notes/Documents