Программа на Java для поиска наибольшего независимого множества в графе по дополнениям

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

В графе с V вершинами и E ребрами LIS (наибольший независимый набор) - это набор всех вершин в графе, которые не соединены друг с другом E ребрами.

Подход :

Мы создаем HashMap, который имеет пару целых чисел и целое число в качестве параметров.
Пара представляет две вершины, а целое число представляет собой границу между этими двумя вершинами.
Мы перебираем все наши вершины и проверяем, существует ли ребро между двумя определенными вершинами. При невыполнении этого условия мы добавляем эти вершины в наши результирующие HashSet-независимые множества.
Таким образом, все наборы независимых наборов добавляются в HashSet, и на последнем шаге мы определяем самый большой из них.

Решение :

Взяв количество вершин и количество ребер в качестве входных данных, мы можем вычислить наибольшее независимое множество в графе.

We also need to define a user-defined pair class here which checks if there exists an edge between two vertices.

Java

static class pair {
    int first, second;
    pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
    @Override public String toString()
    {
        return "(" + first + "," + second + ")";
    }
}

In order to find the largest independent set in the graph, we can first find out all the independent sets in the graph and then separate the set with the maximum length for our answer.

Java

// Java Program to Find the Largest Independent Set in a
// Graph by Complements
  
import java.util.*;
class GFG {
    static ArrayList<Integer> vertices = new ArrayList<>();
    static HashMap<pair, Integer> edges = new HashMap<>();
    
    static HashSet<ArrayList<Integer> > independentSets = new HashSet<>();
  
    public static void main(String args[])
    {
        int numOfVertices = 4, numOfEdges = 0;
        for (int i = 1; i <= numOfVertices; i++)
            vertices.add(i);
  
        HashSet<Integer> SolnSet = new HashSet<>();
        
        // this function call adds all sets to the global
        // solution set
        findAllIndependentSets(1, numOfVertices, SolnSet);
        
        // to find the largest result set
        ArrayList<Integer> Max = new ArrayList<>();
  
        for (ArrayList<Integer> i : independentSets) {
            System.out.println(i);
            
            // comparing lengths of all
            // independent sets
            if (i.size() > Max.size()) 
                Max = i;
        }
  
        System.out.println("Maximal Independent Set = "
                           + Max);
    }
    
    // this function finds all independent sets and
    // adds them to the solution object
    static void findAllIndependentSets(int currentVertice, int setSize,
                           HashSet<Integer> SolnSet)
    {
        for (int i = currentVertice; i <= setSize; i++) 
        {
            // checking if vertex is independent
            if (checkSafety(vertices.get(i - 1), SolnSet)) {
                
                // adding to the temporary solution set
                SolnSet.add(vertices.get(i - 1));
                
                findAllIndependentSets(i + 1, setSize,
                                       SolnSet);
                
                // removing previous set
                SolnSet.remove(vertices.get(i - 1));
            }
        }
        
        // appending the temporary solution set to the
        // solution object
        independentSets.add(new ArrayList<Integer>(SolnSet));
    }
    
    // this function checks if there exists an edge between
    // 2 vertices
    static boolean checkSafety(int vertex,
                               HashSet<Integer> SolnSet)
    {
        for (int i : SolnSet) {
            if (edges.containsKey(new pair(i, vertex)))
                
                // if there is an edge, return false
                return false;
        }
        
        // if vertex is independent , return true
        return true;
    }
    
    // user-define pair class
    static class pair {
        int first, second;
        pair(int first, int second)
        {
            this.first = first;
            this.second = second;
        }
        @Override public String toString()
        {
            return "(" + first + "," + second + ")";
        }
    }
}

Output

[1]
[1, 2, 3]
[1, 3, 4]
[2]
[]
[1, 2, 4]
[1, 2]
[2, 3, 4]
[2, 3]
[3, 4]
[3]
[1, 3]
[2, 4]
[4]
[1, 4]
[1, 2, 3, 4]
Maximal Independent Set = [1, 2, 3, 4]

Вниманию читателя! Не прекращайте учиться сейчас. Ознакомьтесь со всеми важными концепциями Java Foundation и коллекций с помощью курса "Основы Java и Java Collections" по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Picked Java

Программа на Java для поиска наибольшего независимого множества в графе по дополнениям

Java

Java

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