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

Опубликовано: 30 Ноября, 2021

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

Примеры:

 Вход:
Введите количество вершин:  
4
Введите количество ребер:  
5
Введите график: <Старт> <конец>
1 2
2 3
3 4
4 1
1 3
Выход:
График:
1-> 2-> 3
2-> 3
3-> 4
4-> 1
Набор ребер в наборе дуги FeedBack: 2 - 3
4 - 1

Вход:
Введите количество вершин:  
5
Введите количество ребер:  
5
Введите график: <Старт> <конец>
1 2
2 4
5 3
5 1
4 3.
Выход:
График:
1-> 2
2-> 4
4-> 3
5-> 3-> 1
Набор ребер в дуге FeedBack: Нет

Подход:

Мы объявим все необходимые переменные, такие как количество, ребра, начало, конец и вершины.
Теперь мы вызовем функцию Graph: мы возьмем и сохраним значения в соседнем списке, который будет объявлен как переменная класса.
Затем, сохраняя условие while, мы будем вводить все начальные и конечные точки конструктора в графе.
Теперь вызываем функцию set edge: мы проверяем, пуст ли соседний список, если нет, мы сохраним его значения в нем.
Затем мы вызываем функцию printGraph () - этот метод в основном печатает график, в котором мы повторяем цикл и печатаем элементы, и сохраняем его в списке.
Затем мы вызываем объект класса и вызываем функцию проверки - каждый итератор проверяет, взяли ли мы значение только один раз. Если значение повторяется, мы удаляем его.
Затем мы устанавливаем вершину Feedback и вызываем функцию - теперь мы проверим, посетили ли мы все узлы, если бы мы сделали, мы бы посчитали его, а если бы мы не сделали, мы бы оставили его равным 1. Теперь, используя все это, найдет, какой узел можно удалить.

Код:

