I'm working on a graph-related problem and a question popped into my mind: we often use linked structures for trees, linked lists, stacks, and queues, but why not for graphs? Since a graph can be considered a superset of a tree, couldn't it also be implemented using linked structures? Instead of left and right pointers, we could use a pointer array, like creating an ArrayList of Nodes. What do you all think could be the potential drawbacks of this approach?
4 Answers
Ultimately, it's all about what works best for your specific problem. In many scenarios, graphs are implicit, meaning nodes are created on-the-fly as you traverse them. Sometimes you don’t even need a structured representation; just use hashing to check if a node has been visited.
The density of the graph really influences how you represent it. Just think about how many edges are connecting the nodes—this can change the structure you choose.
When trying a new data structure, implementing algorithms like DFS, BFS, or Dijkstra's can really show you its strengths and weaknesses. Also, consider this: your suggested structure is a type of adjacency list because each node has a list of adjacent nodes. What's the main difference between your design and the classic adjacency list? Just remember, a Node's identity is linked to its memory address.
You're right! I'm storing references in my ArrayList, which is turning numbers into redundant information instead of nodes as intended.
Using a node structure means that adjacency relies on a list of pointers within the node. On a 64-bit machine, a 32-bit integer is actually smaller than a 64-bit pointer, which can help with efficiency. Also, remember that as graph connectivity grows exponentially, larger structures can slow things down.
Are you talking about the density of incoming and outgoing edges or the nodes themselves?