I'm considering representing a directory tree in a table.
- Is there a basic result in graph theory to support this? What is it called?
- Does every graph have a matrix representation?
1 Answer
$\begingroup$Yes. Every graph can be described by an adjacency matrix. The vertices index the rows and columns. The entry at row $i$, column $j$ is $1$ if there's an edge from $i$ to $j$ and $0$ otherwise.
So in particular you can represent trees this way. The adjacency matrix for a tree is likely to be quite sparse (lots of $0$s) so perhaps not efficient.
Consider implementing your tree as a list of items where each item is a pair consisting of a vertex $V$ and the list of the vertices connected to $V$. That's essentially reading the adjacency matrix a row at a time, listing the places in each row where there's a $1$.
$\endgroup$
