How to approach Dynamic graph related problems?

How do I approach graph/tree related problems? What are the data structures used for graph storage in practice?

• Answer:

  Note: I am going to keep it as simple and basic as I can. Graph, as you know is a collection of nodes and edges/connections between these nodes. Tree, on the other hand can be viewed as a graph without any cycle.  There would be several ways to represent these. I would broadly divide them into 2, say, 1. Static representation and 2. Dynamic representation. (I will talk about a static graph and dynamic tree. You can then take it further using links at the end.) Static representation(fixed size): This would be simply using a matrix. Say, you knew in advance that the maximum number of nodes in the graph will be 10000. In such a case you would make a fixed size matrix, called adjacency matrix as, adjacency[10000][10000]; You can choose the type to be boolean or integer. If you just want to store if there's a connection between two nodes, use a boolean and set, adjacency[i][j]=adjacency[j][i]=true; On the other hand, say you had weighted graph, make the type of adjacency as integer and store the weight. adjacency[i][j]=adjacency[j][i]=WEIGHT_OF_THE_EDGE; Now, its easy to access a particular edge or its weight, as easy as accessing an element of a matrix. Disadvantages: 1. You should know the maximum number of nodes. 2. Lot of space is wasted. You should be able to realize why. 3. Complexity in most algorithms would increase as the entire matrix will be scanned. Dynamic representation(grows): I called above representation to be static because we assumed a fixed size which is why we had several disadvantages. Obviously dynamic representation would be to have a node as an object. Imagine a tree node. What all does it have? A value which is an integer(for example), a left child and a right child? There you go, make a class or struct like: class Node {       int data;       Node leftChild, rightChild; } While creating the tree, simply create a Node newNode=new node(); for each new node. While assigning it to a parent p as a child do, p.leftChild= newNode; or p.rightChild=newNode; Advantages: 1. Faster access. 2. Lower complexity for most algorithms. 3. Much less wastage of space. Some useful links: http://www.geeksforgeeks.org/graph-and-its-representations/ This is very classic description of graph(both static and dynamic). http://webdocs.cs.ualberta.ca/~holte/T26/tree-as-array.html - This explains static tree(using array). try this if you understood the representations and know a little bit of basics- http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/ Hope this helps :)