0
$\begingroup$

I have created an adjacency matrix which looks something like this

    A   B   C   D   E   F   G   H   I
A   0   0   0   0   0   0   0   0   0
B   1   0   0   0   0   0   0   0   0
C   1   0   0   0   0   0   0   0   0
D   0   0   0   0   0   0   0   0   0
E   1   1   0   1   0   0   0   0   0
F   1   1   1   1   1   0   0   0   0
G   0   0   1   1   0   0   0   0   0
H   0   1   0   0   0   0   1   0   0
I   1   1   0   0   0   1   0   0   0

I am trying to manipulate this matrix such that an indirect link between two alphabet will replace the direct link. e.g. In the graph, C is connected to A and F is connected to both A and C (among others) and I is connected to both A and F. How do I go about removing the direct connections such as A and F, A and I since there are indirect connection between (C to A and F to C, C to A and F to C and I to F).

I tried using loop but it seems like more the indirect connection, the number of loop required increases as well. What type of algorithm should I use for this type of problem? Would adjacency list be a better alternative?

$\endgroup$
1
$\begingroup$

If I understand you correctly, one solution to your problem would be to compute a spanning forest. A spanning forest of a graph is a smallest possible (in terms of number of edges) graph such that there's a path between two vertices in the forest if, and only if, there's a path between them in the original graph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.