Graphs

Graph and its representations

Graph is a data structure that consists of the following two components:

• A finite set of vertices (also called nodes).
• A finite set of edges - each edge is an ordered pair of the form (u, v). The pair is ordered for a directed graph (di-graph), where (u, v) denotes an edge from vertex u to vertex v. Edges can be weighted (store a cost/value) or unweighted.

Common types and terms:

• Undirected graph: edges have no direction. An edge {u, v} connects both vertices symmetrically.
• Directed graph (digraph): edges have direction from one vertex to another.
• Simple graph: no parallel edges and no self-loops.
• Multigraph: may have parallel edges (multiple edges between same pair of vertices) or self-loops.
• Degree: for undirected graphs, degree of a vertex is the number of incident edges. For directed graphs, use in-degree and out-degree.
• Connected (undirected): every vertex reachable from every other vertex. Strongly connected (directed): each vertex reachable from every other vertex via directed paths.

Graphs model many real-life systems such as road networks, telephone and circuit networks, and social networks (for example, in social sites each person is a vertex and relationships are edges). A node (vertex) can be represented as a structure containing fields such as id, name and other attributes.

Following is an example undirected graph with 5 vertices.

Common representations

The two most commonly used representations of a graph are:

• Adjacency Matrix
• Adjacency List

Other representations include the incidence matrix and incidence list. Choice of representation depends on the operations required and the graph density (sparse vs dense).

Adjacency Matrix

An adjacency matrix is a 2-D array of size V × V, where V is the number of vertices. Let the array be adj[][]. For an unweighted graph, adj[i][j] = 1 indicates an edge from vertex i to vertex j (and 0 otherwise). For a weighted graph, adj[i][j] = w indicates an edge of weight w.

An adjacency matrix for an undirected graph is always symmetric.

The adjacency matrix for the example graph is:

Pros

• Easy to implement and reason about.
• Edge presence query (is there an edge u→v?) is O(1).
• Removing or updating an edge is O(1).

Cons

• Space complexity is O(V²). For sparse graphs this wastes memory.
• Adding a vertex requires rebuilding/allocating a new V × V matrix (O(V²) work).

Adjacency List

An adjacency list uses an array (or vector) of lists. The array size equals the number of vertices; each entry stores the list of neighbours of the corresponding vertex. This representation is space-efficient for sparse graphs and can store weights in list nodes.

Adjacency list representation of the example graph is:

Example C implementation (adjacency list for an undirected graph):

// A C Program to demonstrate adjacency list representation of graphs #include <stdio.h> #include <stdlib.h> // A structure to represent an adjacency list node struct AdjListNode { int dest; struct AdjListNode* next; }; // A structure to represent an adjacency list struct AdjList { struct AdjListNode *head; // pointer to head node of list }; // A structure to represent a graph. A graph is an array of adjacency lists. // Size of array will be V (number of vertices in graph) struct Graph { int V; struct AdjList* array; }; // A utility function to create a new adjacency list node struct AdjListNode* newAdjListNode(int dest) { struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode)); newNode->dest = dest; newNode->next = NULL; return newNode; } // A utility function that creates a graph of V vertices struct Graph* createGraph(int V) { struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph)); graph->V = V; // Create an array of adjacency lists. Size of array will be V graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList)); // Initialize each adjacency list as empty by making head as NULL int i; for (i = 0; i < V; ++i) graph->array[i].head = NULL; return graph; } // Adds an edge to an undirected graph void addEdge(struct Graph* graph, int src, int dest) { // Add an edge from src to dest. A new node is added to the adjacency // list of src. The node is added at the begining struct AdjListNode* newNode = newAdjListNode(dest); newNode->next = graph->array[src].head; graph->array[src].head = newNode; // Since graph is undirected, add an edge from dest to src also newNode = newAdjListNode(src); newNode->next = graph->array[dest].head; graph->array[dest].head = newNode; } // A utility function to print the adjacency list representation of graph void printGraph(struct Graph* graph) { int v; for (v = 0; v < graph->V; ++v) { struct AdjListNode* pCrawl = graph->array[v].head; printf(" Adjacency list of vertex %d head ", v); while (pCrawl) { printf("-> %d", pCrawl->dest); pCrawl = pCrawl->next; } printf(" "); } } // Driver program to test above functions int main() { // create the graph given in above figure int V = 5; struct Graph* graph = createGraph(V); addEdge(graph, 0, 1); addEdge(graph, 0, 4); addEdge(graph, 1, 2); addEdge(graph, 1, 3); addEdge(graph, 1, 4); addEdge(graph, 2, 3); addEdge(graph, 3, 4); // print the adjacency list representation of the above graph printGraph(graph); return 0; } 

