Home > Data structure and algorithms > Data structure and algorithms > Graphs

Graphs are one of the most common data structures in computer science. Especially with today's machine learning and artificial intelligence trends, understanding them is crucial. A shocking amount of real-life things can be modeled with graphs. Humans think in associations, so it's obvious why connecting things in this way is practical.

But graphs can be a little tricky to understand! This is because they need a paradigm shift to fully grok. You see, graphs are a non-linear data structure, meaning there is no sequential order intrinsic to them.

Let's explore what this means.

xxxxxxxxxx
 
class Main {
  public static void main(String[] args) {
    // replace with your Java logic here
    for(int i = 1; i <= 100; i++) {
      if(i % 3 == 0 && i % 5 == 0) {
          System.out.println("FizzBuzz");
      } else if(i % 3 == 0) {
          System.out.println("Fizz");
      } else if(i % 5 == 0) {
          System.out.println("Buzz");
      } else {
          System.out.println(i);
      }
    }    
  }
}

Are you sure you're getting this? Click the correct answer from the options.

Which of the following statements is true about graphs?

A) Graphs are linear data structures B) Graphs can be represented as arrays C) Graphs have an intrinsic sequential order D) Graphs are non-linear data structures

Click the option that best answers the question.

To represent a graph in code, there are several ways to do it. One common way is to use an Adjacency List, which is an array of lists. Each element in the array represents a vertex in the graph, and the list at that index contains all the adjacent vertices. This representation works well when the graph is sparse, meaning it has fewer edges compared to the maximum number of edges.

For example, let's say we have a graph with 5 vertices and the following edges:

Vertex 0 is connected to vertices 1 and 4
Vertex 1 is connected to vertices 0, 2, 3, and 4
Vertex 2 is connected to vertices 1 and 3
Vertex 3 is connected to vertices 1, 2, and 4
Vertex 4 is connected to vertices 0, 1, and 3

Here's how we can represent this graph using an adjacency list in Java:

TEXT/X-JAVA

1class Main {
2    public static void main(String[] args) {
3        // Adjacency List representation of a graph
4        int V = 5;
5        ArrayList<ArrayList<Integer>> graph = new ArrayList<>(V);
6
7        for (int i = 0; i < V; i++) {
8            graph.add(new ArrayList<>());
9        }
10
11        // Add edges
12        graph.get(0).add(1);
13        graph.get(0).add(4);
14        graph.get(1).add(0);
15        graph.get(1).add(2);
16        graph.get(1).add(3);
17        graph.get(1).add(4);
18        graph.get(2).add(1);
19        graph.get(2).add(3);
20        graph.get(3).add(1);
21        graph.get(3).add(2);
22        graph.get(3).add(4);
23        graph.get(4).add(0);
24        graph.get(4).add(1);
25        graph.get(4).add(3);
26
27        // Print the graph
28        for (int i = 0; i < V; i++) {
29            System.out.println("Adjacency list of vertex " + i + ": ");
30            System.out.print("head");
31            for (Integer j : graph.get(i)) {
32                System.out.print(" -> " + j);
33            }
34            System.out.println();
35        }
36    }
37}

In this code, we first initialize an empty adjacency list graph with 5 elements. Then, we add edges to the graph by accessing the lists at the corresponding indices and adding the adjacent vertices. Finally, we print the adjacency list representation of the graph. You can run this code to see the output.

This is just one way to represent a graph in code. There are other representations like Adjacency Matrix and Edge List, which have their own advantages and disadvantages depending on the problem at hand. It's important to choose the appropriate representation based on the characteristics of the graph and the operations you need to perform on it.

xxxxxxxxxx
}
 
