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.

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.

500px-Binary_tree_structure.svg.png

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.

333px-6n-graf.svg.png

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
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License