Output:

Adjacency list of vertex 0 head -> 4-> 1 Adjacency list of vertex 1 head -> 4-> 3-> 2-> 0 Adjacency list of vertex 2 head -> 3-> 1 Adjacency list of vertex 3 head -> 4-> 2-> 1 Adjacency list of vertex 4 head -> 3-> 1-> 0 

Pros

• Space complexity is O(|V| + |E|). For sparse graphs this is much smaller than O(V²).
• Adding a vertex is simpler (adjust array/vector size).

Cons

• Edge existence query (is there an edge u→v?) can take O(deg(u)) time, which in the worst case is O(V).

Breadth-First Traversal (BFS)

Breadth-First Search (BFS) traverses a graph level by level, visiting all neighbours of a vertex before moving to the next level. Unlike a tree, a graph may contain cycles; to avoid processing a node more than once we use a visited array (or set).

Example: starting BFS from vertex 2 in the following graph gives the traversal 2, 0, 3, 1.

Typical behaviour and notes:

• BFS explores vertices in order of increasing distance (number of edges) from the source.
• It produces a shortest-path tree from the source for an unweighted graph.
• If the graph is disconnected, a single BFS from one source visits only the reachable vertices; to traverse all vertices, run BFS from each unvisited vertex.

C++ implementation using adjacency lists and STL containers:

// Program to print BFS traversal from a given source vertex. BFS(int s) // traverses vertices reachable from s. #include<iostream> #include <list> using namespace std; // This class represents a directed graph using adjacency list representation class Graph { int V; // No. of vertices list<int> *adj; // Pointer to an array containing adjacency lists public: Graph(int V); // Constructor void addEdge(int v, int w); // function to add an edge to graph void BFS(int s); // prints BFS traversal from a given source s }; Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); // Add w to v's list. } void Graph::BFS(int s) { // Mark all the vertices as not visited bool *visited = new bool[V]; for(int i = 0; i < V; i++) visited[i] = false; // Create a queue for BFS list<int> queue; // Mark the current node as visited and enqueue it visited[s] = true; queue.push_back(s); // 'i' will be used to get all adjacent vertices of a vertex list<int>::iterator i; while(!queue.empty()) { // Dequeue a vertex from queue and print it s = queue.front(); cout << s << " "; queue.pop_front(); // Get all adjacent vertices of the dequeued vertex s // If an adjacent has not been visited, then mark it visited // and enqueue it for(i = adj[s].begin(); i != adj[s].end(); ++i) { if(!visited[*i]) { visited[*i] = true; queue.push_back(*i); } } } } // Driver program to test methods of graph class int main() { // Create a graph given in the above diagram Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); cout << "Following is Breadth First Traversal " << "(starting from vertex 2) "; g.BFS(2); return 0; } 

Output:

Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1 

Time complexity: O(V + E), where V is the number of vertices and E is the number of edges. Each vertex and each edge is processed at most once.

Depth-First Traversal (DFS)

Depth-First Search (DFS) explores as far as possible along each branch before backtracking. As with BFS, graphs may contain cycles so use a visited array to avoid infinite loops.

Example: starting DFS from vertex 2 in the following graph may yield traversal 2, 0, 1, 3.

Recursive C++ implementation using adjacency lists:

// C++ program to print DFS traversal from a given vertex in a given graph #include<iostream> #include<list> using namespace std; // Graph class represents a directed graph using adjacency list representation class Graph { int V; // No. of vertices list<int> *adj; // Pointer to an array containing adjacency lists void DFSUtil(int v, bool visited[]); // A function used by DFS public: Graph(int V); // Constructor void addEdge(int v, int w); // function to add an edge to graph void DFS(int v); // DFS traversal of the vertices reachable from v }; Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); // Add w to v's list. } void Graph::DFSUtil(int v, bool visited[]) { // Mark the current node as visited and print it visited[v] = true; cout << v << " "; // Recur for all the vertices adjacent to this vertex list<int>::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) if (!visited[*i]) DFSUtil(*i, visited); } // DFS traversal of the vertices reachable from v. // It uses recursive DFSUtil() void Graph::DFS(int v) { // Mark all the vertices as not visited bool *visited = new bool[V]; for (int i = 0; i < V; i++) visited[i] = false; // Call the recursive helper function to print DFS traversal DFSUtil(v, visited); } int main() { // Create a graph given in the above diagram Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); cout << "Following is Depth First Traversal (starting from vertex 2) "; g.DFS(2); return 0; } 

Output:

Following is Depth First Traversal (starting from vertex 2) 2 0 1 3 

To traverse a complete graph (including disconnected components), call DFS helper for every vertex that remains unvisited. Example implementation (complete traversal) is shown below:

