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:

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