Backtracking and Graphs
In the previous screens, we learned about the basic backtracking algorithm and how to solve simple problems using backtracking. Now, let's see how backtracking can be applied to solve graph-related problems.
Graphs are widely used in computer science to represent relationships between objects. They are composed of nodes (vertices) and edges, where each edge connects two nodes. In graph theory, many problems can be formulated as finding paths, cycles, or other structures in a graph.
One common graph problem is checking if a given graph is bipartite. A graph is bipartite if its nodes can be divided into two distinct sets (coloring) such that there are no edges between nodes of the same set. This problem can be solved using backtracking.
Here's an example implementation in C++:
1#include <iostream>
2#include <vector>
3#include <unordered_set>
4using namespace std;
5
6// Function to check if a graph is bipartite
7bool isBipartite(vector<vector<int>>& graph, int node, vector<int>& color) {
8 // Base case: node has been colored
9 if (color[node] != 0) {
10 return true;
11 }
12
13 // Color the current node
14 color[node] = 1;
15
16 // Traverse the adjacent nodes
17 for (int neighbor : graph[node]) {
18 // Check if neighbor has same color
19 if (color[neighbor] == color[node]) {
20 return false;
21 }
22
23 // Color the neighbor with a different color
24 if (color[neighbor] == 0 && !isBipartite(graph, neighbor, color)) {
25 return false;
26 }
27 }
28
29 return true;
30}
31
32// Function to check if a given graph is bipartite
33bool isBipartite(vector<vector<int>>& graph) {
34 int n = graph.size();
35 vector<int> color(n, 0);
36
37 // Traverse each node and check if it is bipartite
38 for (int i = 0; i < n; i++) {
39 if (color[i] == 0 && !isBipartite(graph, i, color)) {
40 return false;
41 }
42 }
43
44 return true;
45}
46
47int main() {
48 // Create a graph
49 vector<vector<int>> graph = {{1, 2}, {0, 3}, {0, 4}, {1, 4}, {2, 3}};
50
51 // Check if the graph is bipartite
52 bool isBipartiteGraph = isBipartite(graph);
53
54 // Print the result
55 if (isBipartiteGraph) {
56 cout << "The graph is bipartite." << endl;
57 } else {
58 cout << "The graph is not bipartite." << endl;
59 }
60
61 return 0;
62}In this example, we have a function isBipartite that checks if a given graph is bipartite. It uses backtracking to perform a depth-first search (DFS) traversal of the graph and assigns colors to each node. The algorithm continues exploring the graph, ensuring that adjacent nodes have different colors. If at any point, a node with the same color as its neighbor is encountered, the graph is not bipartite.
This backtracking approach allows us to solve the bipartite graph problem efficiently and determine if a given graph can be divided into two distinct sets.
Next, let's move on to solving another classic problem using backtracking: the N-Queens problem.
xxxxxxxxxx}using namespace std;// Function to check if a graph is bipartitebool isBipartite(vector<vector<int>>& graph, int node, vector<int>& color) { // Base case: node has been colored if (color[node] != 0) { return true; } // Color the current node color[node] = 1; // Traverse the adjacent nodes for (int neighbor : graph[node]) { // Check if neighbor has same color if (color[neighbor] == color[node]) { return false; } // Color the neighbor with a different color if (color[neighbor] == 0 && !isBipartite(graph, neighbor, color)) { return false; } } return true;