// C++ program to print DFS traversal for a given given graph #include<iostream> #include <list> using namespace std; class Graph { int V; // No. of vertices list<int> *adj; // Pointer to an array containing adjacency lists void DFSUtil(int v, bool visited[]); // A function used by DFS public: Graph(int V); // Constructor void addEdge(int v, int w); // function to add an edge to graph void DFS(); // prints DFS traversal of the complete graph }; Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); // Add w to v's list. } void Graph::DFSUtil(int v, bool visited[]) { // Mark the current node as visited and print it visited[v] = true; cout << v << " "; // Recur for all the vertices adjacent to this vertex list<int>::iterator i; for(i = adj[v].begin(); i != adj[v].end(); ++i) if(!visited[*i]) DFSUtil(*i, visited); } // The function to do DFS traversal. It uses recursive DFSUtil() void Graph::DFS() { // Mark all the vertices as not visited bool *visited = new bool[V]; for (int i = 0; i < V; i++) visited[i] = false; // Call the recursive helper function to print DFS traversal // starting from all vertices one by one for (int i = 0; i < V; i++) if (visited[i] == false) DFSUtil(i, visited); } int main() { // Create a graph given in the above diagram Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); cout << "Following is Depth First Traversal "; g.DFS(); return 0; } 

Output:

Following is Depth First Traversal 0 1 2 3 

Time complexity: O(V + E). Each vertex and each edge is visited at most once in the traversal.

Note on iterative DFS: DFS can be implemented iteratively using an explicit stack instead of recursion; this is useful where recursion depth is a concern.

Applications of Depth-First Search (DFS)

DFS is a versatile technique used as a building block for many graph algorithms. Common applications include:

• Cycle detection: In a directed graph, DFS detects a cycle if a back edge to an ancestor is found. In undirected graphs, DFS also detects cycles by finding a visited vertex that is not the parent.
• Path finding: DFS can be specialised to find a path between two vertices; maintain a stack or parent pointers and stop when the destination is reached.
• Topological sorting: DFS is used to produce a topological order of vertices in a directed acyclic graph (DAG); this is useful in job scheduling, instruction ordering, spreadsheet recomputation, makefile dependency resolution and linkers.
• Strongly connected components (SCC): Algorithms such as Kosaraju's and Tarjan's use DFS to find SCCs in directed graphs.
• Solving puzzles and mazes: DFS explores deep paths and can be adapted to find all solutions by backtracking; for single-solution mazes it is often sufficient.

Applications of Breadth-First Search (BFS)

BFS is also fundamental and has many applications:

• Shortest path in unweighted graphs: BFS from a source gives minimum number of edges required to reach every reachable vertex and produces a shortest-path tree.
• Peer-to-peer networks: Protocols such as BitTorrent use breadth-first discovery to find neighbours.
• Web crawlers: Crawlers often use breadth-first strategies to limit depth and control the order of pages indexed.
• Social networks: To find all people within distance k from a person, run BFS up to level k.
• GPS and navigation: BFS can be used to explore neighbouring locations when graph is unweighted or when edges represent uniform cost.
• Broadcasting in networks: A broadcast can follow BFS order to reach all nodes with minimum hops.
• Garbage collection: Copying collectors such as Cheney's algorithm use breadth-first style scanning for good locality.
• Cycle detection in undirected graphs: Either BFS or DFS can be used. For directed graphs, algorithms based on DFS or Kahn's algorithm (in-degree reduction) can detect cycles.
• Maximum flow algorithms: In the Ford-Fulkerson approach, using BFS to find augmenting paths yields the Edmonds-Karp algorithm and gives better worst-case bounds (O(VE²)).
• Bipartiteness test: Colouring levels during BFS can be used to test whether an undirected graph is bipartite.
• Finding connected components: BFS finds all vertices in a component when started from any vertex in that component.

Complexities and representation trade-offs

• Adjacency matrix: space O(V²), edge query O(1), iterate neighbours O(V) per vertex.
• Adjacency list: space O(V + E), iterate neighbours O(deg(v)), edge query O(deg(v)) in worst case O(V).
• BFS and DFS: both run in O(V + E) time when using adjacency lists; with adjacency matrix the running time may be O(V²).

Summary

Graphs model relational data and have multiple representations. Choose adjacency lists for sparse graphs and adjacency matrices for dense graphs or if you need O(1) edge queries. BFS finds shortest paths in unweighted graphs and explores level by level; DFS explores deep paths and is widely used for cycle detection, topological sort and strongly connected components. Both BFS and DFS run in linear time in the size of the graph (O(V + E)) when adjacency lists are used.