Graphs

#programming #graphs #data-structures

A graph is a data structure that consists of a set of nodes (or vertices) and a set of edges that relate these nodes

Formally, a graph $G$ is represented as $G = (V, E)$ where

$V$ is a non-empty finite set of nodes or vertices
$E$ is a set of edges (represented as pairs of vertices)

Directed and undirected

A directed graph (digraph) is where each edge has a direction, ie it connects vertices $v_{i}$ and $v_{j}$ , in that order, and does not connect ${v_{j}, v_{i}}$
- Essentially means that each element in $E$ is ordered ( ${a, b} \neq {b, a}$ )
An undirected graph is represented by just a connection and no direction; bi-directional connections are assumed.
- Essentially means that each element in $E$ is unordered ( ${a, b} \equiv {b, a}$ )

Trees are a special case of graph; in trees, there are no cycles.

General Terminology

Adjacent nodes : Two nodes $u$ and $v$ are called adjacent if they are connected by an edge, $e$ Edge $e$ is called incident with $u$ and $v$ , and $u$ and $v$ are called endpoints of $e$ .
Degree of a vertex : Number of edges incident on it. A loop contributes twice to the degree.
Pendant vertex : Degree = 1
Isolated vertex : Degree = 0
Path : A sequence of vertices that connect two nodes
Complete graph : A graph in which each node is directly connected to each other node
Weighted graph : A graph in which each edge carries a "weight"

Important

No. of edges in a complete directed graph with $n$ vertices?

Since a complete graph has all connections, this means that two nodes have two edges between them, going both directions.
Number of edges $= 2 \times\ {#nC_} {2} = n\times(n-1)$

Important

No. of edges in a complete undirected graph with $n$ vertices?

$^{n} C_{2} = n \times (n - 1) / 2$

Graph Implementation

Adjacency Matrix

It is a $V \times V$ (where $V = N (V)$ ) matrix where if a connection exists between node $a$ and $b$ , then $M_{a b} = 1$ .
{cpp}matrix[vi][vj] = 1; if there is a connection, 0 otherwise.
Clearly, the matrix is going to symmetric if the graph is undirected.

Adjacency List

It is a collection of $V$ lists, where each list stores the nodes that the $i$ -th node is connected to.
Think of it more like a hashmap, where they key is the node, and the value is the list of nodes it is connected to.

Traversal

Breadth-first

Explore all vertices at current depth before moving on to next depth.
Visit neighbours of current node, then move on to next node.

Algorithm

Enqueue the starting node, and mark as visited
While Queue is not empty
- Dequeue node from start and mark as visited
- Visit all unvisited neighbours of current node, and then enqueue those neighbours
Repeat above step till queue is empty

Depth-first

Explore entire depth from vertice before looking at neighbours at same level

Algorithm

Push onto stack, the starting node, after marking as visited
While Stack is not empty
- Pop from stack
- Visit all unvisited neighbours of this node and then push to stack
Continue

Undirected graphs

Connectivity

An undirected graph is called "connected" if there exists a path between every pair of nodes in $V$ .
A subgraph, which is connected, is called a "connected component".
Articulation point (Cut Vertex) : The removal of the vertex produces more connected components then there initially was.
- Essentially means that this vertex is a choke point, and it's removal will break graph connectivity, resulting in (possibly) more fully connected graphs that lack connection between two graphs.
Cut edge : An edge whose removal produces more connected components then there initially was.

Directed graphs

Terminologies

Directed multi-graph : There can be multiple directed edges between a node $v_{i}$ and $v_{j}$ .
In-degree ( $\deg^{-} (u)$ ) : Number of edges for which $u$ is terminal
Out-degree ( $\deg^{+} (u)$ ) : Number of edges for which $u$ is initial

Connectivity

A directed graph is called "strongly connected" if there is a path from $a$ to $b$ and from $b$ to $a$ , whenever they are both present as vertices
A directed graph is called "weakly connected" if the underlying undirected representation of the graph is fully connected.

Transitive closure

In any graph $G$ , it's transitive close $G^{*}$ basically tells you if two nodes are connected by a path.
If a certain node is reachable from another node (maybe through some intermediate nodes), then $G^{*}$ has an edge between those two nodes.
Therefore, $G^{*}$ has

Same vertices as $V$
An edge ${u, v}$ iff there is a path between $u$ and $v$ in $G$

Transitive closure matrix : An extension to adjacency matrix.

In adj matrix, if edge exists, then {cpp}m[i][j] = 1;
in Transitive matrix, {cpp}T[i][j] = 1; if path exists between $i$ and $j$

This can be expanded for a digraph as follows

If there is a directed path between $u$ and $v$ in $G$ , then in $G^{*}$ there is a directed edge between $u$ and $v$ .

Algorithms to construct transitive closure

Unweighted Graph : Warshalls Algorithm
Weighted Graph : Floyd-Warshalls Algorithm

Relations

Relation between

V

and

E

A connected graph with no cycles obeys $E = V - 1$ ; This is the case of a tree
If a graph has $E \geq V$ , then it must contain atleast one cycle
If a connected graph has $E = V$ then it contains exactly one cycle and is called a unicyclic graph.