Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/4: Рейтинг темы: голосов - 4, средняя оценка - 5.00
kitiket22
1 / 1 / 0
Регистрация: 31.01.2013
Сообщений: 4
#1

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

31.01.2013, 15:38. Просмотров 733. Ответов 3
Метки нет (Все метки)

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

Найти путь, соединяющий вершины a и b и не проходящий через заданное подмножество вершин V
Уффф, к завтрашнему дню нужно сдать эти задачи, помогите пожалуйста кто чем...

Из заданного множества int чисел определить максимальное подмножество
Была поставлена задача: &quot;Из заданного множества int чисел определить...

Найти диаметр графа, то есть, максимальное значение среди всех кратчайших расстояний между каждой парой вершин
Найти диаметр графа, то есть максимальное значение среди всех кратчайших...

Максимальное множество вершин графа
Алгоритм Брона-Кербоша на СИ. Нахождение максимального независимого множества...

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

3
kitiket22
1 / 1 / 0
Регистрация: 31.01.2013
Сообщений: 4
18.02.2013, 21:04  [ТС] #2
Тема актуальна
0
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;
}
1
ChuckNorris
2 / 2 / 1
Регистрация: 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;
}

как здесь вывести граф в форме матрицы? напишите пожалуйста
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.06.2013, 16:55

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

найти в массиве наибольшее подмножество...
задача: Найти в массиве натуральных чисел самое большое подмножество...

Дана последовательность целых чисел, за которой следует 0. Найти количество элементов этой последовательности, кратных числу K1 и не кратных числу K2
Ребята помогите пожалуйста решить 2 задачи с помощью цикла do и while. (без...


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

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

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