Проверьте, является ли данный граф двудольным, используя DFS

Опубликовано: 7 Января, 2022

Для связного графа проверьте, является ли граф двудольным или нет. Двудольный граф возможен, если раскраска графа возможна в два цвета, так что вершины в наборе окрашены в один цвет. Обратите внимание, что можно раскрасить график цикла с четным циклом, используя два цвета. Например, см. Следующий график.

Невозможно раскрасить график циклов с нечетным циклом, используя два цвета.

В предыдущем посте обсуждался подход с использованием BFS. В этом посте был реализован подход с использованием DFS.

Ниже приведен алгоритм проверки двудольности графа.

Используйте массив color [], в котором хранится 0 или 1 для каждого узла, обозначающего противоположные цвета.
Вызовите функцию DFS с любого узла.
Если узел u ранее не посещался, тогда назначьте! Color [v] цвету [u] и снова вызовите DFS, чтобы посетить узлы, подключенные к u.
Если в любой точке цвет [u] равен цвету [v], то узел двудольный.
Измените функцию DFS так, чтобы она возвращала в конце логическое значение.

Below is the implementation of the above approach:

C++

// C++ program to check if a connected
// graph is bipartite or not suing DFS
#include <bits/stdc++.h>
using namespace std;
 
// function to store the connected nodes
void addEdge(vector<int> adj[], int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}
 
// function to check whether a graph is bipartite or not
bool isBipartite(vector<int> adj[], int v,
                 vector<bool>& visited, vector<int>& color)
{
 
    for (int u : adj[v]) {
 
        // if vertex u is not explored before
        if (visited[u] == false) {
 
            // mark present vertic as visited
            visited[u] = true;
 
            // mark its color opposite to its parent
            color[u] = !color[v];
 
            // if the subtree rooted at vertex v is not bipartite
            if (!isBipartite(adj, u, visited, color))
                return false;
        }
 
        // if two adjacent are colored with same color then
        // the graph is not bipartite
        else if (color[u] == color[v])
            return false;
    }
    return true;
}
 
// Driver Code
int main()
{
    // no of nodes
    int N = 6;
 
    // to maintain the adjacency list of graph
    vector<int> adj[N + 1];
 
    // to keep a check on whether
    // a node is discovered or not
    vector<bool> visited(N + 1);
 
    // to color the vertices
    // of graph with 2 color
    vector<int> color(N + 1);
 
    // adding edges to the graph
    addEdge(adj, 1, 2);
    addEdge(adj, 2, 3);
    addEdge(adj, 3, 4);
    addEdge(adj, 4, 5);
    addEdge(adj, 5, 6);
    addEdge(adj, 6, 1);
 
    // marking the source node as visited
    visited[1] = true;
 
    // marking the source node with a color
    color[1] = 0;
 
    // Function to check if the graph
    // is Bipartite or not
    if (isBipartite(adj, 1, visited, color)) {
        cout << "Graph is Bipartite";
    }
    else {
        cout << "Graph is not Bipartite";
    }
 
    return 0;
}

Java

// Java program to check if a connected
// graph is bipartite or not suing DFS
import java.util.*;
 
class GFG{
 
// Function to store the connected nodes
static void addEdge(ArrayList<ArrayList<Integer>> adj,
                    int u, int v)
{
    adj.get(u).add(v);
    adj.get(v).add(u);
}
 
// Function to check whether a
// graph is bipartite or not
static boolean isBipartite(ArrayList<ArrayList<Integer>> adj,
                           int v, boolean visited[],
                           int color[])
{
    for(int u : adj.get(v))
    {
         
        // If vertex u is not explored before
        if (visited[u] == false)
        {
             
            // Mark present vertic as visited
            visited[u] = true;
 
            // Mark its color opposite to its parent
            color[u] = 1 - color[v];
 
            // If the subtree rooted at vertex
            // v is not bipartite
            if (!isBipartite(adj, u, visited, color))
                return false;
        }
 
        // If two adjacent are colored with
        // same color then the graph is
        // not bipartite
        else if (color[u] == color[v])
            return false;
    }
    return true;
}
 
// Driver Code
public static void main(String args[])
{
     
    // No of nodes
    int N = 6;
 
    // To maintain the adjacency list of graph
    ArrayList<
    ArrayList<Integer>> adj = new ArrayList<
                                  ArrayList<Integer>>(N + 1);
     
    // Initialize all the vertex
    for(int i = 0; i <= N; i++)
    {
        adj.add(new ArrayList<Integer>());
    }
     
    // To keep a check on whether
    // a node is discovered or not
    boolean visited[] = new boolean[N + 1];
     
    // To color the vertices
    // of graph with 2 color
    int color[] = new int[N + 1];
     
    // The value "-1" of colorArr[i] is
    // used to indicate that no color is
    // assigned to vertex "i". The value
    // 1 is used to indicate first color
    // is assigned and value 0 indicates 
    // second color is assigned.
    Arrays.fill(color, -1);
 
    // Adding edges to the graph
    addEdge(adj, 1, 2);
    addEdge(adj, 2, 3);
    addEdge(adj, 3, 4);
    addEdge(adj, 4, 5);
    addEdge(adj, 5, 6);
    addEdge(adj, 6, 1);
 
    // Marking the source node as visited
    visited[1] = true;
 
    // Marking the source node with a color
    color[1] = 0;
 
    // Function to check if the graph
    // is Bipartite or not
    if (isBipartite(adj, 1, visited, color))
    {
        System.out.println("Graph is Bipartite");
    }
    else
    {
        System.out.println("Graph is not Bipartite");
    }
}
}
 
