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
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[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.