Graph Theory

Graph Theory deals with trees, and more generally, graphs. In general graphs are more interesting than trees as the can model real situations easily.


With graphs, choosing which algorithm to use is incredibly dependent on the problem and its constraints. Say you have weights on the nodes. Never use DFS or BFS then. Instead, use Dijkstra's Algorithm. Say you know that the solution will be in the fifth level of a tree. Then try DFS or Iterative DFS. Make sure not to lock yourself into a "best" algorithm. All search their own purposes.


Iterative DFS


Shortest Path


Minimal Spanning Tree

Eulerian Tour

Network Flow



Trees are assembled from a root node and children. Each child is in turn a node that can have more children. The one requirement is that there cannot be a node that is the child of two different nodes.


In this examples, we have 'Encyclopaedia' as the root node. It's children are 'Science' and 'Culture', and 'Culture's children are 'Art' and 'Craft'


When the input is going to be 'tree-like', as in, it will fit this data structure. Normally, opt for graphs



Graphs are more interesting because the limitations of what nodes can be children of which are removed. This produces interesting ("real-word") situations.



Graphs can be used whenever you have nodes that are connected to similar nodes and these connections can quantified. One example would be a map of the cities in Romania (roads are connecting the cities).


  • node - a single item (say, a city)
  • vertices - a node
  • edge - a path
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License