Graph Connectivity
Graph connectivity refers to the concept of whether a graph is connected or not. In a connected graph, there is a path between any two vertices.
To determine if a graph is connected, we can use a depth-first search (DFS) algorithm. The idea is to start from a vertex and explore as far as possible before backtracking.
Here's an example of a Java code that checks if a graph is connected:
SNIPPET
1// Check if the given graph is connected
2Graph graph = new Graph(5);
3graph.addEdge(0, 1);
4graph.addEdge(1, 2);
5graph.addEdge(2, 3);
6graph.addEdge(3, 4);
7boolean isConnected = graph.isConnected();
8System.out.println("Is the graph connected? " + isConnected);
9
10// Graph class
11class Graph {
12 private int V;
13 private List<List<Integer>> adjList;
14
15 public Graph(int vertices) {
16 V = vertices;
17 adjList = new ArrayList<>();
18 for (int i = 0; i < V; i++) {
19 adjList.add(new ArrayList<>());
20 }
21 }
22
23 public void addEdge(int src, int dest) {
24 adjList.get(src).add(dest);
25 adjList.get(dest).add(src);
26 }
27
28 public boolean isConnected() {
29 boolean[] visited = new boolean[V];
30 dfs(0, visited);
31 for (int i = 0; i < V; i++) {
32 if (!visited[i]) {
33 return false;
34 }
35 }
36 return true;
37 }
38
39 private void dfs(int vertex, boolean[] visited) {
40 visited[vertex] = true;
41 for (int neighbor : adjList.get(vertex)) {
42 if (!visited[neighbor]) {
43 dfs(neighbor, visited);
44 }
45 }
46 }
47}xxxxxxxxxx51
}class Main { public static void main(String[] args) { // replace with your Java logic here // Check if the given graph is connected Graph graph = new Graph(5); graph.addEdge(0, 1); graph.addEdge(1, 2); graph.addEdge(2, 3); graph.addEdge(3, 4); boolean isConnected = graph.isConnected(); System.out.println("Is the graph connected? " + isConnected); }}class Graph { private int V; private List<List<Integer>> adjList; public Graph(int vertices) { V = vertices; adjList = new ArrayList<>(); for (int i = 0; i < V; i++) { adjList.add(new ArrayList<>()); } } public void addEdge(int src, int dest) { adjList.get(src).add(dest); adjList.get(dest).add(src);OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment