Graphs

Types of Graphs

Undirected Graph

An undirected graph is a graph in which edges have no orientation. The edge (u, v) is identical to the edge (v, u).

Directed Graph

A directed graph or digraph is a graph in which edges have orientations. For example, the edge (u, v) is the edge
from node u to node v.

Weighted Graphs

A weighted graph is a graph whose edges contain a certain weight to represent an arbitrary value such as cost, distance, quantity, etc. Such edges are usually denoted as a triplet (u, v, w).

Special Graphs

Trees

A tree is an undirected graph with no cycles. Equivalently, it is a connected graph with N nodes and N-1 edges

Directed Acyclic Graphs (DAGs)

DAGs are directed graphs with no cycles.

Bipartite Graph

A bipartite graph is one whose vertices can be split into two independent groups U, V such that every edge connects betweens U and V.

Complete Graphs

A complete graph is one where there is a unique edge between every pair of nodes.
A complete graph with n vertices is denoted as the graph Kn.

Representing Graphs

Adjacency Matrix

A adjacency matrix m is a matrix where the cell m[i][j] represents the edge weight of going from node i to node j.

Adjacency List

An adjacency list is a way to represent a graph as a map from nodes to lists of edges.

Edge List

An edge list is a way to represent a graph simply as an unordered list of edges. Assume the notation for any triplet (u,v,w) means: “the cost from node u to node v is w”.

Algorithms

Depth First Search (DFS)

The Depth First Search (DFS) is the most fundamental search algorithm used to explore nodes and edges of a graph.
Complexity: O(V + E)

Find Number of components with DFS

Topological order with DFS