Codecrown
Graph Data Structure: Representation, BFS, DFS, and Applications
A Graph is a non-linear data structure used to represent relationships or connections between objects. A graph consists of vertices, also called nodes, and edges that connect pairs of vertices.
Graphs are more flexible than linear data structures because a vertex can be connected to multiple other vertices. They are widely used to model social networks, computer networks, transportation systems, web pages, dependencies, and many other real-world relationships.
Graph algorithms are fundamental in computer science. Common operations include graph traversal, shortest-path computation, cycle detection, connectivity analysis, and finding minimum spanning trees.
1. Basic Components of a Graph
A graph is commonly represented using two fundamental components: vertices and edges.
- Vertex: Represents an individual object or entity in the graph.
- Edge: Represents a connection or relationship between two vertices.
- Degree: Represents the number of edges connected to a vertex in an undirected graph.
- Weight: An optional value assigned to an edge, such as distance, cost, or time.
- Path: A sequence of vertices connected by edges.
- Cycle: A path that starts and ends at the same vertex.
Vertices: A, B, C, D Edges: A — B A — C B — D C — D
2. Types of Graphs
Undirected Graph
In an undirected graph, edges do not have a direction. If A is connected to B, the connection can be traversed from A to B and from B to A.
A — B | | C — D
Directed Graph
In a directed graph, every edge has a direction. An edge from A to B does not necessarily mean that B can directly reach A.
A → B ↓ ↓ C → D
Weighted Graph
A weighted graph assigns a value or cost to each edge. Weights can represent distance, travel time, network cost, or other measurable quantities.
A —5— B | | 2 7 | | C —3— D
Unweighted Graph
In an unweighted graph, edges are treated equally and do not have associated costs.
3. Graph Representation
Graphs can be stored in several ways. The two most common representations are the adjacency matrix and adjacency list.
Adjacency Matrix
An adjacency matrix uses a two-dimensional array where matrix[i][j] indicates whether an edge exists between vertex i and vertex j. For weighted graphs, the matrix can store the edge weight instead.
Graph:
A — B
| |
C — D
Adjacency Matrix:
A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 1
D 0 1 1 0An adjacency matrix requires O(V²) space, where V is the number of vertices. It provides O(1) edge-existence lookup but can consume significant memory for sparse graphs.
Adjacency List
An adjacency list stores a collection of neighboring vertices for every vertex.
A → B, C B → A, D C → A, D D → B, C
An adjacency list typically requires O(V + E) space for an unweighted graph, making it a common choice for sparse graphs.
4. Graph Traversal
Graph traversal means visiting vertices systematically. The two fundamental traversal techniques are Breadth-First Search (BFS) and Depth-First Search (DFS).
Breadth-First Search (BFS)
BFS explores a graph level by level. It starts from a source vertex, visits its immediate neighbors, then visits the neighbors of those vertices.
BFS typically uses a Queue to keep track of vertices that need to be processed.
- Start from the selected source vertex.
- Mark the source as visited and add it to a queue.
- Remove a vertex from the front of the queue.
- Visit all of its unvisited neighbors and add them to the queue.
- Repeat until the queue becomes empty.
Depth-First Search (DFS)
DFS explores as deeply as possible along one path before backtracking. It can be implemented using recursion or an explicit Stack.
- Start from the selected source vertex.
- Mark the vertex as visited.
- Visit an unvisited neighboring vertex.
- Continue recursively or with a stack until no unvisited neighbor remains.
- Backtrack and continue exploring other branches.
5. BFS Implementation in Java
The following example uses an adjacency list and a Queue to perform Breadth-First Search.
import java.util.*;
public class GraphBFS {
static void bfs(List<List<Integer>> graph, int start) {
boolean[] visited = new boolean[graph.size()];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int current = queue.poll();
System.out.print(current + " ");
for (int neighbor : graph.get(current)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}
}
public static void main(String[] args) {
int vertices = 5;
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
graph.add(new ArrayList<>());
}
graph.get(0).add(1);
graph.get(0).add(2);
graph.get(1).add(3);
graph.get(2).add(4);
System.out.print("BFS: ");
bfs(graph, 0);
}
}For a graph represented by an adjacency list, BFS runs in O(V + E) time because each vertex and edge is processed at most a constant number of times.
6. DFS Implementation in Java
DFS can be implemented recursively by following one path as deeply as possible before returning to explore another path.
import java.util.*;
public class GraphDFS {
static void dfs(
List<List<Integer>> graph,
int current,
boolean[] visited) {
visited[current] = true;
System.out.print(current + " ");
for (int neighbor : graph.get(current)) {
if (!visited[neighbor]) {
dfs(graph, neighbor, visited);
}
}
}
public static void main(String[] args) {
int vertices = 5;
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
graph.add(new ArrayList<>());
}
graph.get(0).add(1);
graph.get(0).add(2);
graph.get(1).add(3);
graph.get(2).add(4);
boolean[] visited = new boolean[vertices];
System.out.print("DFS: ");
dfs(graph, 0, visited);
}
}DFS also runs in O(V + E) time when an adjacency list is used.
7. BFS vs DFS
Both BFS and DFS can traverse a graph, but they explore vertices in different ways.
Feature BFS DFS Traversal Level by level Depth first Main data structure Queue Stack / Recursion Shortest path Yes, unweighted Not generally Memory pattern Often wider Often deeper Time complexity O(V + E) O(V + E)
For an unweighted graph, BFS can find the shortest path in terms of the number of edges from a source vertex. DFS does not generally provide this guarantee.
8. Graph Representation Complexity
Representation Space Edge Lookup Adjacency Matrix O(V²) O(1) Adjacency List O(V + E) O(degree(V))
The appropriate representation depends on the graph. Adjacency matrices are useful when the graph is dense or constant-time edge lookup is important. Adjacency lists are generally preferred for sparse graphs and traversal algorithms.
9. Important Graph Algorithms
- BFS: Traverses a graph level by level and can find shortest paths in unweighted graphs.
- DFS: Explores graph branches deeply and is useful for connectivity and cycle-related problems.
- Dijkstra's Algorithm: Finds shortest paths from a source in graphs with non-negative edge weights.
- Bellman-Ford Algorithm: Finds shortest paths while supporting negative edge weights.
- Floyd-Warshall Algorithm: Computes shortest paths between all pairs of vertices.
- Kruskal's Algorithm: Finds a Minimum Spanning Tree using edge sorting and Disjoint Set Union.
- Prim's Algorithm: Builds a Minimum Spanning Tree by repeatedly selecting the cheapest connecting edge.
- Topological Sort: Produces an ordering of vertices in a Directed Acyclic Graph.
10. Real-World Applications of Graphs
- Social Networks: Users can be represented as vertices and relationships as edges.
- Navigation Systems: Locations can be represented as vertices and roads as weighted edges.
- Computer Networks: Devices and communication links can be modeled as graph components.
- Web Crawling: Web pages can be represented as vertices connected by hyperlinks.
- Recommendation Systems: Relationships between users, products, movies, or other entities can be modeled using graphs.
- Dependency Management: Software packages and task dependencies can be represented using directed graphs.
- Transportation Networks: Cities, stations, and routes can be modeled as weighted or unweighted graphs.
11. Common Mistakes
- Forgetting to maintain a visited array or set, which can cause repeated processing or infinite traversal in cyclic graphs.
- Confusing directed and undirected edges when building the graph.
- Assuming DFS always finds the shortest path.
- Using BFS for weighted shortest-path problems without considering edge weights.
- Choosing an adjacency matrix for a very large sparse graph and unnecessarily consuming O(V²) memory.
- Forgetting that disconnected graphs may require starting BFS or DFS from multiple unvisited vertices.
- Using recursive DFS on extremely deep graphs without considering stack-depth limitations.
Conclusion
A Graph is a powerful non-linear data structure for representing relationships between objects. It consists of vertices and edges and can model directed, undirected, weighted, and unweighted relationships.
Graphs can be represented using adjacency matrices or adjacency lists. BFS and DFS are the two fundamental traversal techniques, while algorithms such as Dijkstra, Bellman-Ford, Kruskal, Prim, and Topological Sort solve more specialized graph problems.
Understanding graph representation and traversal provides an essential foundation for solving advanced problems involving networks, paths, dependencies, connectivity, and optimization.