Welcome to the Graph Problems section of the Coding Problems lesson! In this section, we will explore various problems related to graphs.
Graphs are a fundamental data structure in computer science and are used to represent relationships between objects. They consist of nodes (also called vertices) and edges, where each edge connects two nodes. Graphs can be used to model a wide range of real-world networks, such as social networks, transportation networks, and computer networks.
As an engineer with intermediate knowledge of Java and Python, you have likely encountered graph problems during your coding journey. You may have already used graphs to solve problems like finding the shortest path between two nodes, checking if a graph is connected, or finding cycles in a graph.
Let's take a look at an example problem in Java to check if a graph is connected:
1import java.util.*;
2
3public class GraphProblems {
4
5 public static boolean isConnectedGraph(int[][] graph) {
6 int n = graph.length;
7 boolean[] visited = new boolean[n];
8 dfs(graph, 0, visited);
9 for (boolean v : visited) {
10 if (!v) {
11 return false;
12 }
13 }
14 return true;
15 }
16
17 private static void dfs(int[][] graph, int node, boolean[] visited) {
18 visited[node] = true;
19 for (int neighbor : graph[node]) {
20 if (!visited[neighbor]) {
21 dfs(graph, neighbor, visited);
22 }
23 }
24 }
25
26 public static void main(String[] args) {
27 int[][] graph = {
28 {1, 2},
29 {0, 2},
30 {0, 1, 3},
31 {2}
32 };
33
34 System.out.println("Is the graph connected? " + isConnectedGraph(graph));
35 }
36}xxxxxxxxxx}import java.util.*;public class GraphProblems { // Check if a graph is connected or not public static boolean isConnectedGraph(int[][] graph) { int n = graph.length; boolean[] visited = new boolean[n]; dfs(graph, 0, visited); for (boolean v : visited) { if (!v) { return false; } } return true; } private static void dfs(int[][] graph, int node, boolean[] visited) { visited[node] = true; for (int neighbor : graph[node]) { if (!visited[neighbor]) { dfs(graph, neighbor, visited); } } } // Find the shortest path between two nodes in a graph public static List<Integer> shortestPath(int[][] graph, int start, int end) { int n = graph.length;