Graphs can be represented in various ways in code, depending on the requirements and use cases. Each representation has its own advantages and disadvantages, and understanding them is essential for efficiently working with graphs.
One commonly used representation of a graph is the adjacency matrix. In this representation, a matrix of size V x V is used, where V is the number of vertices in the graph. The value at matrix position (i, j) represents the weight of the edge between vertices i and j. If there is no edge between the vertices, the value at that position is usually set to infinity or a special value to indicate the absence of an edge.
1// Adjacency Matrix representation of a graph
2
3class Main {
4 public static void main(String[] args) {
5 int V = 5; // Number of vertices
6 int[][] adjacencyMatrix = new int[V][V];
7
8 // Add edges
9 adjacencyMatrix[0][1] = 1;
10 adjacencyMatrix[1][2] = 1;
11 adjacencyMatrix[2][3] = 1;
12 adjacencyMatrix[3][4] = 1;
13 adjacencyMatrix[4][0] = 1;
14
15 // Print adjacency matrix
16 for (int i = 0; i < V; i++) {
17 for (int j = 0; j < V; j++) {
18 System.out.print(adjacencyMatrix[i][j] + " ");
19 }
20 System.out.println();
21 }
22 }
23}Another common representation is the adjacency list. In this representation, each vertex in the graph is associated with a list of its adjacent vertices. This representation is more memory-efficient when the graph has a large number of vertices but relatively fewer edges.
1// Adjacency List representation of a graph
2
3class Graph {
4 int V;
5 ArrayList<ArrayList<Integer>> adjacencyList;
6
7 public Graph(int v) {
8 V = v;
9 adjacencyList = new ArrayList<>(V);
10
11 for (int i = 0; i < V; i++) {
12 adjacencyList.add(new ArrayList<>());
13 }
14 }
15
16 public void addEdge(int src, int dest) {
17 adjacencyList.get(src).add(dest);
18 adjacencyList.get(dest).add(src); // Uncomment this line for undirected graph
19 }
20
21 public void printGraph() {
22 for (int i = 0; i < V; i++) {
23 System.out.print(i + " -> ");
24 for (int j = 0; j < adjacencyList.get(i).size(); j++) {
25 System.out.print(adjacencyList.get(i).get(j) + " ");
26 }
27 System.out.println();
28 }
29 }
30}
31
32// Usage
33
34class Main {
35 public static void main(String[] args) {
36 int V = 5; // Number of vertices
37 Graph graph = new Graph(V);
38
39 // Add edges
40 graph.addEdge(0, 1);
41 graph.addEdge(1, 2);
42 graph.addEdge(2, 3);
43 graph.addEdge(3, 4);
44 graph.addEdge(4, 0);
45
46 // Print adjacency list
47 graph.printGraph();
48 }
49}These are just a few examples of how graphs can be represented in code. Depending on the specific use case, other representations such as edge list, incidence matrix, or adjacency set might be more suitable and efficient.
Build your intuition. Click the correct answer from the options.
Which representation of a graph is more memory-efficient when the graph has a large number of vertices but relatively fewer edges?
Click the option that best answers the question.
- Adjacency Matrix
- Adjacency List
- Edge List
- Incidence Matrix
Graph traversal algorithms are used to explore or visit all the vertices of a graph. They are essential for understanding the structure and connectivity of a graph. Two commonly used graph traversal algorithms are depth-first search (DFS) and breadth-first search (BFS).
Depth-First Search (DFS):
In DFS, we start at a given vertex (usually called the source vertex) and explore as far as possible along each branch before backtracking. This means that we go depth-first, exploring vertices in the order they are encountered until we reach a dead end, and then backtrack to the previous vertex and explore another branch.
DFS can be implemented using either recursion or an explicit stack. Here is a recursive implementation of DFS in Java:
1public class DFS {
2 private boolean[] visited;
3 private Graph graph;
4
5 public DFS(Graph g) {
6 graph = g;
7 visited = new boolean[graph.getVertices()];
8 }
9
10 public void traverse(int source) {
11 visited[source] = true;
12 System.out.print(source + " ");
13
14 for (int neighbor : graph.getNeighbors(source)) {
15 if (!visited[neighbor]) {
16 traverse(neighbor);
17 }
18 }
19 }
20
21 public static void main(String[] args) {
22 int V = 6; // Number of vertices
23 Graph graph = new Graph(V);
24
25 // Add edges
26 graph.addEdge(0, 1);
27 graph.addEdge(0, 2);
28 graph.addEdge(1, 3);
29 graph.addEdge(2, 4);
30 graph.addEdge(3, 5);
31
32 DFS dfs = new DFS(graph);
33 dfs.traverse(0);
34 }
35}Breadth-First Search (BFS):
In BFS, we explore all the vertices at the current level before moving to the next level. This means that we visit all the neighbors of a vertex before visiting the neighbors' neighbors.
BFS can be implemented using a queue data structure. Here is an implementation of BFS in Java:
1import java.util.LinkedList;
2import java.util.Queue;
3
4public class BFS {
5 private boolean[] visited;
6 private Graph graph;
7
8 public BFS(Graph g) {
9 graph = g;
10 visited = new boolean[graph.getVertices()];
11 }
12
13 public void traverse(int source) {
14 Queue<Integer> queue = new LinkedList<>();
15 queue.offer(source);
16 visited[source] = true;
17
18 while (!queue.isEmpty()) {
19 int vertex = queue.poll();
20 System.out.print(vertex + " ");
21
22 for (int neighbor : graph.getNeighbors(vertex)) {
23 if (!visited[neighbor]) {
24 queue.offer(neighbor);
25 visited[neighbor] = true;
26 }
27 }
28 }
29 }
30
31 public static void main(String[] args) {
32 int V = 6; // Number of vertices
33 Graph graph = new Graph(V);
34
35 // Add edges
36 graph.addEdge(0, 1);
37 graph.addEdge(0, 2);
38 graph.addEdge(1, 3);
39 graph.addEdge(2, 4);
40 graph.addEdge(3, 5);
41
42 BFS bfs = new BFS(graph);
43 bfs.traverse(0);
44 }
45}Let's test your knowledge. Is this statement true or false?
Breadth-first search is a graph traversal algorithm that visits all of the direct neighbors of a node before visiting any of its descendants.
Press true if you believe the statement is correct, or false otherwise.
Dijkstra's algorithm is a well-known algorithm used to find the shortest path between two vertices in a weighted graph. It guarantees the shortest path from a source vertex to all other vertices. This algorithm is widely used in various applications, such as GPS navigation systems, network routing protocols, and airline travel planning.
The basic idea behind Dijkstra's algorithm is to continuously update the shortest path distances from the source vertex to all other vertices in the graph. It maintains a priority queue of vertices to explore, sorted by their current shortest distance from the source. At each step, it selects the vertex with the smallest current distance and relaxes the edges connected to it.
Let's take a look at an implementation of Dijkstra's algorithm in Java:
1class Graph {
2 private int V;
3 private int[][] graph;
4
5 public Graph(int V) {
6 this.V = V;
7 graph = new int[V][V];
8 }
9
10 public void addEdge(int src, int dest, int weight) {
11 graph[src][dest] = weight;
12 }
13
14 public void dijkstra(int source) {
15 // Initialize distance array
16 int[] dist = new int[V];
17 Arrays.fill(dist, Integer.MAX_VALUE);
18 dist[source] = 0;
19
20 // Initialize visited array
21 boolean[] visited = new boolean[V];
22
23 // Initialize priority queue
24 PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> dist[a] - dist[b]);
25 pq.offer(source);
26
27 while (!pq.isEmpty()) {
28 int vertex = pq.poll();
29 visited[vertex] = true;
30
31 // Relax edges connected to the current vertex
32 for (int neighbor = 0; neighbor < V; neighbor++) {
33 int weight = graph[vertex][neighbor];
34
35 if (weight > 0 && !visited[neighbor]) {
36 int newDistance = dist[vertex] + weight;
37
38 if (newDistance < dist[neighbor]) {
39 // Update shortest distance to neighbor
40 dist[neighbor] = newDistance;
41
42 // Add neighbor to priority queue
43 pq.offer(neighbor);
44 }
45 }
46 }
47 }
48
49 // Print the shortest distances from the source vertex
50 System.out.println(Arrays.toString(dist));
51 }
52
53 public static void main(String[] args) {
54 int V = 5; // Number of vertices
55 Graph graph = new Graph(V);
56
57 // Add edges
58 graph.addEdge(0, 1, 4);
59 graph.addEdge(0, 2, 1);
60 graph.addEdge(1, 3, 1);
61 graph.addEdge(2, 1, 2);
62 graph.addEdge(2, 3, 5);
63 graph.addEdge(3, 4, 3);
64
65 graph.dijkstra(0);
66 }
67}xxxxxxxxxx}import java.util.Arrays;import java.util.PriorityQueue;class Graph { private int V; private int[][] graph; public Graph(int V) { this.V = V; graph = new int[V][V]; } public void addEdge(int src, int dest, int weight) { graph[src][dest] = weight; } public void dijkstra(int source) { int[] dist = new int[V]; Arrays.fill(dist, Integer.MAX_VALUE); boolean[] visited = new boolean[V]; dist[source] = 0; PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> dist[a] - dist[b]); pq.offer(source); while (!pq.isEmpty()) { int vertex = pq.poll();Let's test your knowledge. Click the correct answer from the options.
Which data structure is commonly used in the implementation of Dijkstra's algorithm?
Click the option that best answers the question.
- Stack
- Queue
- Heap
- Linked List
REPLACE_WITH_YOUR_CONTENT
xxxxxxxxxxREPLACE_WITH_YOUR_JAVA_CODETry this exercise. Click the correct answer from the options.
Which algorithm is used to find the minimum spanning tree of a graph?
Click the option that best answers the question.
- Dijkstra's algorithm
- Depth-first search
- Prim's algorithm
- Breadth-first search
Generating complete for this lesson!
