Graphs

📚 Drozdek (Ch. 8)

Definition and Terminology

A graph is a data structure containing nodes and connections between them (much like a tree), but with no requirement for hierarchical ordering.
- We often call the nodes vertices, and the connections between them edges.
- A simple graph, then is the non-empty set of vertices and edges \(G=(V,E)\).

Terminology

A directed graph (or “digraph”) is the non-empty set of vertices and edges \(G=(V,E)\) where the edges \(E={v_i, v_j}\) have a direction associated with them.
- Neither simple graphs nor digraphs allow pairs of vertices to have more than one edge connecting them. A multigraph relaxes this restriction.
- A pseudograph allows an edge to connect a single vertex to itself (a loop).

A directed graph

Terminology

A weighted graph is a graph in which each edge has a number (or weight) assigned.
- Depending on context, weight is also called “cost”, “distance”, “length”, or some other name.
A graph is complete if for each pair of distinct vertices, there is exactly one edge connecting them.

A weighted graph

Terminology

A subgraph is a set of edges and vertices that are themselves subsets of the edges and vertices of a larger graph.
- A subgraph induced by vertices \(V'\) is a graph such that any edges in the subgraph \((V', E')\) are also in the larger graph.
- Two vertices are adjacent if there is an edge connecting them that is a member of the same graph.
- The edge connecting them is said to be incident with them.

A Subgraph (in blue)

Terminology

The degree of a vertex \(v\) is the number of edges incident with \(v\).
- A vertex with no incident edges is called an isolated vertex.
  - It is possible to have a graph \(G\) containing only isolated vertices. (\(E\) can be empty).

Vertex Degrees

Representations

Aside from drawings: Graphs may be represented by
- Adjacency lists
- Adjacency matrices
- Incidence matrices
  - See Drozdek pg 378-379

Representation: Adjacency List

Drozdek, Figure 8.2

Representation: Adjacency matrix

Drozdek, Figure 8.2

Representation: Incidence matrix

Drozdek, Figure 8.2

Traversals

Much like tree traversals, vertices are “visited” one at a time.
Unlike trees, graphs have cycles, so tree traversal algorithms would result in infinite loops.
- A cycle is a path from one vertex \(v_i\) through one or more edges such that the path returns to \(v_i\).
Vertices must be “marked” to avoid re-visiting the same vertex.
Isolated vertices must also be visited in some way.

Depth-First Traversal: Example

Starting with the list \(V\) of vertices, the next available vertex v is visited
- Create the list of vertices adjacent to \(v\) , and perform depth-first traversal on them.
- If v has no adjacent vertices, backtrack to the predecessor of \(v\) .
- When you backtrack to the vertex where you started, you are done.
- Repeat as long as there are unvisited vertices

Depth-First Traversal: Example

Starting with the list \(V\) of vertices, the next available vertex v is visited
- Create the list of vertices adjacent to \(v\) , and perform depth-first traversal on them.
- If v has no adjacent vertices, backtrack to the predecessor of \(v\) .
- When you backtrack to the vertex where you started, you are done.
- Repeat as long as there are unvisited vertices

Depth-First Traversal: Example

Starting with the list \(V\) of vertices, the next available vertex v is visited
- Create the list of vertices adjacent to \(v\) , and perform depth-first traversal on them.
- If v has no adjacent vertices, backtrack to the predecessor of \(v\) .
- When you backtrack to the vertex where you started, you are done.
- Repeat as long as there are unvisited vertices

Depth-First Traversal: Example

Starting with the list \(V\) of vertices, the next available vertex v is visited
- Create the list of vertices adjacent to \(v\) , and perform depth-first traversal on them.
- If v has no adjacent vertices, backtrack to the predecessor of \(v\) .
- When you backtrack to the vertex where you started, you are done.
- Repeat as long as there are unvisited vertices

Depth-First Traversal: Example

Starting with the list \(V\) of vertices, the next available vertex v is visited
- Create the list of vertices adjacent to \(v\) , and perform depth-first traversal on them.
- If v has no adjacent vertices, backtrack to the predecessor of \(v\) .
- When you backtrack to the vertex where you started, you are done.
- Repeat as long as there are unvisited vertices

Depth-First Traversal: Example

Starting with the list \(V\) of vertices, the next available vertex v is visited
- Create the list of vertices adjacent to \(v\) , and perform depth-first traversal on them.
- If v has no adjacent vertices, backtrack to the predecessor of \(v\) .
- When you backtrack to the vertex where you started, you are done.
- Repeat as long as there are unvisited vertices

Depth-First Traversal: Example

Starting with the list \(V\) of vertices, the next available vertex v is visited
- Create the list of vertices adjacent to \(v\) , and perform depth-first traversal on them.
- If v has no adjacent vertices, backtrack to the predecessor of \(v\) .
- When you backtrack to the vertex where you started, you are done.
- Repeat as long as there are unvisited vertices

Depth-First Traversal: Example

Starting with the list \(V\) of vertices, the next available vertex v is visited
- Create the list of vertices adjacent to \(v\) , and perform depth-first traversal on them.
- If v has no adjacent vertices, backtrack to the predecessor of \(v\) .
- When you backtrack to the vertex where you started, you are done.
- Repeat as long as there are unvisited vertices

Depth-First Traversal: Example

Starting with the list \(V\) of vertices, the next available vertex v is visited
- Create the list of vertices adjacent to \(v\) , and perform depth-first traversal on them.
- If v has no adjacent vertices, backtrack to the predecessor of \(v\) .
- When you backtrack to the vertex where you started, you are done.
- Repeat as long as there are unvisited vertices

Depth-First Traversal: Example

Starting with the list \(V\) of vertices, the next available vertex v is visited
- Create the list of vertices adjacent to \(v\) , and perform depth-first traversal on them.
- If v has no adjacent vertices, backtrack to the predecessor of \(v\) .
- When you backtrack to the vertex where you started, you are done.
- Repeat as long as there are unvisited vertices

Depth-First Traversal: Example

This algorithm generates a tree (or forest , a set of trees) called a spanning tree.
- A spanning tree includes all vertices of the original graph, but does not contain any cycles.

Breadth-First Traversals

We have discussed Depth-First traversals, where the traversal choose one path and “follows” it as far as possible before returning to try other paths.

The Breadth-First Traversal instead focuses on visiting all neighboring vertices before proceeding to other vertices.

In a tree-like structure, we could visualize this as working across each level of the tree before proceeding further “down” toward the leaves.

In a graph, the idea is the same - work on all vertices you can discover at the same “level” (distance from the start) before moving further into the graph.

Breadth-First traversals utilize a Queue

Whereas depth-first traversals made use of a stack as the primary “bookkeeping” data structure to allow backtracking, breadth-first traversals will use a queue to aid in prioritizing the ordering of vertex visits. The general algorithm is:

function breadthFirstSearch(graph G):
    let unseen := all vertices from G
    let edges := empty List {}
    let working := empty Queue {}
    for each vertex v in unseen do
        remove v from unseen
        enqueue v into working
        while working is not empty do
            v := dequeue from working
            for all vertices u adjacent to v in G do
                if u is in unseen
                    enqueue u into working
                    insert edge(vu) into edges
    return edges

Breadth-First traversal: Example

Drozdek Fig. 8.5

We’ll start traversing from (a).

Breadth-First traversal: Example

Drozdek Fig. 8.5

We see the nodes with edges from (a) and queue them up…

Breadth-First traversal: Example

Drozdek Fig. 8.5

From (e) we don’t discover anything new; just mark it and continue.

Breadth-First traversal: Example

Drozdek Fig. 8.5

From (f) we don’t discover anything new; just mark it and continue.

Breadth-First traversal: Example

Drozdek Fig. 8.5

From (g) we discover (b) and add it to the queue.

Breadth-First traversal: Example

Drozdek Fig. 8.5

From (i) we don’t discover anything new; just mark it and continue.

Notice that the edges (ef), (ei), (fi) will not be traversed at this point.

Breadth-First traversal: Example

Drozdek Fig. 8.5

From (b) we don’t discover anything new; just mark it and continue.

Now our queue is empty, but we have unvisited nodes, so we pick one ( (c) ) and continue.

Breadth-First traversal: Example

Drozdek Fig. 8.5

From (b) we discover (h) and add it to the queue.

Breadth-First traversal: Example

Drozdek Fig. 8.5

From (h) we discover (d) and add it to the queue.

Breadth-First traversal: Example

Drozdek Fig. 8.5

From (d) we don’t discover anything new.

Also, our queue is empty now, so we check for unvisited nodes…

But there are none. That means we are finished.

Breadth-First traversal: Example

Drozdek Fig. 8.5

Final state, with visit ordering shown.

Edges that were traversed are shown in solid black; edges not traversed are shown in dotted grey.

Dijkstra’s Algorithm

Let the node at which we are starting be called the initial node. Let the distance of node \(Y\) be the distance from the initial node to \(Y\). Dijkstra’s algorithm will assign some initial distance values and will try to improve them step by step.

Dijkstra’s Algorithm

Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
Mark all nodes except the initial node as unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes except the initial node.

Dijkstra’s Algorithm

For the current node, consider all of its unvisited neighbors and calculate their tentative distances.

For example, if the current node \(A\) is marked with a distance of 6, and the edge connecting it with a neighbor \(B\) has length 2, then the distance to \(B\) (through \(A\)) will be \(6+2=8\).
If this distance is less than the previously recorded distance, then overwrite that distance. Even though a neighbor has been examined, it is not marked as visited at this time, and it remains in the unvisited set .

Dijkstra’s Algorithm

When finished considering the neighbors of current node, mark current node as visited and remove it from the unvisited set . A visited node will never be checked again; its distance recorded now is final and minimal.

The next current node will be the node marked with the lowest (tentative) distance in the unvisited set .
If the unvisited set is empty, then stop. The algorithm has finished. Otherwise, set the unvisited node marked with the smallest tentative distance as the next “current node” and go back to step (3).

Dijkstra’s Algorithm

function Dijkstra(Graph, source):
    let Q be an empty queue
    for each vertex v in Graph.Vertices:  # Initialize
        dist[v] ← INFINITY
        prev[v] ← UNDEFINED
        add v to Q
    dist[source] ← 0
    
    while Q is not empty:
        u ← vertex in Q with min dist[u]
        remove u from Q
        
        for each neighbor v of u still in Q:
            alt ← dist[u] + Graph.Edges(u, v)
            if alt < dist[v]:
                dist[v] ← alt
                prev[v] ← u
    return dist[], prev[]

Source: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Dijkstra’s Algorithm Example

Drozdek, Figure 8.7

Dijkstra’s Algorithm Example

Drozdek, Figure 8.7

Dijkstra’s Algorithm Example

Drozdek, Figure 8.7

Dijkstra’s Algorithm Example

Drozdek, Figure 8.7

Dijkstra’s Algorithm Example

Drozdek, Figure 8.7

Dijkstra’s Algorithm Example

Drozdek, Figure 8.7

Dijkstra’s Algorithm Example

Drozdek, Figure 8.7

Dijkstra’s Algorithm Example

Drozdek, Figure 8.7

Dijkstra’s Algorithm Example

Drozdek, Figure 8.7

Dijkstra’s Algorithm Example

Drozdek, Figure 8.7

Dijkstra’s Algorithm Example

Drozdek, Figure 8.7

Dijkstra’s Algorithm Example

Drozdek, Figure 8.7

You can find the shortest path by backtracking to the points where the “best” assigned distance updated to the final value.

Ford’s Algorithm (Bellman-Ford algorithm)

Dijkstra’s Algorithm does not work if some weights are negative.

To solve this problem, a label-correcting algorithm can be used.

Ford’s algorithm is an example.

Does not permanently determine the shortest distance for any vertex until it processes the entire graph.

Ford’s Algorithm (Bellman-Ford algorithm)

function BellmanFord(list vertices, list edges, vertex source) is
    distance := list of size n
    predecessor := list of size n

    for each vertex v in vertices do // Step 1: initialize graph
        distance[v] := inf           // Init. vertex dist. to infinity
        predecessor[v] := null       // Init. a null predecessor
    
    distance[source] := 0            // Dist. to self is zero.

    repeat |V|−1 times:              // Step 2: relax edges repeatedly
         for each edge(u, v) with weight w in edges do
             if distance[u] + w < distance[v] then
                 distance[v] := distance[u] + w
                 predecessor[v] := u

                                     // Step 3: error if neg. weight cycle
    if a negative-weight cycle exists, raise an error 

    return distance, predecessor

Source: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

General Label-Correcting Algorithm

Based on Drozdek, Chapter 8.3

function labelCorrectingAlgorithm (weighted simple digraph Graph, vertex first)
    for all vertices v in Graph do      // Step 1: initialize graph
        currDist[v] := inf              // Init. vertex dist. to infinity
    currDist[first] := 0                // Dist. to self is zero
    toBeChecked := {first}              // Set of vertices to check
    while toBeChecked is not empty      // Step 2: relax edges repeatedly
        v := a vertex in toBeChecked
        remove v from toBeChecked
        for all vertices u adjacent to v do
            if currDist[u] > currDist[v] + weight(edge(vu))
                currDist[u] := currDist[v] + weight(edge(vu))
                predecessor[u] := v
                add u to toBeChecked if it is not there

Efficiency hinges on the data structure used for toBeChecked

All-To-All Shortest PathsThe WFI Algorithm

Based on Drozdek, Chapter 8.3

function WFI(matrix weights):
   for i := 1 to numberOfVertices do
      for j := 1 to numberOfVertices do
         for k := 1 to numberOfVertices do
            if weights[j][k] > weights[j][i] + weights[i][k] then
               weights[j][k] := weights[j][i] + weights[i][k] then         
   return weights

weights is an adjacency matrix
N-cubed efficiency…
Can detect cycles if the diagonal of the weight matrix is initialized to infinity.

Cycle Detection

We often need to detect cycles in both directed and undirected graphs.

Depth-First Traversal can be used for this.

Cycle Detection: Undirected Graphs

function detectCyclesDFS(vertex v, Graph G):
    let static visited := {}   // Set of visited nodes (shared between calls)
    let static edges   := {}   // Set of edges found (shared for all calls)
    let has_cycle := false
    insert v into visited
    for each vertex u in G adjacent to v do
        if u is not in visited:
            has_cycle := has_cycle || detectCyclesDFS(u, G)
        else if edge(u,v) is not in edges:
            has_cycle := true  // cycle detected
        add edge(u,v) to edges
    return has_cycle

Cycle Detection: Digraphs

Algorithm is a bit more complicated. Label vertices as “working” when we discover them, and as “finished” when we exhaust recursively traversing all adjacent nodes.

If we see a vertex labeled “working” for the second time, we have a cycle.

function detectDigraphCyclesDFS(vertex v, Graph G):
    let has_cycle := false
    label[v] = WORKING         // label the current vertex as "working"
    for each vertex u in G adjacent to v do
        if u has no label yet:
            has_cycle := has_cycle || detectDigraphCyclesDFS(u, G)
        else if label[u] is not FINISHED
            has_cycle := true  // cycle detected
    num[v] = FINISHED          // mark v as "finished"
    return has_cycle

Eulerian Graphs

(Euler is pronounced very much like “oiler”.)

An Eulerian trail is a path that includes all edges of the graph only once.
An Eulerian cycle is a cycle that is also an Eulerian trail.
An Eulerian graph is a graph that has an Eulerian cycle.
- A graph is Eulerian if every vertex is incident to an even number of edges.

Finding Eulerian Cycles : Fleury’s Algorithm

“Only take a bridge when there is no other path to take.”

function FleuryAlgorithm(undirected graph G):
    let success := false
    let v := any vertex in G
    let path := v
    let untraversed := G
    while v has untraversed edges
        let e represent an edge to be determined later
        if edge(v,u) is the only untraversed edge
            e := edge(v,u)
            remove v from untraversed
        else e := edge(v,u) which is not a bridge in untraversed
        path := path + u
        remove e from untraversed
        v := u
    if untraversed has no edges
        success := true
    return success, path

Eularian graph and cycle

Drozdek, Figure 8.34

An Eulerian graph

An Eulerian path illustrated (numbers indicate traversal order from b)

Hamiltonian Graphs

A Hamiltonian cycle is a cycle that passes through all the vertices of the graph.
- A Hamiltonian graph is a graph that includes at least one Hamiltonian cycle.
- All complete graphs are Hamiltonian.
  - As a consequence, an algorithm of first create a complete graph using false edges, then reducing it can be used to find Hamiltonian cycles in incomplete graphs.

Hamiltonian Graph

Image: https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg

The Traveling Salesman Problem (TSP)

Given a set of \(n\) cities, find the minimum length tour in which each city is visited exactly once, then you return home.

This is equivalent to finding the minimum Hamiltonian cycle.
If distances between each of the \(n\) cities are known, there are \((n - 1)!\) possible routes.
- Eliminating reverse routes, you get \(\frac{(n - 1)!}{2}\)
- Clever algorithms can do it in a polynomial factor of \(2^n\) steps…

Graphs