Размещено на http://www.allbest.ru/

Алгоритм Каргера

Постановка задачи:

Алгоритм Каргера - это рандомизированный алгоритм для эффективного нахождения минимального разреза в связанном графе.

Я решила реализовать его через задачу поиска минимального разреза графа, написанную на языке Java. В виде таблицы смежности в текстовый файл пользователем задаётся исходный граф. Программа проводит нужные вычисления и выводит в консоль минимальный разрез графа.

Описание алгоритма:

Алгоритм Каргера - это вероятностный алгоритм в информатике и теории графов, позволяющий найти минимальный разрез связного графа. Сам алгоритм изобретен Девидом Каргером, опубликован в 1993 году. Идея данного алгоритма основана на стягивании ребра в неориентированном графе. Во время стягивания ребра происходит объединение двух вершин в одну, что уменьшает количество вершин графа на единицу. Все рёбра стягиваемых вершин соединяются со вновь образованной вершиной, порождая мультиграф. Алгоритм Каргера итеративно выбирает случайные рёбра и выполняет операцию до тех пор, пока не останется две вершины, которые и представляют собой разрез изначального графа. Если повторять алгоритм достаточное количество раз, то с высокой вероятностью может быть найден минимальный разрез.

Псевдокод:

повторить n ? 2 раза

выбрать случайно ребро e

стянуть ребро e

результат число рёбер между двумя последними вершинами

Пояснение к псевдокоду:

Для нахождения минимального разреза связного графа, алгоритм выбирает случайное ребро, стягивает две вершины этого ребра в одну вершину и повторяет это действие пока не останется две вершины. Количество рёбер между последними двумя вершинами и будет являться минимальным разрезом. Однако так как алгоритм Каргера является вероятностным алгоритмом, то его следует повторять большое количество раз для получение наиболее точного ответа.

Рис.1 Иллюстрация стягивания двух вершин ребра в одну.

Рис.2 Пошаговая иллюстрация работы алгоритма.

Реализация:

Листинг кода программы с комментариями:

package com.company;

import java.io.IOException;

import java.io.File;

import java.util.Random;

import java.util.HashMap;

import java.util.ArrayList;

import java.io.FileReader;

import java.io.BufferedReader;

public class Main {

public static int Karger(HashMap<Integer, ArrayList<Integer" database, ArrayList<Integer> tops)

{

//mark для сжатых ребер

int mark = database.size() + 1;

while (tops.size() > 2)//Перебираем граф, пока не останется 2 вершины

{

int numOfEdges = NumberOfEdges(database, tops); //Количество рёбер

int[][] edges = EdgesMatrix(numOfEdges, database, tops); //Определяем двумерный массив рёбер

Random rand = new Random();

int num = rand.nextInt(edges.length); //Случайно выбираем ребро графа

//Первая вершина случайного ребра

int top1 = edges[num][0];

//Вторая вершина случайного ребра

int top2 = edges[num][1];

ArrayList<Integer> arrayTop1 = database.get(top1);

ArrayList<Integer> arrayTop2 = database.get(top2);

arrayTop1.addAll(arrayTop2);

tops.remove((Integer) top2);

database.remove(top2);

// Присвоим top1 новую mark и меняем все mark вершины 1 или вершины 2 на новые

for (Integer top : tops) {

ArrayList<Integer> values = database.get(top);

for (int j = 0; j < values.size(); j++) {

if (values.get(j) == top1)

values.set(j, mark);

if (values.get(j) == top2)

values.set(j, mark);

}

}

//Изменим mark ключевого узла top1 в таблице смежности

ArrayList<Integer> values = database.get(top1);

database.remove(top1);

database.put(mark, values);

//Изменить mark top1 в вершинах массива ArrayList

int index = tops.indexOf(top1);

tops.set(index, mark);

//Удалим петли

int position = 0;

int length = database.get(mark).size();

while (position < length)

{

if(database.get(mark).get(position) == mark)

{

database.get(mark).remove(position);

length--;

}

else

position++;

}

mark++;

}

return database.get(tops.get(0)).size();

}

public static void ReadDataBase(HashMap<Integer, ArrayList<Integer" database, ArrayList<Integer> tops) throws IOException

{

File file = new File(System.getProperty("user.dir") + "/database.txt");

try (BufferedReader input = new BufferedReader(new FileReader(file))) {

String line = input.readLine();

while (line != null) {

String[] vector = line.split(" ");

int key = Integer.parseInt(vector[0]);

tops.add(key);

//Перевод строк файла в числа для списка рёбер

ArrayList<Integer> edges = new ArrayList<>();

for (int i = 0; i < vector.length - 1; i++)

if (Integer.parseInt(vector[i + 1]) != key)

edges.add(Integer.parseInt(vector[i + 1]));

//Сохраняем в "базу данных"(таблица смежности) значения полученные из фала

database.put(key, edges);

line = input.readLine();

}

}

}

public static void main(String[] arg) throws IOException

{

HashMap<Integer, ArrayList<Integer" database = new HashMap<>();

ArrayList<Integer> tops = new ArrayList<>();

ReadDataBase(database, tops);

//В начале основной минимум равен n * n, где n = колличество узлов в графе

int finalMinimum = database.size() * database.size();

for(int i = 0; i < database.size(); i++)

{

int minimumCut = Karger(database, tops);

int iTry = i+1;

System.out.println("Попытка номер " + iTry + ": " + minimumCut);

if(minimumCut < finalMinimum)

finalMinimum = minimumCut;

//Очищаем "базу данных"(таблицу смежности) и массив вершин

database.clear();

tops.clear();

ReadDataBase(database, tops);

}

System.out.println("\n Минимальный разрез: " + finalMinimum);

}

//Зная число рёбер графа, таблицу смежности и его вершины, определяем рёбра графа

public static int[][] EdgesMatrix(int numOfEdges, HashMap<Integer, ArrayList<Integer" database, ArrayList<Integer> tops)

{

int k = 0;

int[][] edges = new int[numOfEdges][2];

for (Integer top : tops) {

ArrayList<Integer> vector = database.get(top);

for (Integer integer : vector) {

edges[k][0] = top;

edges[k][1] = integer;

k++;

}

}

return edges;

}

//Зная таблицу смежности и вершины, определяем колличество рёбер графа

public static int NumberOfEdges(HashMap<Integer, ArrayList<Integer" database, ArrayList<Integer> tops)

{

int numOfEdges = 0;

for (Integer top : tops) {

ArrayList<Integer> vector = database.get(top);

numOfEdges += vector.size();

}

return numOfEdges;

}

}

Примеры работы программы:



Рис.3 Исходный граф, представленный в виде таблицы смежности в текстовом файле.

Рис.4 Вывод программы в консоль результатов 8 попыток использования алгоритма Каргера на исходном графе и вывод ответа - минимального разреза

Можно сравнить результат работы программы со своими собственными вычислениями (найти минимальный разрез графа любым другим способом). Ответ оказался верным, действительно минимальный разрез для исходного графа равен 2. программа код алгоритм

Вывод:

В данной работе я познакомилась с вероятностным алгоритмом Каргера, реализовав его на Java. Я использовала текстовый ввод графа в виде таблицы смежности и после вычислений программа вывела в консоль значение минимального разреза. Алгоритм довольно эффективный и простой в реализации.

Список использованной литературы

1. https://e-maxx.ru/algo/stoer_wagner_mincut

2. https://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B0%D1%80%D0%B3%D0%B5%D1%80%D0%B0_%D0%B4%D0%BB%D1%8F_%D0%BD%D0%B0%D1%85%D0%BE%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE_%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D0%B7%D0%B0

3. http://ru.knowledgr.com/04287640/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%9A%D0%B0%D1%80%D0%B3%D0%B5%D1%80%D0%B0

4. https://www.geeksforgeeks.org/kargers-algorithm-for-minimum-cut-set-1-introduction-and-implementation/

5. https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B0%D1%80%D0%B3%D0%B5%D1%80%D0%B0

6. https://medium.com/@dev.elect.iitd/kargers-algorithm-d8067eb1b790

Размещено на Allbest.ru

...