class Main {
    public static void main(String[] args) {
        // Adjacency List representation of a graph
        int V = 5;
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>(V);
​
        for (int i = 0; i < V; i++) {
            graph.add(new ArrayList<>());
        }
​
        // Add edges
        graph.get(0).add(1);
        graph.get(0).add(4);
        graph.get(1).add(0);
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(4);
        graph.get(2).add(1);
        graph.get(2).add(3);
        graph.get(3).add(1);
        graph.get(3).add(2);
        graph.get(3).add(4);
        graph.get(4).add(0);
        graph.get(4).add(1);
        graph.get(4).add(3);
​
        // Print the graph
        for (int i = 0; i < V; i++) {
            System.out.println("Adjacency list of vertex " + i + ": ");

Are you sure you're getting this? Click the correct answer from the options.

Which of the following is NOT a common way to represent a graph in code?

Click the option that best answers the question.

Adjacency List
Adjacency Matrix
Edge List
Linked List

Graph traversal is the process of visiting all vertices/nodes of a graph in a systematic way. It is an essential operation when working with graphs, as it allows us to explore and analyze the connections and relationships between nodes.

There are several algorithms for graph traversal, each with its own characteristics and use cases. Here are some of the most commonly used algorithms:

Depth-First Search (DFS): This algorithm starts at a given node and explores as far as possible along each branch before backtracking. It uses a stack to keep track of visited nodes. DFS is often used to find connected components, detect cycles, and solve problems like finding a path between two nodes.
Breadth-First Search (BFS): This algorithm explores all the vertices at the same level before moving on to the next level. It uses a queue to keep track of visited nodes. BFS is often used to find the shortest path between two nodes and solve problems like finding the minimum number of moves in a game.
Topological Sort: This algorithm orders the vertices of a directed acyclic graph (DAG) in such a way that for every directed edge (u,v), vertex u comes before vertex v in the ordering. Topological sort is often used in scheduling problems, dependency resolution, and determining the order of tasks.
Depth-Limited Search (DLS): This algorithm is similar to DFS but limits the depth of exploration to a given level. It is useful when there is a known depth limit or when searching for a solution within a specific depth limit.
Iterative Deepening Depth-First Search (IDDFS): This algorithm combines the advantages of DFS and BFS. It performs a series of DFS with increasing depth limits until the goal node is found. IDDFS is often used in games with large state spaces and limited memory.

Each of these algorithms has its own advantages and use cases. The choice of algorithm depends on the problem at hand, the characteristics of the graph, and the desired outcome.

Here's an example of a BFS implementation in Java to find the shortest path between two nodes:

TEXT/X-JAVA

1import java.util.*;
2
3class Graph {
4    private int V;
5    private LinkedList<Integer>[] adjList;
6
7    Graph(int V) {
8        this.V = V;
9        adjList = new LinkedList[V];
10        for (int i = 0; i < V; i++) {
11            adjList[i] = new LinkedList<>();
12        }
13    }
14
15    void addEdge(int v, int w) {
16        adjList[v].add(w);
17    }
18
19    void BFS(int start, int end) {
20        boolean[] visited = new boolean[V];
21        int[] parent = new int[V];
22        LinkedList<Integer> queue = new LinkedList<>();
23
24        visited[start] = true;
25        queue.add(start);
26
27        while (!queue.isEmpty()) {
28            int current = queue.poll();
29
30            if (current == end) {
31                printPath(parent, start, end);
32                return;
33            }
34
35            for (int neighbour : adjList[current]) {
36                if (!visited[neighbour]) {
37                    visited[neighbour] = true;
38                    parent[neighbour] = current;
39                    queue.add(neighbour);
40                }
41            }
42        }
43
44        // Path does not exist
45        System.out.println("No path found.");
46    }
47
48    void printPath(int[] parent, int start, int end) {
49        List<Integer> path = new ArrayList<>();
50        int current = end;
51
52        while (current != start) {
53            path.add(current);
54            current = parent[current];
55        }
56
57        path.add(start);
58        Collections.reverse(path);
59
60        System.out.println("Shortest path between " + start + " and " + end + ": ");
61        for (int vertex : path) {
62            System.out.print(vertex + " -> ");
63        }
64        System.out.println();
65    }
66}

Build your intuition. Click the correct answer from the options.

What is the main goal of graph traversal algorithms?

Click the option that best answers the question.

To find the longest path between two nodes
To determine if a graph is cyclic
To visit all nodes in a graph
To find the smallest path between two nodes

Graph search algorithms are used to find specific nodes in a graph. These algorithms allow us to navigate through the graph and search for nodes that satisfy certain conditions. Let's explore some commonly used graph search algorithms.

Depth-First Search (DFS): DFS explores as far as possible along each branch before backtracking. It traverses the graph using a stack and is often used to find connected components and detect cycles. Here's an example of DFS in Java:

TEXT/X-JAVA

1class Graph {
2  private int V;
3  private LinkedList<Integer>[] adjList;
4
5  Graph(int V) {
6    this.V = V;
7    adjList = new LinkedList[V];
8    for (int i = 0; i < V; i++) {
9      adjList[i] = new LinkedList<>();
10    }
11  }
12
13  void addEdge(int v, int w) {
14    adjList[v].add(w);
15  }
16
17  void DFS(int start) {
18    boolean[] visited = new boolean[V];
19    DFSUtil(start, visited);
20  }
21
22  void DFSUtil(int v, boolean[] visited) {
23    visited[v] = true;
24    System.out.print(v + " ");
25
26    for (int i : adjList[v]) {
27      if (!visited[i]) {
28        DFSUtil(i, visited);
29      }
30    }
31  }
32}

xxxxxxxxxx
 
class Main {
  public static void main(String[] args) {
    // replace with your Java logic here
    
  }
}

Depth-First Search (DFS) explores as far as possible along each branch before backtracking. It traverses the graph using a ___ and is often used to find ____ and detect ____.

The correct term for the first blank is stack, which is a data structure that follows the Last-In-First-Out (LIFO) principle. The second blank is connected components, which are sets of nodes that are reachable from one another. Finally, the third blank is cycles, which are paths that start and end at the same node.

DFS can be implemented using a recursive or iterative approach. The recursive approach is simpler to implement but may encounter a stack overflow error for large graphs. The iterative approach uses an explicit stack data structure to avoid the stack overflow error.

Here's an example of implementing DFS using an iterative approach in Python:

PYTHON

1from collections import defaultdict
2
3class Graph:
4    def __init__(self):
5        self.graph = defaultdict(list)
6
7    def add_edge(self, u, v):
8        self.graph[u].append(v)
9
10    def dfs(self, start):
11        visited = set()
12        stack = [start]
13
14        while stack:
15            vertex = stack.pop()
16            if vertex not in visited:
17                print(vertex, end=' ')
18                visited.add(vertex)
19
20                for neighbor in self.graph[vertex]:
21                    if neighbor not in visited:
22                        stack.append(neighbor)
23
24# Create a graph
25graph = Graph()
26graph.add_edge(0, 1)
27graph.add_edge(0, 2)
28graph.add_edge(1, 2)
29graph.add_edge(2, 0)
30graph.add_edge(2, 3)
31graph.add_edge(3, 3)
32
33# Perform DFS
34graph.dfs(2)

Shortest Paths

In graph theory, the shortest path problem is the problem of finding a path between two nodes such that the sum of the weights of its edges is minimized. This problem arises in various applications such as network routing, GPS navigation, and social networks.

There are several algorithms to find the shortest path between nodes in a graph. Some of the commonly used algorithms are:

Dijkstra's Algorithm: It is an algorithm for finding the shortest paths between nodes in a weighted graph with non-negative edge weights.
Bellman-Ford Algorithm: It is an algorithm for finding the shortest paths between nodes in a weighted graph with negative or positive edge weights.
A* Search Algorithm: It is an algorithm that combines elements of Dijkstra's Algorithm and heuristic search to find the shortest path between nodes.
Floyd-Warshall Algorithm: It is an algorithm for finding the shortest paths between all pairs of nodes in a weighted graph.

The choice of algorithm depends on the specific requirements of the problem and the characteristics of the graph. For example, if the graph has non-negative edge weights, Dijkstra's Algorithm is a good choice. If the graph has negative edge weights, Bellman-Ford Algorithm can be used.

Here's an example of implementing Dijkstra's Algorithm to find the shortest path between nodes in a graph:

TEXT/X-JAVA

1import java.util.*;
2
3class Graph {
4    private int v;
5    private List<List<Pair<Integer, Integer>>>> adj;
6
7    public Graph(int vertices) {
8        v = vertices;
9        adj = new ArrayList<>();
10        for (int i = 0; i < v; i++)
11            adj.add(new ArrayList<>());
12    }
13
14    public void addEdge(int src, int dest, int weight) {
15        adj.get(src).add(new Pair<>(dest, weight));
16        adj.get(dest).add(new Pair<>(src, weight));
17    }
18
19    public void dijkstra(int src) {
20        int[] dist = new int[v];
21        Arrays.fill(dist, Integer.MAX_VALUE);
22
23        PriorityQueue<Pair<Integer, Integer>>>> pq = new PriorityQueue<>(v, new Comparator<>() {
24            public int compare(Pair<Integer, Integer>>>> p1, Pair<Integer, Integer>>>> p2) {
25                int key1 = p1.getValue();
26                int key2 = p2.getValue();
27                return key1 - key2;
28            }
29        });
30
31        dist[src] = 0;
32        pq.add(new Pair<>(src, 0));
33
34        while (!pq.isEmpty()) {
35            int u = pq.poll().getKey();
36
37            for (Pair<Integer, Integer>>>> neighbor : adj.get(u)) {
38                int v = neighbor.getKey();
39                int weight = neighbor.getValue();
40
41                if (dist[u] + weight < dist[v]) {
42                    dist[v] = dist[u] + weight;
43                    pq.add(new Pair<>(v, dist[v]));
44                }
45            }
46        }
47
48        // Print the shortest paths
49        System.out.println("Vertex\t\tDistance from Source");
50        for (int i = 0; i < v; ++i)
51            System.out.println(i + "\t\t" + dist[i]);
52    }
53}
54
55public class ShortestPaths {
56    public static void main(String[] args) {
57        int vertices = 5;
58        int src = 0;
59
60        Graph graph = new Graph(vertices);
61
62        graph.addEdge(0, 1, 4);
63        graph.addEdge(0, 2, 2);
64        graph.addEdge(1, 2, 1);
65        graph.addEdge(1, 3, 3);
66        graph.addEdge(2, 3, 4);
67        graph.addEdge(3, 4, 2);
68
69        graph.dijkstra(src);
70    }
71}

xxxxxxxxxx
 
\/\/@TODO: INSERT JAVA CODE HERE
​
​
class ShortestPaths {
    public static void main(String[] args) {
        // Replace with your Java logic here
        System.out.println("Shortest Paths Algorithm");
    }    
}

Are you sure you're getting this? Is this statement true or false?

The Bellman-Ford Algorithm is used to find the shortest path between nodes in a weighted graph with non-negative edge weights.

Press true if you believe the statement is correct, or false otherwise.

Minimum Spanning Trees

In graph theory, a minimum spanning tree (MST) is a spanning tree of a weighted connected graph that has the minimum possible weight. A spanning tree is a subgraph of a graph that includes all the vertices and is itself a tree.

Minimum spanning trees have various applications, especially in network design, where the goal is to minimize the cost to connect a set of nodes. For example, consider a scenario where you need to connect a set of cities with minimal cost, where each city represents a vertex and the cost to connect two cities represents the weight of an edge.

There are several algorithms to find the minimum spanning tree of a graph, including:

Prim's Algorithm
- It starts with an arbitrary vertex and keeps adding the vertex with the minimum weight edge until all vertices are included in the spanning tree.
- The key idea is to maintain a set of vertices already included in the minimum spanning tree (MST) and a set of vertices not yet included.
- It works on connected, undirected, and weighted graphs.
Kruskal's Algorithm
- It starts with the empty spanning tree and keeps adding the edge with the minimum weight until all vertices are included and the graph becomes connected.
- The key idea is to sort the edges in increasing order of their weight and add the next edge to the spanning tree if it does not form a cycle.
- It works on connected, undirected, and weighted graphs.

The choice of algorithm depends on the specific requirements and characteristics of the graph. Prim's algorithm is efficient for dense graphs, while Kruskal's algorithm works well for sparse graphs.

Here's an example of implementing Prim's Algorithm to find the minimum spanning tree of a graph:

SNIPPET

1<`syntaxhighlight lang="java">
2import java.util.*;
3
4class Graph {
5    // Implement the Graph data structure and the constructors, addEdge() method, etc.
6
7    public void primMST() {
8        // Initialize the variables and data structures
9
10        while (/* There are vertices not included in MST */) {
11            // Find the vertex with the minimum weight edge
12
13            // Add the vertex to MST and update the data structures
14        }
15
16        // Print the minimum spanning tree
17    }
18}
19
20public class MinimumSpanningTrees {
21    public static void main(String[] args) {
22        // Create a graph object and add the edges
23
24        // Call the primMST() method to find the minimum spanning tree
25    }
26}
27</syntaxhighlight>`

xxxxxxxxxx
}
 
import java.util.*;
​
class Graph {
    private int v;
    private List<List<Pair<Integer, Integer>>>> adj;
​
    public Graph(int vertices) {
        v = vertices;
        adj = new ArrayList<>(v);
        for (int i = 0; i < v; i++) {
            adj.add(new ArrayList<>());
        }
    }
​
    public void addEdge(int src, int dest, int weight) {
        adj.get(src).add(new Pair<>(dest, weight));
        adj.get(dest).add(new Pair<>(src, weight));
    }
​
    public void primMST() {
        int[] key = new int[v];
        Arrays.fill(key, Integer.MAX_VALUE);
​
        boolean[] mstSet = new boolean[v];
​
        int[] parent = new int[v];
        parent[0] = -1;
​
        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(v, Comparator.comparingInt(Pair::getValue));

Try this exercise. Fill in the missing part by typing it in.

In graph theory, a minimum spanning tree is a spanning tree of a weighted connected graph that has the minimum possible ___.

Write the missing line below.

Topological Sorting

In graph theory, topological sorting is the linear ordering of the vertices of a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v in the ordering. A topological ordering is possible if and only if the graph has no directed cycles. Topological sorting has many applications, especially in scheduling problems, dependency analysis, and task ordering.

Topological sorting can be performed using various algorithms, including depth-first search (DFS) and breadth-first search (BFS). The algorithm we will focus on is based on DFS.

Here's an example implementation of topological sorting in Java:

TEXT/X-JAVA

1<<code>>

xxxxxxxxxx
}
 
class Graph {
    private int V; // No. of vertices
    private LinkedList<Integer> adj[]; // Adjacency List
​
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }
​
    void addEdge(int v, int w) { adj[v].add(w); }
​
    void topologicalSortUtil(int v, boolean visited[],
                             Stack<Integer> stack) {
        visited[v] = true;
        Integer i;
​
        Iterator<Integer> it = adj[v].iterator();
        while (it.hasNext()) {
            i = it.next();
            if (!visited[i])
                topologicalSortUtil(i, visited, stack);
        }
​
        stack.push(new Integer(v));
    }
​
    void topologicalSort() {

Build your intuition. Fill in the missing part by typing it in.

In graph theory, topological sorting is the _ ordering of the vertices of a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v in the ordering. A topological ordering is possible if and only if the graph has no directed cycles. Topological sorting has many applications, especially in scheduling problems, dependency analysis, and task ordering.

Write the missing line below.

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}

xxxxxxxxxx
}
 
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);

Build your intuition. Fill in the missing part by typing it in.

To determine if a graph is connected, we can use a ____ algorithm.

Write the missing line below.

Graph Coloring

Graph coloring is the assignment of labels, known as colors, to the vertices of a graph such that no two adjacent vertices have the same color.

Graph coloring has a wide variety of applications, such as scheduling tasks with dependencies, register allocation in compilers, and solving Sudoku puzzles.

In the context of graph theory, a graph can be represented as an adjacency matrix. An adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not.

To implement graph coloring, we can use a backtracking algorithm. The idea is to recursively try different colors for each vertex until a valid coloring is found.

Here's an example of Java code that performs graph coloring:

TEXT/X-JAVA

1// Example code for graph coloring
2int[][] graph = {
3  {0, 1, 1, 0, 0},
4  {1, 0, 1, 1, 0},
5  {1, 1, 0, 1, 1},
6  {0, 1, 1, 0, 1},
7  {0, 0, 1, 1, 0}
8};
9
10int numOfNodes = graph.length;
11
12int[] colors = new int[numOfNodes];
13// Initialize all nodes with no color
14for (int i = 0; i < numOfNodes; i++) {
15  colors[i] = 0;
16}
17
18int numOfColors = 3; // Number of available colors
19
20// Call the graph coloring function
21if (graphColoring(graph, numOfColors, colors, 0)) {
22  System.out.println("Graph can be colored with " + numOfColors + " colors.");
23  System.out.println("Colors assigned to nodes:");
24  for (int i = 0; i < numOfNodes; i++) {
25    System.out.println("Node " + i + ": Color " + colors[i]);
26  }
27} else {
28  System.out.println("Graph cannot be colored with " + numOfColors + " colors.");
29}
30
31private static boolean graphColoring(int[][] graph, int numOfColors, int[] colors, int node) {
32  int numOfNodes = graph.length;
33
34  // Base case: All nodes have been assigned a color
35  if (node == numOfNodes) {
36    return true;
37  }
38
39  // Try different colors for the current node
40  for (int color = 1; color <= numOfColors; color++) {
41    if (isSafe(graph, colors, node, color)) {
42      // Assign the current color
43      colors[node] = color;
44
45      // Recursively color the remaining nodes
46      if (graphColoring(graph, numOfColors, colors, node + 1)) {
47        return true;
48      }
49
50      // Reset the color if it didn't lead to a solution
51      colors[node] = 0;
52    }
53  }
54
55  return false;
56}
57
58private static boolean isSafe(int[][] graph, int[] colors, int node, int color) {
59  int numOfNodes = graph.length;
60
61  // Check if any adjacent nodes have the same color
62  for (int adjacentNode = 0; adjacentNode < numOfNodes; adjacentNode++) {
63    if (graph[node][adjacentNode] == 1 && colors[adjacentNode] == color) {
64      return false;
65    }
66  }
67
68  return true;
69}

xxxxxxxxxx
}
 
class Main {
  public static void main(String[] args) {
    // replace with your Java logic here
    // Example code for graph coloring
    int[][] graph = {
      {0, 1, 1, 0, 0},
      {1, 0, 1, 1, 0},
      {1, 1, 0, 1, 1},
      {0, 1, 1, 0, 1},
      {0, 0, 1, 1, 0}
    };
​
    int numOfNodes = graph.length;
​
    int[] colors = new int[numOfNodes];
    // Initialize all nodes with no color
    for (int i = 0; i < numOfNodes; i++) {
      colors[i] = 0;
    }
​
    int numOfColors = 3; // Number of available colors
​
    // Call the graph coloring function
    if (graphColoring(graph, numOfColors, colors, 0)) {
      System.out.println("Graph can be colored with " + numOfColors + " colors.");
      System.out.println("Colors assigned to nodes:");
      for (int i = 0; i < numOfNodes; i++) {
        System.out.println("Node " + i + ": Color " + colors[i]);
      }

Let's test your knowledge. Is this statement true or false?

Graph coloring is the process of assigning colors to the vertices of a graph such that no two adjacent vertices have the same color.

Press true if you believe the statement is correct, or false otherwise.

Eulerian and Hamiltonian Paths

In graph theory, an Eulerian path is a path in a graph that visits every edge exactly once. An Eulerian circuit is an Eulerian path that starts and ends at the same vertex.

Similarly, a Hamiltonian path is a path in a graph that visits every vertex exactly once. A Hamiltonian cycle is a Hamiltonian path that starts and ends at the same vertex.

Eulerian and Hamiltonian paths are important concepts in graph theory and have applications in various areas, such as transportation planning, network optimization, and DNA sequencing.

To find an Eulerian path or Eulerian circuit in a graph, we can use the Hierholzer's algorithm. This algorithm starts from an arbitrary vertex and repeatedly adds edges to the current path until all edges have been visited.

Here's an example of Java code that finds an Eulerian path in a graph:

TEXT/X-JAVA

1// Example code for finding an Eulerian path in a graph
2int[][] graph = {
3  {0, 1, 1, 1, 0},
4  {1, 0, 1, 0, 1},
5  {1, 1, 0, 1, 0},
6  {1, 0, 1, 0, 1},
7  {0, 1, 0, 1, 0}
8};
9
10int[] path = new int[graph.length];
11for (int i = 0; i < path.length; i++) {
12  path[i] = -1;
13}
14
15// Starting vertex
16int startVertex = 0;
17
18// Call the function to find an Eulerian path
19findEulerianPath(graph, path, startVertex);
20
21// Print the Eulerian path
22System.out.println("Eulerian Path:");
23for (int i = 0; i < path.length; i++) {
24  System.out.print(path[i] + " ");
25}
26
27// Function to find an Eulerian path
28private static void findEulerianPath(int[][] graph, int[] path, int currVertex) {
29  // Loop through all vertices
30  for (int nextVertex = 0; nextVertex < graph.length; nextVertex++) {
31    // Check if an edge exists between the current vertex and the next vertex
32    if (graph[currVertex][nextVertex] == 1) {
33      // Check if the next vertex is not visited already
34      if (path[nextVertex] == -1) {
35        // Set current vertex and next vertex as visited
36        path[nextVertex] = currVertex;
37
38        // Recursively find the Eulerian path for the next vertex
39        findEulerianPath(graph, path, nextVertex);
40
41        // Check if all vertices are visited and there is an edge from the last vertex to the starting vertex
42        if (isLastEdge(graph, currVertex, nextVertex) && isAllVisited(path)) {
43          // Set the last vertex as the next vertex
44          path[0] = nextVertex;
45        }
46      }
47    }
48  }
49}
50
51// Function to check if the current vertex has an edge to the next vertex
52private static boolean isLastEdge(int[][] graph, int currVertex, int nextVertex) {
53  // Get the degree of the current vertex
54  int currVertexDegree = 0;
55  for (int i = 0; i < graph.length; i++) {
56    currVertexDegree += graph[currVertex][i];
57  }
58
59  // If the degree is 1, it is the last edge
60  return currVertexDegree == 1;
61}
62
63// Function to check if all vertices are visited
64private static boolean isAllVisited(int[] path) {
65  for (int i = 0; i < path.length; i++) {
66    if (path[i] == -1) {
67      return false;
68    }
69  }
70  return true;
71}

xxxxxxxxxx
}
 
class Main {
  public static void main(String[] args) {
    // replace with your Java logic here
    // Example code for Eulerian and Hamiltonian Paths
    int[][] graph = {
      {0, 1, 1, 1, 0},
      {1, 0, 1, 0, 1},
      {1, 1, 0, 1, 0},
      {1, 0, 1, 0, 1},
      {0, 1, 0, 1, 0}
    };
​
    int[] path = new int[graph.length];
    for (int i = 0; i < path.length; i++) {
      path[i] = -1;
    }
​
    // Starting vertex
    int startVertex = 0;
​
    // Call the function to find an Eulerian path
    findEulerianPath(graph, path, startVertex);
​
    // Print the Eulerian path
    System.out.println("Eulerian Path:");
    for (int i = 0; i < path.length; i++) {
      System.out.print(path[i] + " ");
    }
  }

Build your intuition. Click the correct answer from the options.

Which of the following statements is true about Eulerian and Hamiltonian paths?

Eulerian paths visit every vertex exactly once.
Hamiltonian paths visit every edge exactly once.
Eulerian paths and Hamiltonian paths are the same thing.
Eulerian paths and Hamiltonian paths always exist in every graph.

Click the option that best answers the question.

1 and 2
1 and 3
2 and 4
3 and 4

Network Flows

In graph theory, a network flow is a directed graph where each edge has a capacity and a flow. The capacity defines the maximum amount of flow that can pass through the edge, while the flow represents the actual amount of flow passing through the edge.

Finding the maximum flow in a network is a common problem in computer science and has applications in various domains such as transportation network optimization, network design, and data compression.

One popular algorithm to find the maximum flow in a network is the Ford-Fulkerson algorithm. This algorithm uses a combination of breadth-first search and capacity augmentation to incrementally find the maximum flow.

Here's an example Java code that demonstrates the Ford-Fulkerson algorithm:

TEXT/X-JAVA

1// Example code for finding the maximum flow in a network
2
3class Main {
4  public static void main(String[] args) {
5    // Example graph with capacities
6    int[][] graph = {
7      {0, 16, 13, 0, 0, 0},
8      {0, 0, 10, 12, 0, 0},
9      {0, 4, 0, 0, 14, 0},
10      {0, 0, 9, 0, 0, 20},
11      {0, 0, 0, 7, 0, 4},
12      {0, 0, 0, 0, 0, 0}
13    };
14
15    int source = 0;
16    int sink = 5;
17
18    int maxFlow = fordFulkerson(graph, source, sink);
19    System.out.println("Maximum Flow: " + maxFlow);
20  }
21
22  private static int fordFulkerson(int[][] graph, int source, int sink) {
23    int[][] residualGraph = new int[graph.length][graph[0].length];
24    for (int i = 0; i < graph.length; i++) {
25      for (int j = 0; j < graph[0].length; j++) {
26        residualGraph[i][j] = graph[i][j];
27      }
28    }
29
30    int[] parent = new int[graph.length];
31    int maxFlow = 0;
32
33    while (bfs(residualGraph, source, sink, parent)) {
34      int pathFlow = Integer.MAX_VALUE;
35
36      for (int vertex = sink; vertex != source; vertex = parent[vertex]) {
37        int u = parent[vertex];
38        pathFlow = Math.min(pathFlow, residualGraph[u][vertex]);
39      }
40
41      for (int vertex = sink; vertex != source; vertex = parent[vertex]) {
42        int u = parent[vertex];
43        residualGraph[u][vertex] -= pathFlow;
44        residualGraph[vertex][u] += pathFlow;
45      }
46
47      maxFlow += pathFlow;
48    }
49
50    return maxFlow;
51  }
52
53  private static boolean bfs(int[][] graph, int source, int sink, int[] parent) {
54    boolean[] visited = new boolean[graph.length];
55
56    Queue<Integer> queue = new LinkedList<>();
57    queue.add(source);
58    visited[source] = true;
59    parent[source] = -1;
60
61    while (!queue.isEmpty()) {
62      int u = queue.poll();
63
64      for (int v = 0; v < graph.length; v++) {
65        if (!visited[v] && graph[u][v] > 0) {
66          queue.add(v);
67          parent[v] = u;
68          visited[v] = true;
69        }
70      }
71    }
72
73    return visited[sink];
74  }
75}

The code defines a graph with capacities and uses the Ford-Fulkerson algorithm to find the maximum flow from a given source to a sink vertex. The maximum flow is then printed to the console.

Feel free to modify the code and test it with different network configurations to understand the concept of network flows and the Ford-Fulkerson algorithm better.

xxxxxxxxxx
}
 
class Main {
  public static void main(String[] args) {
    // replace with your Java logic here
    // Example graph with capacities
    int[][] graph = {
      {0, 16, 13, 0, 0, 0},
      {0, 0, 10, 12, 0, 0},
      {0, 4, 0, 0, 14, 0},
      {0, 0, 9, 0, 0, 20},
      {0, 0, 0, 7, 0, 4},
      {0, 0, 0, 0, 0, 0}
    };
​
    int source = 0;
    int sink = 5;
​
    int maxFlow = fordFulkerson(graph, source, sink);
    System.out.println("Maximum Flow: " + maxFlow);
  }
​
  private static int fordFulkerson(int[][] graph, int source, int sink) {
    int[][] residualGraph = new int[graph.length][graph[0].length];
    for (int i = 0; i < graph.length; i++) {
      for (int j = 0; j < graph[0].length; j++) {
        residualGraph[i][j] = graph[i][j];
      }
    }
​
    int[] parent = new int[graph.length];

Let's test your knowledge. Fill in the missing part by typing it in.

In graph theory, a ____ is a directed graph where each edge has a capacity and a flow.

Write the missing line below.

Graph Isomorphism

Graph isomorphism is a topic in graph theory that deals with determining whether two graphs are isomorphic, i.e., whether they have the same structure.

A graph isomorphism is a one-to-one mapping between the vertices of two graphs that preserves the edge structure.

Determining graph isomorphism is a challenging problem and is often studied in the context of algorithm design and complexity theory.

There are various algorithms to check for graph isomorphism, including the Weisfeiler-Lehman algorithm, the Nauty algorithm, and the Individualization-Refinement algorithm.

Here's an example Java code that demonstrates checking graph isomorphism:

TEXT/X-JAVA

1// Example code for checking graph isomorphism
2
3class Main {
4  public static void main(String[] args) {
5    // Create two example graphs
6    int[][] graph1 = {
7      {0, 1, 1},
8      {1, 0, 1},
9      {1, 1, 0}
10    };
11
12    int[][] graph2 = {
13      {0, 1, 0},
14      {1, 0, 1},
15      {0, 1, 0}
16    };
17
18    if (isIsomorphic(graph1, graph2)) {
19      System.out.println("The two graphs are isomorphic.");
20    } else {
21      System.out.println("The two graphs are not isomorphic.");
22    }
23  }
24
25  private static boolean isIsomorphic(int[][] graph1, int[][] graph2) {
26    // Logic for checking graph isomorphism
27    // Replace with your own implementation
28    return true;
29  }
30}

The code creates two example graphs and uses a placeholder function isIsomorphic to check if they are isomorphic. In the code, replace the isIsomorphic function with the logic for checking graph isomorphism.

Feel free to modify the code and test it with different graphs to understand the concept of graph isomorphism better.

xxxxxxxxxx
}
 
class Main {
  public static void main(String[] args) {
    // replace with your Java logic here
    System.out.println("Checking graph isomorphism...");
​
    // Create two example graphs
    int[][] graph1 = {
      {0, 1, 1},
      {1, 0, 1},
      {1, 1, 0}
    };
​
    int[][] graph2 = {
      {0, 1, 0},
      {1, 0, 1},
      {0, 1, 0}
    };
​
    if (isIsomorphic(graph1, graph2)) {
      System.out.println("The two graphs are isomorphic.");
    } else {
      System.out.println("The two graphs are not isomorphic.");
    }
  }
​
  private static boolean isIsomorphic(int[][] graph1, int[][] graph2) {
    // Logic for checking graph isomorphism
    // Replace with your own implementation
    return true;

Try this exercise. Fill in the missing part by typing it in.

Graph isomorphism is a topic in graph theory that deals with determining whether two graphs are ___, i.e., whether they have the same structure.

A graph isomorphism is a one-to-one mapping between the _ of two graphs that preserves the edge structure.

Determining graph isomorphism is a challenging problem and is often studied in the context of algorithm design and complexity theory.

There are various algorithms to check for graph isomorphism, including the __, the ____, and the _ algorithm.

Write the missing line below.

Graph Partitioning

Graph partitioning is the process of dividing a graph into subsets, or partitions, in such a way that the vertices within each partition have more connections to other vertices in the same partition than to vertices in other partitions.

Graph partitioning is a fundamental problem in computer science and finds applications in various domains, such as parallel computing, network optimization, and social network analysis.

There are several algorithms to partition a graph into subsets, including the Kernighan-Lin algorithm, the Spectral bisection algorithm, and the Metis algorithm.

Here's an example Java code that demonstrates graph partitioning:

TEXT/X-JAVA

1// Example code for graph partitioning
2
3import java.util.ArrayList;
4import java.util.Arrays;
5
6public class GraphPartition {
7  public static void main(String[] args) {
8    // Create example graph
9    int[][] graph = {
10      {0, 1, 0, 1},
11      {1, 0, 1, 0},
12      {0, 1, 0, 1},
13      {1, 0, 1, 0}
14    };
15
16    // Perform graph partitioning
17    ArrayList<ArrayList<Integer>> partitions = partitionGraph(graph);
18
19    // Print the partitions
20    for (int i = 0; i < partitions.size(); i++) {
21      System.out.println("Partition " + (i + 1) + ": " + partitions.get(i));
22    }
23  }
24
25  private static ArrayList<ArrayList<Integer>> partitionGraph(int[][] graph) {
26    // Logic for graph partitioning
27    // Replace with your own implementation
28    return new ArrayList<>();
29  }
30}

The code creates an example graph represented as a 2D array and uses a placeholder function partitionGraph to partition the graph into subsets. In the code, replace the partitionGraph function with the logic for performing graph partitioning.

Feel free to modify the code and test it with different graphs to understand the concept of graph partitioning better.

xxxxxxxxxx
 
import java.util.ArrayList;
import java.util.Arrays;
​
public class GraphPartition {
  public static void main(String[] args) {
    // Create example graph
    int[][] graph = {
      {0, 1, 0, 1},
      {1, 0, 1, 0},
      {0, 1, 0, 1},
      {1, 0, 1, 0}
    };
​
    // Perform graph partitioning
    ArrayList<ArrayList<Integer>> partitions = partitionGraph(graph);
​
    // Print the partitions
    for (int i = 0; i < partitions.size(); i++) {
      System.out.println("Partition " + (i + 1) + ": " + partitions.get(i));
    }
  }
​
  private static ArrayList<ArrayList<Integer>> partitionGraph(int[][] graph) {
    // Logic for graph partitioning
    // Replace with your own implementation
    return new ArrayList<>();
  }
}

Let's test your knowledge. Click the correct answer from the options.

Which of the following algorithms can be used to partition a graph into subsets?

Click the option that best answers the question.

Kernighan-Lin algorithm
Spectral bisection algorithm
Metis algorithm
All of the above

Generating complete for this lesson!

Are you sure you're getting this? Click the correct answer from the options.

Click the option that best answers the question.

Are you sure you're getting this? Click the correct answer from the options.

Click the option that best answers the question.

Build your intuition. Click the correct answer from the options.

Click the option that best answers the question.

Are you sure you're getting this? Is this statement true or false?

Minimum Spanning Trees

Try this exercise. Fill in the missing part by typing it in.

Topological Sorting

Build your intuition. Fill in the missing part by typing it in.

Graph Connectivity

Build your intuition. Fill in the missing part by typing it in.

Graph Coloring

Let's test your knowledge. Is this statement true or false?

Eulerian and Hamiltonian Paths

Build your intuition. Click the correct answer from the options.

Click the option that best answers the question.

Network Flows

Let's test your knowledge. Fill in the missing part by typing it in.

Graph Isomorphism

Try this exercise. Fill in the missing part by typing it in.

Graph Partitioning

Let's test your knowledge. Click the correct answer from the options.

Click the option that best answers the question.

Programming Categories

Popular Lessons