Algorithms in Graphs
Input Repr
Adjacency Matrix
- Cannot be used with parallel edges
- requires \(n^{2}\) bits of memory
Incidence Matrix
- Parallel Edges can be represented
- Repesented by \(A(G)\)
- requires \(n.e > n^{2}\) bits of memory
Edge Listing
- List out edges in ordered edge pairs
- Eg: \((1,2),(2,3) \dots\)
- can also repr self loops and \(\parallel\) edges
- Bits req to label(1 thorugh \(n\)) each vertex is b, where
\(2^{b-1}< n \leq 2^{b}\)
- If the matrix is sparse, edge listing is more efficient
Successor Listing
- Number vertexes from \(1 - n\)
- Repr as a linear array
- \(n(1+d_{avg})\) is the storage requirements
Algorithms for Connectedness and Components
- Uses fusion of adjacent vertices
- We start with some vertice in the graph and fuse all vertices that are adjacent to it