Форум программистов, компьютерный форум CyberForum.ru

Найти максимальное по числу вершин подмножество - C++

Восстановить пароль Регистрация
 
kitiket22
1 / 1 / 0
Регистрация: 31.01.2013
Сообщений: 4
31.01.2013, 15:38     Найти максимальное по числу вершин подмножество #1
Задали сделать прогу на C++ собственно вот задача:
Найти максимальное по числу вершин подмножество попарно несмежных вершин заданного графа (cn<=10 вершинами)
Юзал поиск, ответов в темах не нашёл...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.01.2013, 15:38     Найти максимальное по числу вершин подмножество
Посмотрите здесь:

C++ найти в массиве наибольшее подмножество...
C++ Максимальное множество вершин графа
Дана последовательность целых чисел, за которой следует 0. Найти количество элементов этой последовательности, кратных числу K1 и не кратных числу K2 C++
Найти подмножество множества C++
Найти количество элементов этой последовательности, кратных числу K1 и не кратных числу K2 C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
kitiket22
1 / 1 / 0
Регистрация: 31.01.2013
Сообщений: 4
18.02.2013, 21:04  [ТС]     Найти максимальное по числу вершин подмножество #2
Тема актуальна
kitiket22
1 / 1 / 0
Регистрация: 31.01.2013
Сообщений: 4
10.05.2013, 20:16  [ТС]     Найти максимальное по числу вершин подмножество #3
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include "stdafx.h"
#include <iostream>
#include <conio.h>
using namespace std;
struct Bow
{
    int vertex1, vertex2;
};
int** AdjMatrix(Bow *Bows, int BowNumber, int VertexNumber)
{
    int **AdjMatr = new int*[VertexNumber];     
 
    for(int i = 0; i < VertexNumber; i++)
        AdjMatr[i] = new int[VertexNumber];     
    for( int i = 0; i <  VertexNumber; i++)
        for( int j = 0; j < VertexNumber; j++)
            AdjMatr[i][j] = 0;                  
    for( int i = 0; i < BowNumber; i++)         
    {
        AdjMatr[ Bows[i].vertex1 - 1][Bows[i].vertex2 - 1] = 1;         AdjMatr[ Bows[i].vertex2 - 1][Bows[i].vertex1 - 1] = 1; 
    }
                                                
return AdjMatr;
};
 
Bow* FindunAdj(Bow *Bows, int BowNumber, int VertexNumber, int *count)
{
    int maxnumb = VertexNumber*( VertexNumber - 1 )/2;  
    *count = 0;                                         
    Bow *temp =  new Bow[maxnumb];                      
 
    int** AdjMatr = AdjMatrix(Bows, BowNumber, VertexNumber);   
 
    for ( int i = 0; i < VertexNumber; i++)
        for( int j = i + 1; j < VertexNumber; j++)
            if ( AdjMatr[i][j] != 1 )   
            {
                temp[*count].vertex1 = i + 1;
                temp[*count].vertex2 = j + 1;
                (*count)++;
            }
    Bow* UnAdj =  (Bow*) realloc (temp, *count * sizeof(Bow));  
    return UnAdj;
};
 
