Graph Algorithms

Graph Theory is a study of graphs, a mathematical structure modeling the associations between objects. It is vital for many computer science problems and worth attention for not only theoretical studies but also practical application development.

This chapter discusses fundamental graph structures, typical graph problems and correlated algorithm analysis. Specifically, graph searching primitives such as DFS and BFS are the most important techniques throughout the graph algorithms.

Graph Definitions

Generally, there are two kinds of graphs: directed graph and undirected graph. Both of them involve a relationship between Vertex V and Edge E.

Directed Graph

Given a graph G = (V, E), wherein the V is a set of vertices of G and E is a set of edges going in and out from vertices with directions, connected them together. Specifically, given vertices {1, 2, 3, 4, 5, 6}, a graph can be built like below:

Figure 1. Directed Graph

Note: there are cycles (even self cycles, a vertex points to itself) in directed graphs and to be noted that problems like topological sort could not have solutions if cycles present, the directed graph with no cycles is called DAG (directed acyclic graph).

Undirected Graph

Unlike directed graph, undirected graph only has edges with no directions between connected vertices. Since the relations among vertices have no ordering, there exists no self cycles. Similarly,

Figure 2. Undirected Graph

Degrees

In an undirected graph, the degree of a vertex means the number of edges associated with that vertex. For instance, the degree of vertex 3 in the above graph is 3;

While in the directed graph, the degree of a vertex is the summation of its in-degree and out-degree. Such in-degree means the number of edges pointing towards the vertex and out-degree means the number of edges pointing out of the vertex.

Note: the vertex with zero degree means it is a lonely island, disconnected from any other vertices in the graph.

Connectivity

If for any given vertices in an undirected graph, there exists paths reachable from all other vertices, then the graph is connected. Specifically, if an undirected graph G = (V, E) is connected, the number of edges is larger than or equal to number of vertices minus 1: |E| ≥ |V| - 1.

There are only definitions of strongly connected and weakly connected in a directed graph. In a strongly connected directed graph G = (V, E), for any two distinct vertices x, y within V, there exists paths from x to y and from y to x;

Substituting all directional edges of a directed graph with undirected ones could obtain a base graph of the original graph. If such a base graph is connected, then the original directed graph is weakly connected.

Graph Representations

Two vertices sharing a same edge are adjacent in a graph. To define such relationships among vertices, two practical uses of data structures are introduced: adjacency matrix and adjacency list.

Adjacency Matrix

This matrix (e.g. adj[][]) is a 2D array with size |V| ✗ |V|; In an undirected graph, if vertex a and vertex b are connected, then adj[a][b] = 1 and adj[b][a] = 1; if there are no edges between say vertex e and vertex c, then adj[e][c] = 0, adj[c][e] = 0;

For a directed graph, the matrix cell value depends on the existance of directional edges; If vertex a has an edge going outward to vertex b while vertex b has no edges going inward to vertex a, then adj[a][b] = 1 but adj[b][a] = 0

Figure 3. Adjacency Matrices of a Directed Graph and an Undirected Graph

Adjacency matrix is practical when the graph is dense (at least one edge going in between two vertices) and finding the existence of edges is immediate (LOOKUP costs Ο(1)). It is less so if the graph is sparse (the graph topology structure approaches a forest rather than a graph).

Adjacency List

Adjacency list is an array of linkedlist in design and it costs only Ο(|V| + |E|) compared to adjacency matrix. In addition, the array can be dynamic which means adding vertices to a graph is easier than a static structure like adjacency matrix.

Figure 4. Adjacency List of a Directed Graph

Though it normally costs Ο(|E|) time to LOOKUP edge associations, it is a preferable choice than adjacency matrix in a massive-scale data network such as WEB.

Table of Contents

• Breadth-First Search - a searching primitive prototype for many important algorithms like [Minimum Spanning Tree] and [Dijkstra Shortest Path].
• Depth-First Search - in contrast to BFS, DFS provides a simple recursive implementation.
• Shortest Path Algorithms - a prevalent type of graph algorithm in practice, e.g. find a shortest path from location A to location B in map.
• Minimum Spanning Tree - a technique to transform graphs to trees
• Graph Minimum-Cut - split the graph into different groups for applications like community finding.
• Topological Sort - sort a DAG graph with respect to its topological relations.