Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Derby'
0 / 0 / 0
Регистрация: 29.05.2012
Сообщений: 2
#1

Построение максимальной клики графа - C (СИ)

01.06.2012, 18:31. Просмотров 908. Ответов 0
Метки нет (Все метки)

Всем привет. В поисках учебной задачи, наткнулся на что-то похожее. Но, к сожалению, не могу разобраться в коде. Знающие, поясните пожалуйста комментариями, что там происходит. Что есть "n" - ? Размерность матрицы связности? Почему иногда строки транспонируются? причем не все. Что за функция? Заранее спасибо.

Сам код:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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;
}
(Источник - http://www.cyberforum.ru/cpp-beginners/thread514478.html)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.06.2012, 18:31
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Построение максимальной клики графа (C (СИ)):

Перевод из С++ построение одного графа на основе другого
По графу G построить граф G’ следующим образом: в качестве вершин в G’ берутся...

Поиск максимальной клики на графе
Есть программа для поиска клик на графе, ввод структуры (списка)смежности в ней...

Разбиение графа на клики. Надо разобраться с кодом!
Здравствуйте,уважаемые форумчане. Пожалуй сразу перейду к проблеме. Я попросил...

Построение Графа
Добрый день. Имеется StringGrid 10x10. На основе его данных (т.е 0 или 1)...

Построение графа
Пожалуйста помогите. Для M={1,3,4,6} задать M*M графом отношение...

построение графа
Мне нужно построить ориентированый граф, который задаетса матрицей смежности,...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.06.2012, 18:31
Привет! Вот еще темы с решениями:

Построение графа на JS
Здравствуйте. Подскажите, пожалуйста, библиотеку на JS для построения графа....

построение графа
Задача: &quot;Задан граф дерево с корневой вершиной. Нужно, начиная с корневой...

Построение графа
Помогите пожалуйста написать программу вот задание:Построить копию заданного...

Построение графа
Помогите! есть матрица смежности с весом ребер, нужно по этой матрице строить...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru