Как создать случайный неориентированный граф для заданного числа ребер в Java?

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

Ненаправленный граф - это граф, то есть набор объектов (называемых вершинами или узлами), которые соединены вместе, причем все ребра двунаправлены. Ненаправленный граф иногда называют неориентированной сетью. Напротив, граф, в котором ребра указывают в направлении, называется ориентированным графом.

Ненаправленный граф: двунаправленный

Примеры:

 Вход:
Введите количество кромок:
5
Выход:
Сгенерированный случайный график:
1 -> {5 2}
2 -> {1}
3 -> {Изолированная вершина! }      
4 -> {6}
5 -> {1}
6 -> {4 10}
7 -> {Изолированная вершина! }      
8 -> {10}
9 -> {Изолированная вершина! }      
10 -> {8 6}

Вход:
Введите количество кромок:
10
Выход:
Сгенерированный случайный график:
1 -> {4 9}
2 -> {8}
3 -> {8}
4 -> {1 6}
5 -> {6}
6 -> {10 5 8 9 4}
7 -> {8}
8 -> {7 3 6 2}
9 -> {1 6}
10 -> {6}

Подход:

Введите количество ребер для случайного Направленного ациклического графа.
Итеративно выстраивайте связь между двумя случайными вершинами.
Утверждать «изолированную вершину», если степень некоторой вершины равна нулю.

Implementation:

Java

// Java program to Generate a Random Undirected Graph
// for a GivenNumber of Edges
 
// importing generic packages
import java.util.*;
import java.util.Random;
 
public class RandomUG {
    static int maxVertex = 10;
 
    // Function to generate random graph
    public static void generateRandomGraphs(int e)
    {
        int i = 0, j = 0, count = 0;
 
        int[][] edge = new int[e][2];
        Random rand = new Random();
 
        // Build a connection between two random vertex
        while (i < e) {
            edge[i][0] = rand.nextInt(maxVertex) + 1;
            edge[i][1] = rand.nextInt(maxVertex) + 1;
 
            // using rand to pick a random integer in range
            // of (1 - maxVertex)
            i++;
        }
 
        System.out.println(
            "The Generated Random Graph is :");
 
        // Print the Graph
        for (i = 0; i < maxVertex; i++) {
            count = 0;
 
            System.out.print((i + 1) + " -> { ");
 
            for (j = 0; j < e; j++) {
                if (edge[j][0] == i + 1) {
                    System.out.print(edge[j][1] + " ");
                    count++;
                }
 
                else if (edge[j][1] == i + 1) {
                    System.out.print(edge[j][0] + " ");
                    count++;
                }
 
                // print “Isolated vertex” for the vertex
                // having zero degree.
                else if (j == e - 1 && count == 0)
                    System.out.print("Isolated Vertex!");
            }
            System.out.print(" }
");
        }
    }
 
    public static void main(String args[]) throws Exception
    {
        int e = 6;
        System.out.println("Enter the number of Edges : " +e);
 
        // Function to generate a Random unDirected Graph
        generateRandomGraphs(e);
    }
}

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

Picked Java

Как создать случайный неориентированный граф для заданного числа ребер в Java?

Java

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