Graph Theory deals with trees, and more generally, graphs. In general graphs are more interesting than trees as the can model real situations easily.
Algorithms
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.
DFS
Iterative DFS
BFS
Shortest Path
Floyd-Warshall
Minimal Spanning Tree
Eulerian Tour
Network Flow
Trees
Introduction
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'
Uses
When the input is going to be 'tree-like', as in, it will fit this data structure. Normally, opt for graphs
Graphs
Introduction
Graphs are more interesting because the limitations of what nodes can be children of which are removed. This produces interesting ("real-word") situations.
Uses
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).
Vocabulary
- node - a single item (say, a city)
- vertices - a node
- edge - a path