Graphs are one of the most powerful data structures in computer science, widely used in applications. A Graph is a non-linear data structure consisting of nodes (also called vertices) and edges that connect pairs of nodes. Graphs are used to represent networks like social connections, transportation systems, or web page links. A graph consists of:
- Vertices (Nodes): Represented as
V, these are the points in a graph. - Edges: Represented as
E, these are the connections between nodes.
A graph is typically denoted as G(V, E), where V is the set of vertices and E is the set of edges connecting them.
Types of Graphs
- Directed Graph (Digraph): Edges have a direction, meaning the connection goes one way. Example: Twitter’s follower system.
- Undirected Graph: Edges have no direction, meaning the connection is bidirectional. Example: Facebook’s friend system.
- Weighted Graph: Each edge has a weight or cost. Example: Road networks with distances.
- Unweighted Graph: Edges do not have any weight.
- Cyclic Graph: A graph that contains at least one cycle.
- Acyclic Graph: A graph without any cycles.
Declaration & Initialization
Using Adjacency List (with HashMap & List)
|
1 2 3 4 5 6 7 8 9 |
import java.util.*; class Graph { Map<Integer, List<Integer>> adjList = new HashMap<>(); public void addVertex(int v) { adjList.putIfAbsent(v, new ArrayList<>()); } } |
Using Adjacency Matrix
|
1 2 3 4 5 6 7 |
class GraphMatrix { int[][] adjMatrix; GraphMatrix(int numVertices) { adjMatrix = new int[numVertices][numVertices]; } } |
Basic Operations
Insertion (Add Vertex / Edge):
|
1 2 3 4 |
public void addEdge(int src, int dest) { adjList.get(src).add(dest); // For undirected graph: adjList.get(dest).add(src); } |
Deletion (Remove Edge):
|
1 2 3 |
public void removeEdge(int src, int dest) { adjList.get(src).remove(Integer.valueOf(dest)); } |
Traversal – Breadth First Search (BFS Example):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
public void bfs(int start) { Queue<Integer> queue = new LinkedList<>(); Set<Integer> visited = new HashSet<>(); queue.add(start); visited.add(start); while (!queue.isEmpty()) { int node = queue.poll(); System.out.print(node + " "); for (int neighbor : adjList.get(node)) { if (!visited.contains(neighbor)) { queue.add(neighbor); visited.add(neighbor); } } } } |
Other Traversals: Depth-First Search (DFS), Dijkstra’s algorithm (for weighted graphs), etc.
Advantages & Disadvantages
| Advantages | Disadvantages |
|---|---|
| Efficient for representing complex relationships. | Can consume more memory (especially adjacency matrix). |
| Flexible – supports both directed & undirected relationships. | Graph algorithms may be harder to implement for beginners. |
| Real-world modeling: social networks, navigation, etc. | Performance can vary based on graph size and type. |
Real-world examples
- Social networks: Users connected as friends or followers (Facebook, Twitter).
- Google Maps & GPS: Cities and roads modeled as weighted graphs for shortest path calculation.
- Web crawling: Web pages are nodes, hyperlinks are edges.
- Airline routes: Airports as vertices and flights as edges with costs.
- Recommendation systems: Product/user relationships in e-commerce.
