# Graphs

### Definitions #

**Degree**of a node: the number of edges connected to it**Connected**graph: there is a path betwen any two nodes**Weighted**graph: every edge has a weight

### Euler paths/cycles #

**Euler path**: a path that visists every edge of a graph exactly once**Euler cycle**: an Euler path that starts and ends at the same vertex- A connected graph has an
**Euler cycle**if and only if**all nodes have an even degree** - A connected graph has an
**Euler path**if**at most two nodes have an odd degree**

### Simple #

**Simple path**: when all nodes are different**Simple cycle**: when all nodes are different (execpt begin/end) and it contains at least 3 nodes**Simple graph**: when it contains no loops and no paralel edges

### Trees as graphs #

- A tree is a connected simple graph without simple cycles
**Spanning tree**: a full subgraph that is a tree**Minimal spanning tree**: an undirected spanning tree for which the weight is minimal

### DFS vs BFS #

Let $m$ the number of edges and $n$ the number of nodes in a graph:

DFS | BFS | |
---|---|---|

time complexity | $\mathcal{O}(m+n)$ | $\mathcal{O}(m+n)$ |

finds shortest path | No | Yes |

good for infinite graphs | No | Yes |

needs memory for | current branch | whole level (queue of nodes) |

### Dijkstra's Algorithm #

Computes the shortest paths from any gives node to all other nodes.

Let $m$ the number of edges and $n$ the number of nodes in a graph:

- Every node is
`enqueue`

'd and`removeMin`

'd once - Every node $v$ is repositioned in the priority queue at most $degree(v)$ times
- The sum of all degrees is $2m$
- Each action (
`enqueue`

/`removeMin`

/`reposition`

) takes $\mathcal{O}(\log{(n)})$ time

Conclusion: the time complexity for Dijkstra's algorithm is: $\mathcal{O}((n+m)\log{(n)})$

### A* algorithm #

Uses a heuristic such that less nodes of the graph have to be traversed. Often the distance between locations is used.

### DFS to find path #

```
algorithm FindPath(G, v, w):
if v == w:
return TRUE
give v the label PATH
forall e incident with v do:
if e has no label then:
x <- the other node incident with e
if x has no label then:
give e the label PATH
if FindPath(G, x, w):
return TRUE
remove the label PATH from e
else:
give e the label OLD
return FALSE
```

### BFS to find shortest path #

On weighted graphs you would use Dijkstra's but on unweighted graphs you can use this.

```
prev[node] -> node
algorithm FindShortestPath(G, v):
prev[v] <- NULL
Q <- empty queue of nodes
give v the label VISITED
enqueue(v)
while Q not empty do
x <- dequeue()
if x = w
return prev
forall e incident with u do
if e has no label then
w <- the other node incident with e
if w has no label then
give e the label NEW
give w the label VISITED
prev[u] = x
enqueue(w)
else
give e the label OLD
```

## Shortest path from Dijkstra #

Uses a predesessor array to keep track of the path

```
path Dijkstra(g, v, w)
parent = parent nodes in shortest path tree
d = array of distances
p = min prio queue
while S is not empty do:
u = pop(P)
if u != w:
remove u from P
for all z in neighours:
if d[u] + dist[u][z] < d[z]:
d[z] = d[u] + dist[u][z]
parent[z] = u
else // the final node
path = empty path
add v to P
// backwards
while u != v:
u = parent(v)
add v to beginning of path
```