# Manipulating Adjacency matrix

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?

## 1 Answer

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.