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:

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