Graph Representations

Edge List

The edge list structure is implemented making use of two main linked list, one of vertexes, and one of edges.

Each vertex object simply contains the item stored at the vertex.

Each edge contains the edge weight, and the from/to ends of the edge.

Adjacency List

Extension on the edge list structure, with an extra list of nodes present at each vertex object. This allows easy traversal from a vertex along each of its edges.

Adjacency Matrix

Similar to Edge List, adds integer keys to vertexes. Adds a 2d Adjacency array, contains reference to the edge object for any edge from i to j.


DFS & BFS

O(n+m)


Directed Graphs

Strong connectivity

This occurs when each vertex can reach every other vertex in a directed graph.

To determine strong connectivity, start a DFS at v, if all nodes visited, perform a DFS starting at v, with all edges reversed, if all nodes visited, the graph is strongly connected, otherwise it is not.


Transitive Closure

Transitive closure is adding extra edges into a graph, such that if a->b->c, a new edge a->c is created.

n*DFS

Can perform DFS from every node O(n(n+m))

Floyd-Warshall

Floyd-Warshall is the dynamic programming method to compute transitive closure.

for i = 0 to V-1:

    for s = 0 to V-1:
        for t = 0 to V-1:
            if (A[s][i] && A[i][t]):
                A[s][t] = true

Floyd Warshall is specifically suited to the Adjacency Matrix Structure. O(n^3), assuming areAdjacent(i,j) is O(1)


Topological Ordering

Topological Ordering is numbering the edges such that for all edges (vi,vj), i < j. This will only be possible if the graph is a Directed Acyclic Graph (DAG).

Perform a DFS with an outer loop that ensures all connected components are found, whilst the recursion is unwinding, start labeling each node with {N, n-1, n-2, ..., 1}.


Shortest Path

  • A subpath of a shortest path, is itself a shortest path.
  • There is a tree of shortest paths, from a start vertex to all the other vertices.

Dijkstra's Algorithm

Dijkstra's calculates the shortest path from V to all other nodes, given:

  • Graph is connected
  • The graph is undirected
  • The edge weights are not negative

Start with the initial node in the 'cloud', with d(v) = 0.. Update any nodes connected to v with either the current d(v+1), or with d(v) + edge weight, whichever is smaller. Add the node with the smallest d() to the cloud, and compute all distances of adjacent edges outside the cloud.

This is a GREEDY algorithm! O(mlogn), IF we are using a heap-based Priority Queue to hold the elements, this allows easy selection of the next node.

Bellman-Ford Algorithm

  • Works with negative edges.
  • Must assume directed edges. (Otherwise get negative cycles)
  • Iteration I finds all shortest paths which contain i edges
  • O(nm) running time.

Bellman-Ford is Dynamic Programming

DAG

If we have a directed acyclic graph, it is much faster to calculate the topological ordering of said graph, and follow from top to bottom summing the distances. This can be performed in O(n+m) time!

Floyd

Floyd is designed to find all shortest paths from each node to every other node. This can be done in O(n^3) time. Also DP approach.


Minimum Spanning Trees

A Miniumum Spanning Tree is a tree of a weighted graph, with a minimum total edge weight.

Kruskal's Algorithm

Start with no edges and successfully add edges in order of increasing cost (making sure we don't insert edges that create cycles).

Prim-Jarnik's Algorithm

Start with any node and iteratively grow a tree from it. At each step add the node (and associated edge) that is the cheapest extension to the tree.

Reverse Deletion

Start with the full graph and delete edges in order of decreasing cost (making sure not to disconnect the graph).

Baruvka's Algorithm

Simmilar to Kruskal's Algorithm, except we grow many clouds at once.