What are the pros and cons of objects-pointers graph representation? In which cases it's better than Adjacency list and Adjacency matrix? What are the complexity of insertion, deletion, adding an edge, deleting an edge, check for a neighbor, check size of neighbors of a vertex ?
1 Answers
0
votes
If you mean representation by allocated (new, malloc, etc.) node objects that contain lists of pointers to other nodes, then the main difference is that you don't automatically get references to all the nodes in the graph as you do with numbered nodes and adjacencies stored in an array indexed by node number. You're normally interested in distinguished nodes like sources and/or sinks, so keep only lists of these subsets around.
Of course if you allocate the node objects from an array, then the two forms are perfectly equivalent.
If factors of 2 matter in your application, on 64-bit machines you save space by storing up to 4 giga-nodes in an array because you can refer to them with 32-bit indices rather than 64-bit pointers. Indices are also a little more readable for debugging: Node 42 rather than the Node at 0xf23a456792341280.
The only disadvantage of adjacency list/nodes in arrays is deletion. To get back space from deleted nodes, you need to squeeze the deleted entries out of the array and adjust all the adjacencies or pointers to match.
