Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Помогите написать программу в С. Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств Сам метод: Клика Антиподом понятия независимого множества является понятие клики. Подмножество U вершин графа G называется кликой, если любые две входящие в него вершины смежны, т.е. если порожденный подграф G(U) является полным. Клика называется максимальной, если она не содержится в клике с большим числом вершин, и наибольшей, если число вершин в ней наибольшее среди всех клик. Число вершин в наибольшей клике графа G называется его плот-ностью (или кликовым числом) и обозначается через (G). Как и в случае независимых множеств, максимальная клика графа может оказаться не наибольшей. Понятие клики, в частности максимальной клики, используется в различных социологических теориях ( вопросы, связанные с голосованием, альянсами и т.п.), а также в теории игр. Очевидно следующее утверждение: подмножество вершин графа G является кликой тогда и только тогда, когда оно является независимым множеством в дополнительном графе G*. Вот то, что я начал писать:
#include <stdio.h>
#include <conio.h>
 
#define M 120
 
int n, g[M][M], f[M][M];
int main()
{
    printf("Vvedite n= %d", n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            printf("%d", g[i][j]);
 
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &g[i][j]);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (g[i][j] == 0)
                g[i][j] = 1;
            else
                g[i][j] = 0;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            printf(" %d \n", g[i][j]);
 
    getch();
 
    return 0;
}

Решение задачи: «Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств»

textual
Листинг программы
#include <stdio.h>
#include <conio.h>
 
#define M 120
 
int n,g[M][M],Res[M], N_res, Q[M], i_end;
 
void rec(int ii, int N)
{
    int i, j;
    if(N>N_res)
    {
        for(i=0; i<i_end; i++)
            Res[i]=Q[i];
        N_res=N;
    }
    if(ii==n)
        return;
    for(i=ii; i<n; i++)
    {       
        for(j=0; j<i_end; j++)
            if(g[Q[j]][i]==0)
                break;
        if(j==i_end)
        {
            Q[i_end++]=i;
            rec(ii+1, N+1);
            i_end--;
        }
        rec(ii+1, N);
    }
}
 
int main()
{
 printf("Vvedite n= ",n);
 scanf("%d",&n);
 int i;
 for(i=0;i<n;i++)
     for(int j=0;j<n;j++)
         scanf("%d",&g[i][j]);   
for(i=0;i<n;i++)
    for(int j=0;j<n;j++)
        if (g[i][j]==1) g[j][i]=1;
for(i=0;i<n;i++)
{
    for(int j=0;j<n;j++)
        printf(" %d",g[i][j]);
    printf("\n");
}
for(i=0; i<n; i++)
{
    i_end=0; 
    rec(i, 0);
}
printf("Max klik:\n");
for(i=0; i<N_res; i++)
    printf("%d ", Res[i]);
getch();
return 0;
}

Объяснение кода листинга программы

В этом коде реализован алгоритм поиска наибольшей независимой множества подмножеств, используя язык программирования C. Список действий, которые выполняются в коде:

  1. Ввод данных: Вводится значение переменной n, которое представляет собой количество вершин в графе. Затем, с помощью цикла, вводятся значения матрицы g, представляющей собой граф.
  2. Обработка графа: В этом блоке кода матрица g заполняется значениями, соответствующими верхней треугольной части матрицы. Это делается для удобства работы с алгоритмом поиска независимых множеств.
  3. Вывод матрицы g: С помощью цикла и функции printf выводятся значения матрицы g. Это делается для проверки входных данных.
  4. Реализация алгоритма поиска наибольшей независимой множества: Этот блок кода реализует рекурсивную функцию rec, которая ищет наибольшую независимую множества.
  5. Вывод результата: С помощью цикла и функции printf выводятся значения наибольшей независимой множества.
  6. Ввод-вывод: В этом блоке кода происходит ввод значения переменной n и вывод сообщения Max klik:.
  7. Завершение программы: Программа завершается с помощью функции getch, которая ожидает нажатия клавиши. Переменные, используемые в коде:
  8. n: Количество вершин в графе.
  9. g[i][j]: Значение (0 или 1) в матрице g, представляющей собой граф.
  10. Res[i]: Значение (вершина) из наибольшей независимой множества.
  11. N_res: Количество вершин в наибольшей независимой множества.
  12. Q[i]: Вершина, которую нужно рассмотреть в текущем подмножестве.
  13. i_end: Индекс последнего элемента в массиве Q.
  14. M: Размер матрицы g.

Оцени полезность:

12   голосов , оценка 4.5 из 5
Похожие ответы