🎯 Objective: Learn the fundamental concept of a Graph data structure and implement it in Java.
📝 Table of Contents
1️⃣ Introduction to Graphs
Graphs are one of the most versatile data structures used in computer science. A graph consists of nodes, often called vertices, and edges that connect pairs of vertices. Unlike arrays or linked lists, graphs can represent complex relationships between elements.
Why use Graphs?
- Model Network Topologies
- Solve Routing Problems
- Social Network Analysis
- Represent Hierarchies
- … and much more!
2️⃣ Types of Graphs
- Undirected Graph: Edges do not have a direction.
- Directed Graph: Edges have a direction.
- Weighted Graph: Edges have weights or costs associated with them.
3️⃣ Graph Representation
There are two popular ways to represent a graph:
- Adjacency Matrix: A 2D array where the cell
[i][j]
istrue
if there is an edge from vertexi
to vertexj
. - Adjacency List: An array of lists. The index represents the vertex, and each element in the list represents the vertices that the index vertex is connected to.
4️⃣ Java Implementation
Adjacency List Implementation:
import java.util.LinkedList;
public class Graph {
int vertices;
LinkedList<Integer>[] adjacencyList;
// Constructor
public Graph(int vertices) {
this.vertices = vertices;
adjacencyList = new LinkedList[vertices];
for (int i = 0; i < vertices; i++) {
adjacencyList[i] = new LinkedList<>();
}
}
// Add Edge
public void addEdge(int src, int dest) {
// For undirected graph
adjacencyList[src].add(dest);
adjacencyList[dest].add(src);
}
// Display the graph
public void displayGraph() {
for (int i = 0; i < vertices; i++) {
System.out.print("Vertex " + i + " is connected to: ");
for (int j = 0; j < adjacencyList[i].size(); j++) {
System.out.print(adjacencyList[i].get(j) + " ");
}
System.out.println();
}
}
public static void main(String args[]) {
Graph graph = new Graph(5);
graph.addEdge(0, 1);
graph.addEdge(0, 4);
graph.addEdge(1, 3);
graph.addEdge(3, 2);
graph.addEdge(2, 4);
graph.displayGraph();
}
}
Output:
Vertex 0 is connected to: 1 4
Vertex 1 is connected to: 0 3
Vertex 2 is connected to: 3 4
Vertex 3 is connected to: 1 2
Vertex 4 is connected to: 0 2
5️⃣ Summary
Graphs are incredibly flexible and widely used in various fields of computer science. In this post, we’ve covered the basics and provided a simple Java implementation. Happy learning!