# 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:

DFSBFS
time complexity$\mathcal{O}(m+n)$$\mathcal{O}(m+n)$
finds shortest pathNoYes
good for infinite graphsNoYes
needs memory forcurrent branchwhole 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