Graph Transversal

Euler Tour

Given a (multi)graph G(V,E). An Euler tour is a cycle in G that contains each edge exactly once.

Euler theorem

A graph has an Euler tour if and only if it is connected and every vertex has an even degree.

Hierholzer’s Algorithm

Start at any unmarked edge and mark the edge to a neighbor. Continue the process at the neighbor.

If there is no such neighbor anymore, a cycle has been marked, otherwise the endpoint would have an odd degree

BFS

Breadth-first search first examines the neighbors of the starting vertex, then their neighbors, then their neighbors, etc., to discover paths.

ALGORITHM

GIVEN: Graph G(V,E)

Starting vertex s ∈ V

1. Create a marking array M of size n. All vertices except s are initially unmarked.

2. Initialize a queue S with s.

3. As long as S is not empty, set v to S.front() and perform S.dequeue(). Then iterate over all outgoing edges {v,w} from v. If w is unmarked, mark w and perform S.enqueue(w).

The edges from the current node to previously undiscovered nodes form a tree (BFS tree) rooted at s.

BFS hopdistance

BFS ALGO

O(n + m)

DFS

Unlike BFS, these hop distance values do not have to be minimal!
As with BFS, the edges to previously undiscovered nodes also form a tree in

DFS, which contains all nodes reachable from s.

Tree edge

The edges (v,w) with pre[w] = v are also called tree edges.

Forward edge

Edges (v,w) that lead to nodes in the subtree of v but are not tree edges arecalled forward edges

Backward edge

Edges (v,w) that lead to a predecessor node of v are called backward edges.

Cross edge

All other edges are called cross edges. These run between different DFS

subtrees.

DFS lemma

In an undirected graph, there are no cross edges.

DFS obs

If there is a non-tree edge in an undirected graph, the graph contains a cycle.

This does not hold in directed graphs

Dfs as recursion

DFS as stack

BFS vs DFS

But only BFS guarantees minimal path length!

DFS can discover long paths faster than BFS (usually when additional

information is available). Otherwise, BFS can also be better