Mark As Completed Discussion

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.

TEXT/X-JAVA
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.

TEXT/X-JAVA
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.

Are you sure you're getting this? 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:

TEXT/X-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:

TEXT/X-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:

TEXT/X-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}
JAVA
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

Try this exercise. 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

JAVA
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

Let's test your knowledge. 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!