// This code is contributed by adityapande88

Python3

# Python3 program to check if a connected
# graph is bipartite or not suing DFS
  
# Function to store the connected nodes
def addEdge(adj, u, v):
 
    adj[u].append(v)
    adj[v].append(u)
 
# Function to check whether a graph is
# bipartite or not
def isBipartite(adj, v, visited, color):
 
    for u in adj[v]:
  
        # If vertex u is not explored before
        if (visited[u] == False):
  
            # Mark present vertic as visited
            visited[u] = True
  
            # Mark its color opposite to its parent
            color[u] = not color[v]
  
            # If the subtree rooted at vertex v
            # is not bipartite
            if (not isBipartite(adj, u,
                                visited, color)):
                return false
                 
        # If two adjacent are colored with
        # same color then the graph is not
        # bipartite
        elif (color[u] == color[v]):
            return Talse
     
    return True
 
# Driver Code
if __name__=="__main__":
 
    # No of nodes
    N = 6
  
    # To maintain the adjacency list of graph
    adj = [[] for i in range(N + 1)]
  
    # To keep a check on whether
    # a node is discovered or not
    visited = [0 for i in range(N + 1)]
  
    # To color the vertices
    # of graph with 2 color
    color = [0 for i in range(N + 1)]
  
    # Adding edges to the graph
    addEdge(adj, 1, 2)
    addEdge(adj, 2, 3)
    addEdge(adj, 3, 4)
    addEdge(adj, 4, 5)
    addEdge(adj, 5, 6)
    addEdge(adj, 6, 1)
  
    # Marking the source node as visited
    visited[1] = True
  
    # Marking the source node with a color
    color[1] = 0
  
    # Function to check if the graph
    # is Bipartite or not
    if (isBipartite(adj, 1, visited, color)):
        print("Graph is Bipartite")
    else:
        print("Graph is not Bipartite")
         
# This code is contributed by rutvik_56

C#

// C# program to check if a connected
// graph is bipartite or not suing DFS
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to store the connected nodes
static void addEdge(List<List<int>> adj,
                    int u, int v)
{
    adj[u].Add(v);
    adj[v].Add(u);
}
 
// Function to check whether a
// graph is bipartite or not
static bool isBipartite(List<List<int>> adj,
                        int v, bool []visited,
                        int []color)
{
    foreach(int u in adj[v])
    {
         
        // If vertex u is not explored before
        if (visited[u] == false)
        {
             
            // Mark present vertic as visited
            visited[u] = true;
 
            // Mark its color opposite to its parent
            color[u] = 1 - color[v];
 
            // If the subtree rooted at vertex
            // v is not bipartite
            if (!isBipartite(adj, u, visited, color))
                return false;
        }
         
        // If two adjacent are colored with
        // same color then the graph is
        // not bipartite
        else if (color[u] == color[v])
            return false;
    }
    return true;
}
 
// Driver Code
public static void Main(String []args)
{
     
    // No of nodes
    int N = 6;
 
    // To maintain the adjacency list of graph
    List<List<int>> adj = new List<List<int>>(N + 1);
     
    // Initialize all the vertex
    for(int i = 0; i <= N; i++)
    {
        adj.Add(new List<int>());
    }
     
    // To keep a check on whether
    // a node is discovered or not
    bool []visited = new bool[N + 1];
     
    // To color the vertices
    // of graph with 2 color
    int []color = new int[N + 1];
     
    // The value "-1" of colorArr[i] is
    // used to indicate that no color is
    // assigned to vertex "i". The value
    // 1 is used to indicate first color
    // is assigned and value 0 indicates 
    // second color is assigned.
    for(int i = 0; i <= N; i++)  
        color[i] = -1;
 
    // Adding edges to the graph
    addEdge(adj, 1, 2);
    addEdge(adj, 2, 3);
    addEdge(adj, 3, 4);
    addEdge(adj, 4, 5);
    addEdge(adj, 5, 6);
    addEdge(adj, 6, 1);
 
    // Marking the source node as visited
    visited[1] = true;
     
    // Marking the source node with a color
    color[1] = 0;
 
    // Function to check if the graph
    // is Bipartite or not
    if (isBipartite(adj, 1, visited, color))
    {
        Console.WriteLine("Graph is Bipartite");
    }
    else
    {
        Console.WriteLine("Graph is not Bipartite");
    }
}
}
 
// This code is contributed by Princi Singh

C++

Проверьте, является ли данный граф двудольным, используя DFS

C++

Java

Python3

C#

РЕКОМЕНДУЕМЫЕ СТАТЬИ