int _tmain(int argc, _TCHAR* argv[])
{
    int BowNumber, VertexNumber; 
    Bow *Bows;  
 
    printf("Vvedite kol-vo vershin.\n");
    scanf("%d", &VertexNumber);         
    printf("Vvedite kol-vo dug.\n");
    scanf("%d", &BowNumber);                
    Bows = new Bow[BowNumber];              
    printf("Vvedite dugi\n");
    for ( int j = 0; j < BowNumber; j++)    
    {
        do
        {
            printf( "Duga %d\n", j + 1);
            printf("Vvedite nachalnuu i konechnuu vershinu\n");
            scanf("%d %d", &Bows[j].vertex1, &Bows[j].vertex2); //      }
        while ( !( ( Bows[j].vertex1 <= VertexNumber )  && ( Bows[j].vertex2 <= VertexNumber )  && ( Bows[j].vertex1 > 0 )  && ( Bows[j].vertex2 > 0 ) ) );
    }
    
    printf("V grafe %d vershin i %d dug\n", VertexNumber, BowNumber);
    for ( int j = 0; j < BowNumber; j++ )   // 
    {
        printf("Duga %d { %d, %d }\n", j + 1, Bows[j].vertex1, Bows[j].vertex2);
    }
    int count;                                  Bow *UnAdj = FindunAdj(Bows, BowNumber, VertexNumber, &count);  for( int i = 0; i < count; i++)
        printf("Para 1 { %d, %d }\n", UnAdj[i].vertex1, UnAdj[i].vertex2); 
    delete[](UnAdj);
    getch();
    return 0;
}
Добавлено через 6 часов 23 минуты
С описанием
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// lab1.cpp: определяет точку входа для консольного приложения.
//
 
#include "stdafx.h"
#include <iostream>
#include <conio.h>
using namespace std;
// структура Bow состоит из двух целых чисел vertex1 и vertex2
struct Bow
{
    int vertex1, vertex2;
};
//Создание матрици смежности. Входные параметры: дин.массив дуг, кол-во дуг, и вол-во вешин
//Возвращает дин. двумерный массив (матрицу) определяющий граф, т.к. граф - динамический, то и 
//матрица динамическая и возвращается указатель на неё.
int** AdjMatrix(Bow *Bows, int BowNumber, int VertexNumber)
{
    int **AdjMatr = new int*[VertexNumber];     //Выделение памяти для строк
    for(int i = 0; i < VertexNumber; i++)
        AdjMatr[i] = new int[VertexNumber];     //Выделение памяти столбцов
    for( int i = 0; i <  VertexNumber; i++)
        for( int j = 0; j < VertexNumber; j++)
            AdjMatr[i][j] = 0;                  //Изначально она заполняется нулями
    for( int i = 0; i < BowNumber; i++)         //Создается матрица смежности. Если есть дуга от а до b, то в [a,b] ставится еденица
    {
        AdjMatr[ Bows[i].vertex1 - 1][Bows[i].vertex2 - 1] = 1; // Заполнение матрицы.
        AdjMatr[ Bows[i].vertex2 - 1][Bows[i].vertex1 - 1] = 1; //Вычитается единица из-за особенностей работы С++ с матрицами,
    }                                           // итерация идет с 0 по BowNumber - 1 элемент
    return AdjMatr;
};
//Изначально не известно сколько всего искомых пар елементов, поэтому берется максимально возможное значение
//Во входных параметрах подается указатель на интовое число, в него запишется кол-во найденых пар элементов
// а, так как обращение идет по адресу, то значение не потеряется после выполнения функции
//Когда все пары найдены, происходит перевыделение памяти и часть освобождается
Bow* FindunAdj(Bow *Bows, int BowNumber, int VertexNumber, int *count)
{
    int maxnumb = VertexNumber*( VertexNumber - 1 )/2;  // Для нахождения нужных вершин нужно обработать только половину матрицы
    *count = 0;                                         // Так, как матрица симметрицна относительно диагонали
    Bow *temp =  new Bow[maxnumb];                      // Так как изначально неизвестно сколько искомых вешин, выделяется память на максимально их число
    int** AdjMatr = AdjMatrix(Bows, BowNumber, VertexNumber);   //Это число является треугольным и вычисляется по формуле n*(n + 1)/2;
    for ( int i = 0; i < VertexNumber; i++)
        for( int j = i + 1; j < VertexNumber; j++)
            if ( AdjMatr[i][j] != 1 )   //если не смежно не равно 1
            {
                temp[*count].vertex1 = i + 1;
                temp[*count].vertex2 = j + 1;
                (*count)++;
            }
    Bow* UnAdj =  (Bow*) realloc (temp, *count * sizeof(Bow));  //Вперевыделяестя память с освобождение лишней памяти
    return UnAdj;
};
 
int _tmain(int argc, _TCHAR* argv[])
{
    int BowNumber, VertexNumber; // Содержит кол-во дуг и вершин для каждого графа ( Bow - дуга, Vertex - вершина )
    Bow *Bows;  // Заранее не известно какого размера граф, поэтому память выделяется динамически в дин. массив структуры Bow (структура Bow описана выше)
                                    // Ввод начальных данных
    printf("Vvedite kol-vo vershin.\n");
    scanf("%d", &VertexNumber);         // Кол-во вершин
    printf("Vvedite kol-vo dug.\n");
    scanf("%d", &BowNumber);                // Кол-во дуг
    Bows = new Bow[BowNumber];              // Выделение памяти под массив дуг
    printf("Vvedite dugi\n");
    for ( int j = 0; j < BowNumber; j++)    // Ввод
    {
        do
        {
            printf( "Duga %d\n", j + 1);
            printf("Vvedite nachalnuu i konechnuu vershinu\n");
            scanf("%d %d", &Bows[j].vertex1, &Bows[j].vertex2); // Вводятся 2 числа начала и конца дуги
        }//Защита от дурака: проверяется введены ли такие значения, которые пренадлежат множеству вешин. Множество вершин {1, ..., VertexNumber }
        while ( !( ( Bows[j].vertex1 <= VertexNumber )  && ( Bows[j].vertex2 <= VertexNumber )  && ( Bows[j].vertex1 > 0 )  && ( Bows[j].vertex2 > 0 ) ) );
    }
    // Вывод всех введённых данных
    printf("V grafe %d vershin i %d dug\n", VertexNumber, BowNumber);
    for ( int j = 0; j < BowNumber; j++ )   // Zapusk cikla
    {
        printf("Duga %d { %d, %d }\n", j + 1, Bows[j].vertex1, Bows[j].vertex2);
    }
    int count;                              // Создается счетчик найденых пар, его адрес передается в функции FindAdj и все изменения в ней произошедшис с count сохранятся
    Bow *UnAdj = FindunAdj(Bows, BowNumber, VertexNumber, &count); //Выполнение функции поиска нужных вершин
    for( int i = 0; i < count; i++)
        printf("Para 1 { %d, %d }\n", UnAdj[i].vertex1, UnAdj[i].vertex2); // Вывод найденых пар
    delete[](UnAdj);
    getch();
    return 0;
}
ChuckNorris
2 / 2 / 0
Регистрация: 25.10.2012
Сообщений: 42
03.06.2013, 16:55     Найти максимальное по числу вершин подмножество #4
Цитата Сообщение от kitiket22 Посмотреть сообщение
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include "stdafx.h"
#include <iostream>
#include <conio.h>
using namespace std;
struct Bow
{
    int vertex1, vertex2;
};
int** AdjMatrix(Bow *Bows, int BowNumber, int VertexNumber)
{
    int **AdjMatr = new int*[VertexNumber];     
 
    for(int i = 0; i < VertexNumber; i++)
        AdjMatr[i] = new int[VertexNumber];     
    for( int i = 0; i <  VertexNumber; i++)
        for( int j = 0; j < VertexNumber; j++)
            AdjMatr[i][j] = 0;                  
    for( int i = 0; i < BowNumber; i++)         
    {
        AdjMatr[ Bows[i].vertex1 - 1][Bows[i].vertex2 - 1] = 1;         AdjMatr[ Bows[i].vertex2 - 1][Bows[i].vertex1 - 1] = 1; 
    }
                                                
return AdjMatr;
};
 
Bow* FindunAdj(Bow *Bows, int BowNumber, int VertexNumber, int *count)
{
    int maxnumb = VertexNumber*( VertexNumber - 1 )/2;  
    *count = 0;                                         
    Bow *temp =  new Bow[maxnumb];                      
 
    int** AdjMatr = AdjMatrix(Bows, BowNumber, VertexNumber);   
 
    for ( int i = 0; i < VertexNumber; i++)
        for( int j = i + 1; j < VertexNumber; j++)
            if ( AdjMatr[i][j] != 1 )   
            {
                temp[*count].vertex1 = i + 1;
                temp[*count].vertex2 = j + 1;
                (*count)++;
            }
    Bow* UnAdj =  (Bow*) realloc (temp, *count * sizeof(Bow));  
    return UnAdj;
};
 
int _tmain(int argc, _TCHAR* argv[])
{
    int BowNumber, VertexNumber; 
    Bow *Bows;  
 
    printf("Vvedite kol-vo vershin.\n");
    scanf("%d", &VertexNumber);         
    printf("Vvedite kol-vo dug.\n");
    scanf("%d", &BowNumber);                
    Bows = new Bow[BowNumber];              
    printf("Vvedite dugi\n");
    for ( int j = 0; j < BowNumber; j++)    
    {
        do
        {
            printf( "Duga %d\n", j + 1);
            printf("Vvedite nachalnuu i konechnuu vershinu\n");
            scanf("%d %d", &Bows[j].vertex1, &Bows[j].vertex2); //      }
        while ( !( ( Bows[j].vertex1 <= VertexNumber )  && ( Bows[j].vertex2 <= VertexNumber )  && ( Bows[j].vertex1 > 0 )  && ( Bows[j].vertex2 > 0 ) ) );
    }
    
    printf("V grafe %d vershin i %d dug\n", VertexNumber, BowNumber);
    for ( int j = 0; j < BowNumber; j++ )   // 
    {
        printf("Duga %d { %d, %d }\n", j + 1, Bows[j].vertex1, Bows[j].vertex2);
    }
    int count;                                  Bow *UnAdj = FindunAdj(Bows, BowNumber, VertexNumber, &count);  for( int i = 0; i < count; i++)
        printf("Para 1 { %d, %d }\n", UnAdj[i].vertex1, UnAdj[i].vertex2); 
    delete[](UnAdj);
    getch();
    return 0;
}
Добавлено через 6 часов 23 минуты
С описанием
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// lab1.cpp: определяет точку входа для консольного приложения.
//
 
#include "stdafx.h"
#include <iostream>
#include <conio.h>
using namespace std;
// структура Bow состоит из двух целых чисел vertex1 и vertex2
struct Bow
{
    int vertex1, vertex2;
};
//Создание матрици смежности. Входные параметры: дин.массив дуг, кол-во дуг, и вол-во вешин
//Возвращает дин. двумерный массив (матрицу) определяющий граф, т.к. граф - динамический, то и 
//матрица динамическая и возвращается указатель на неё.
int** AdjMatrix(Bow *Bows, int BowNumber, int VertexNumber)
{
    int **AdjMatr = new int*[VertexNumber];     //Выделение памяти для строк
    for(int i = 0; i < VertexNumber; i++)
        AdjMatr[i] = new int[VertexNumber];     //Выделение памяти столбцов
    for( int i = 0; i <  VertexNumber; i++)
        for( int j = 0; j < VertexNumber; j++)
            AdjMatr[i][j] = 0;                  //Изначально она заполняется нулями
    for( int i = 0; i < BowNumber; i++)         //Создается матрица смежности. Если есть дуга от а до b, то в [a,b] ставится еденица
    {
        AdjMatr[ Bows[i].vertex1 - 1][Bows[i].vertex2 - 1] = 1; // Заполнение матрицы.
        AdjMatr[ Bows[i].vertex2 - 1][Bows[i].vertex1 - 1] = 1; //Вычитается единица из-за особенностей работы С++ с матрицами,
    }                                           // итерация идет с 0 по BowNumber - 1 элемент
    return AdjMatr;
};
//Изначально не известно сколько всего искомых пар елементов, поэтому берется максимально возможное значение
//Во входных параметрах подается указатель на интовое число, в него запишется кол-во найденых пар элементов
// а, так как обращение идет по адресу, то значение не потеряется после выполнения функции
//Когда все пары найдены, происходит перевыделение памяти и часть освобождается
Bow* FindunAdj(Bow *Bows, int BowNumber, int VertexNumber, int *count)
{
    int maxnumb = VertexNumber*( VertexNumber - 1 )/2;  // Для нахождения нужных вершин нужно обработать только половину матрицы
    *count = 0;                                         // Так, как матрица симметрицна относительно диагонали
    Bow *temp =  new Bow[maxnumb];                      // Так как изначально неизвестно сколько искомых вешин, выделяется память на максимально их число
    int** AdjMatr = AdjMatrix(Bows, BowNumber, VertexNumber);   //Это число является треугольным и вычисляется по формуле n*(n + 1)/2;
    for ( int i = 0; i < VertexNumber; i++)
        for( int j = i + 1; j < VertexNumber; j++)
            if ( AdjMatr[i][j] != 1 )   //если не смежно не равно 1
            {
                temp[*count].vertex1 = i + 1;
                temp[*count].vertex2 = j + 1;
                (*count)++;
            }
    Bow* UnAdj =  (Bow*) realloc (temp, *count * sizeof(Bow));  //Вперевыделяестя память с освобождение лишней памяти
    return UnAdj;
};
 
int _tmain(int argc, _TCHAR* argv[])
{
    int BowNumber, VertexNumber; // Содержит кол-во дуг и вершин для каждого графа ( Bow - дуга, Vertex - вершина )
    Bow *Bows;  // Заранее не известно какого размера граф, поэтому память выделяется динамически в дин. массив структуры Bow (структура Bow описана выше)
                                    // Ввод начальных данных
    printf("Vvedite kol-vo vershin.\n");
    scanf("%d", &VertexNumber);         // Кол-во вершин
    printf("Vvedite kol-vo dug.\n");
    scanf("%d", &BowNumber);                // Кол-во дуг
    Bows = new Bow[BowNumber];              // Выделение памяти под массив дуг
    printf("Vvedite dugi\n");
    for ( int j = 0; j < BowNumber; j++)    // Ввод
    {
        do
        {
            printf( "Duga %d\n", j + 1);
            printf("Vvedite nachalnuu i konechnuu vershinu\n");
            scanf("%d %d", &Bows[j].vertex1, &Bows[j].vertex2); // Вводятся 2 числа начала и конца дуги
        }//Защита от дурака: проверяется введены ли такие значения, которые пренадлежат множеству вешин. Множество вершин {1, ..., VertexNumber }
        while ( !( ( Bows[j].vertex1 <= VertexNumber )  && ( Bows[j].vertex2 <= VertexNumber )  && ( Bows[j].vertex1 > 0 )  && ( Bows[j].vertex2 > 0 ) ) );
    }
    // Вывод всех введённых данных
    printf("V grafe %d vershin i %d dug\n", VertexNumber, BowNumber);
    for ( int j = 0; j < BowNumber; j++ )   // Zapusk cikla
    {
        printf("Duga %d { %d, %d }\n", j + 1, Bows[j].vertex1, Bows[j].vertex2);
    }
    int count;                              // Создается счетчик найденых пар, его адрес передается в функции FindAdj и все изменения в ней произошедшис с count сохранятся
    Bow *UnAdj = FindunAdj(Bows, BowNumber, VertexNumber, &count); //Выполнение функции поиска нужных вершин
    for( int i = 0; i < count; i++)
        printf("Para 1 { %d, %d }\n", UnAdj[i].vertex1, UnAdj[i].vertex2); // Вывод найденых пар
    delete[](UnAdj);
    getch();
    return 0;
}

как здесь вывести граф в форме матрицы? напишите пожалуйста
Yandex
Объявления
03.06.2013, 16:55     Найти максимальное по числу вершин подмножество
Ответ Создать тему
Опции темы

Текущее время: 08:49. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru