На нашем сайте мы используем cookie для сбора информации технического характера и обрабатываем IP-адрес вашего местоположения. Продолжая использовать этот сайт, вы даете согласие на использование файлов cookies. Здесь вы можете узнать, как мы пользуемся файлами cookies.
Я согласен
логотип upread.ru

Поиск клик графа по алгоритму Брона-Кербоша на C#


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

Текстовый файл вот такого формата:



Первая строка размерность матрицы, остальные - единицы и нули. В готовом проекте идет несколько файлов с примерами



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

По сути здесь всего два основных части: метод FindAllCliques() для поиска клик и вложенный класс VertexMatrix. В FindAllCliques() мы создаем несколько списков List: для вершин, образующих клику, для вершин графа, для «отработанных вершин» и список несмежных с вершиной вершин.

Также используются три подметода.
  • SubtractSet(List<int> set, int vert) - вычитает вершину из множества.
  • SubtractSet(List<int> set1, List<int> set2) - вычитает второе множество из первого
  • List<int> G(int vert) – возвращает список вершин, не смежных с vert
Класс VertexMatrix кроме геттеров и сеттеров имеет два поля: размерность матрицы и непосредственно саму матрицу (двумерный массив). А также метод заполнения второго поля чтением из файла:

public int[,] ReadGraphFromFile(string filename)
        {
            List<string> input = File.ReadAllText(filename).Replace("\r\n", "\n").Replace(" \n", "\n").Split('\n').ToList();
            int size = Convert.ToInt32(input[0]);
            input.RemoveAt(0);
            int i = 0, j = 0;

            int[,] result = new int[size, size];
            foreach (var row in input)
            {
                j = 0;
                foreach (var col in row.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries))
                {
                    result[i, j] = int.Parse(col.Trim());
                    j++;
                }
                i++;
            }
            return (int[,])result.Clone();
        }
После выбора файла и нажатия «Go» в каждой строке текстбокса будет клика



В тексте программы имеются комментарии. Полный код с исходниками вы можете заказать у меня. Уточняйте актуальную стоимость в личке.



Автор этого материала - я - Пахолков Юрий. Я оказываю услуги по написанию программ на языках Java, C++, C# (а также консультирую по ним) и созданию сайтов. Работаю с сайтами на CMS OpenCart, WordPress, ModX и самописными. Кроме этого, работаю напрямую с JavaScript, PHP, CSS, HTML - то есть могу доработать ваш сайт или помочь с веб-программированием. Пишите сюда.



тегизаметки, си шарп, алгоритмы

Читайте также:




Пошаговое руководство по верстке на вордпресс. Глава третья: меню, страницы и шапка
Шаблонизатор Smarty и PHP, или пробуем смотреть на проблему шире


© upread.ru 2013-2020
При перепечатке активная ссылка на сайт обязательна.
Задать вопрос
письмо
Здравствуйте! Вы можете задать мне любой вопрос. Если не получается отправить сообщение через эту форму, то пишите на почу up777up@yandex.ru
Отправляя сообщение я подтверждаю, что ознакомлен и согласен с политикой конфиденциальности данного сайта.