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.

## 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
page revision: 20, last edited: 20 Dec 2008 17:40