Ява

 // Java Program to Find a Good Feedback Vertex Set in a
 // Graph
 import java.util.HashMap;
 import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
 import java.util.Scanner;
 // Let us declare a class
 class Edge
 {
    // We have declared a Map with Integer as its parameters
    // Named adjacentList
    private Map<Integer, List<Integer> > adjacentList; 
    // Now lets us declare a function called "Graph"
    public Edge( int vertices)
    {
        // Now taking the new List as a HashMap
        adjacentList
            = new HashMap<Integer, List<Integer> >(); 
        // Iterating i from 1 till vertices
        for ( int i = 1 ; i <= vertices; i++) {
            // Adding them to a new LinkedList
            adjacentList.put(i, new LinkedList<Integer>());
        }
    }
    // We are now declaring a class edge
    // It has two parameters start and end
    public void set_Edge( int end, int start)
    {
        // We will write the condition for checking
        // If the the vertices are empty
        if (end > adjacentList.size()
            || start > adjacentList.size())
            System.out.println( "There are no vertices" ); 
        // Now if the input isn't zero
        // We will add them to a new list
        List<Integer> fls = adjacentList.get(start);
        fls.add(end);
    }
    // We created a list function called get edge
    // Help us to return the edges of a Graph
    public List<Integer> get_Edge( int end)
    {
        // Returning the edges back
        return adjacentList.get(end);
    }
    // Now let us check
    public Edge check()
    {
        // Now let us keep the count as 0
        Integer count = 0 ; 
        // Let us iterator for easy function
        Iterator<Integer> iterator
            = this .adjacentList.keySet().iterator(); 
        // Let us take a size variable of adjacent List
        Integer size = this .adjacentList.size() - 1 ; 
        // Iterating it till the end of the loop
        while (iterator.hasNext()) { 
            // Now taking the variable which is an iterator
            Integer i = iterator.next();
            // Declaring a new list adjlist
            List<Integer> adjList
                = this .adjacentList.get(i); 
            // checking for equal size we would return the
            // same
            if (count == size) {
                return this ;
            }
            // Now keeping the condition adjList==0
            if (adjList.size() == 0 ) { 
                // Every time we run the if
                // we increase the count
                count++;
                // Now taking an iterator Right
                Iterator<Integer> iteratorR
                    = this .adjacentList.keySet().iterator(); 
                // Again iterating completely over the new
                // Iterator
                while (iteratorR.hasNext()) { 
                    // Having the new R , help us to iterate
                    // the new Iterator
                    Integer R = iteratorR.next();
                    // New List is taken
                    List<Integer> lit
                        = this .adjacentList.get(R); 
                    // This if condition will help not to
                    // have
                    // Any duplicate values inside the new
                    // List
                    if (lit.contains(i)) {
                        // If we have one we would remove it
                        lit.remove(i);
                    }
                }
                // The below line would help us to remove
                // the values
                // Of the adjacent List as we move on to
                // make the vertices
                // The other values are simultaneously
                // removed.
                this .adjacentList.remove(i); 
                iterator
                    = this .adjacentList.keySet().iterator();
            }
        }
        return this ;
    }
    // This function helps us to print a graph
    public void printGraph() 
    {
        System.out.println( "The Graph is:" ); 
        // Now let us taken an iterator and try to print it
        // This iterator contains the values of the new
        // graph
        Iterator<Integer> iterator
            = this .adjacentList.keySet().iterator(); 
        // Now iterating the values
        while (iterator.hasNext()) 
        {
            // taking the variable i to be the next Iterator
            Integer i = iterator.next();
            // Taking a list which will help us have the
            // side edges.
            List<Integer> edgeList = this .get_Edge(i); 
            // Now checking the edge list if it is not zero
            if (edgeList.size() != 0 ) 
            {
                // print them out
                System.out.print(i);
                // now iterating it till edgelist
                for ( int j = 0 ; j < edgeList.size(); j++) 
                {
                    // Now printing the graph in its pattern
                    System.out.print( "-> "
                                     + edgeList.get(j));
                }
                System.out.println();
            }
        }
    }
    // Closing the function
    // Now finding the FeedbackArc set
    public boolean getFeedbackArcSet( int vertices) 
    {
        // Taking boolean flag false
        boolean flag = false ; 
        // Now taking visited array
        // This array length is vertices+1
        int [] visited = new int [vertices + 1 ]; 
        // This iterator has values of adjacent list
        Iterator<Integer> iterator
            = this .adjacentList.keySet().iterator(); 
        // Now let us see the feedback arc
        System.out.print(
            "The set of edges in FeedBack arc set: " ); 
        // Now it has iterator which is next
        while (iterator.hasNext()) 
        {
            // Now taking i which will be iterating next
            Integer i = iterator.next();
            // Now taking a list of values adjacent list
            List<Integer> list = this .adjacentList.get(i); 
            // Visited array to be after i
            visited[i] = 1 ; 
            // Now taking if the list size not equal to 0
            if (list.size() != 0 ) 
            {
                // We iterate till list sie
                for ( int j = 0 ; j < list.size(); j++) 
                {
                    // If we have visited the list
                    // e will flag it to be true
                    if (visited[list.get(j)] == 1 ) 
                    {
                        flag = true ; 
                        // Now taking the output of feedback
                        // arc
                        System.out.println(i + " - "
                                           + list.get(j));
                    }
                    else
                    {
                        // Now if we dint visit
                        // We will be iterating it to 1
                        visited[list.get(j)] = 1 ;
                    }
                }
            }
        }
        // Return the flag
        flag; return
    }
 }
 // Now let us declare the class GFG
 class GFG { 
    public static void main(String[] args)
    {
        // Now let us declare and initialize all the
        // variables
        int vertices = 4 , e = 5 , count = 1 ;
        int [] start = { 1 , 2 , 3 , 4 , 1 };
        int [] end = { 2 , 3 , 4 , 1 , 3 }; 
        // Now let us see the object of the class
        Edge ist;
        // Now let us try the exception.
        try
        {
            // printing both the values
            System.out.println( "Number of vertices: "
                               + vertices);
            System.out.println( "Number of edges: " + e); 
            // Now calling the function
            ist = new Edge(vertices); 
            // calling the function by iterating the loop
            for ( int i = 0 ; i < e; i++) 
            {
                // Now calling the function set_edge
                ist.set_Edge(end[i], start[i]);
            }
            // Now we are calling the print Graph Function
            ist.printGraph();
            // Now we will call the object of class
            // and then we called the function check
            Edge modified = ist.check();
            // If we dont get the flag to be true
            // We can print the output to be None or empty
            if (modified.getFeedbackArcSet(vertices)
                == false ) 
            {
                System.out.println( "None" );
            }
        }
        // Try for catch
        // We print empty nodes
        catch (Exception E) 
        {
            System.out.println( "Empty Nodes" );
        }
    }
 }

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

Technical Scripter Picked Java

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

Ява

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