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

Графы - C++

Восстановить пароль Регистрация
 
Den UA
0 / 0 / 0
Регистрация: 23.06.2010
Сообщений: 9
12.07.2010, 13:47     Графы #1
Решается судьба степеньдии от этих задач, помогите пожалуйста.
1) Для неориентированого графа определить степени вершин. В случае равенства всех степеней , изменитьстепень равенства одной из них.
2) Для неориентированого графа удалить все вершины не смежные с данной.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.07.2010, 13:47     Графы
Посмотрите здесь:

Графы C++
C++ Графы
C++ Графы
C++ [C++] графы
C++ Графы
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
besstiaa
 Аватар для besstiaa
93 / 93 / 7
Регистрация: 04.06.2010
Сообщений: 223
12.07.2010, 17:56     Графы #2
С или С++?
Den UA
0 / 0 / 0
Регистрация: 23.06.2010
Сообщений: 9
13.07.2010, 10:43  [ТС]     Графы #3
Сильно не важно, но если можеш то на Си буду очень признателен
Den UA
0 / 0 / 0
Регистрация: 23.06.2010
Сообщений: 9
14.07.2010, 15:13  [ТС]     Графы #4
Так кто то может решить? В помощи нуждаюсь
Хохол
14.07.2010, 15:17
  #5

Не по теме:

Цитата Сообщение от Den UA Посмотреть сообщение
В случае равенства всех степеней , изменитьстепень равенства одной из них.
Просто любопытно, что такое степень равенства?

dxdy
 Аватар для dxdy
97 / 97 / 5
Регистрация: 14.06.2010
Сообщений: 283
14.07.2010, 15:40     Графы #6
Den UA Задачи из этой же серии я только недавно решал девушке , у которой тоже зависела от этой работы стипендия. Вы случайно не из одного универа?
Попробуй по аналогии сделать свою задачу. Неориентированный граф!!!
dxdy
 Аватар для dxdy
97 / 97 / 5
Регистрация: 14.06.2010
Сообщений: 283
14.07.2010, 16:03     Графы #7
В принципе мне в своем коде проще разобраться, там всего лишь надо добавить одну функцию, проверка массива на равенство для первого задания:
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <fstream>
using namespace std;
 
int ReadFile(char *name);
void IniMatrix(int **&Array, int n, int *&Check);
int *CheckMatrix(int **Array, int n, int *Check);
int PrintMatrix(int **Array, int n);
bool CheckRav(int *Check, int n);
 
int main(){
        ReadFile("test.txt");
        return 0;
}
 
//-----------------------
int ReadFile(char *name){
        ifstream in(name);
        if(!in){ cout <<"Error" << endl; return -1; }
 
        int n = 0;
        in >> n;
        if(n <= 0){ cout << "Error" << endl; return -1; }
 
        int **Array = new int*[n];
        for(int i = 0; i < n; i++)
                Array[i] = new int[n];
 
        int *Check = new int[n+1];
        IniMatrix(Array,n,Check);
        int value = 0;
        // считываем из матрицы
                for(int i = 0; i < n; i++){
                        for(int j = 0; j < n; j++)
                                if( in >> value ){
                                        Array[i][j] = value;
                                }else{
                                        cout << "Matrix ne polsost zapoln" << endl; break;
                                }
                }
        PrintMatrix(Array,n);
        in.close();
 
        // считаем количество ребер
        Check = CheckMatrix(Array,n,Check);
 
        // проверяем на равенство вершины
        if( CheckRav(Check,n) ){
            for(int i = 0; i < n; i++){
                if( Array[0][i] == 1 ){
                    Array[0][i] = 0; break;
                }
            }
            cout << "\nZadanie 1" << endl;
            PrintMatrix(Array,n);
        }
        else{
            cout << "Ravenstvo ne vypoln!" << endl;
        }
 
        for(int i = 0; i < n; i++)
                delete []Array[i];
        delete []Array;
        delete []Check;
        return 0;
}
 
//-------- Инициализация
void IniMatrix(int **&Array, int n, int *&Check){
        for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++)
                        Array[i][j] = 0;
                Check[i] = 0;
        }
        Check[n] = 0;
}
 
//-------------------
int *CheckMatrix(int **Array, int n, int *Check){
        for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                        if( Array[i][j] == 1 )
                                Check[i]++;
                }
        }
        return Check;
}
 
//-----------
int PrintMatrix(int **Array, int n){
        for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++)
                        cout << Array[i][j] <<" ";
                cout << endl;
        }
        return 0;
}
 
//------------
bool CheckRav(int *Check, int n){
    for(int i = 1; i < n; i++){
        if( Check[i] != Check[0] ){
            return false;
        }
    }
    return true;
}
Пример документа "test.txt"
3
0 1 1
1 0 1
1 1 0
Пример работы программы:
Изображения
 
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.07.2010, 17:29     Графы
Еще ссылки по теме:

Графы C++
Графы C++
графы C++

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

Или воспользуйтесь поиском по форуму:
dxdy
 Аватар для dxdy
97 / 97 / 5
Регистрация: 14.06.2010
Сообщений: 283
14.07.2010, 17:29     Графы #8
Во втором задании самое главное это правильно задавать исходную матрицу смежности! Матрица смежности для неориентированного графа должна быть симметричная и по главной диагонали стоять единицы! Если это условие не выполняется, проверка условия задачи 2 не будет выполняться!
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <fstream>
using namespace std;
 
int ReadFile(char *name);
void IniMatrix(int **&Array, int n);
int *CheckMatrix(int **Array, int n, int key);
int PrintMatrix(int **Array, int n);
bool isVersh(int **Array, int n, int key, int pos);
bool isGraf(int **Array, int n);
 
int main(){
        ReadFile("test.txt");
        return 0;
}
 
//-----------------------
int ReadFile(char *name){
        ifstream in(name);
        if(!in){ cout <<"Error" << endl; return -1; }
 
        int n = 0;
        in >> n;
        if(n <= 0){ cout << "Error" << endl; return -1; }
 
        int **Array = new int*[n];
        for(int i = 0; i < n; i++)
                Array[i] = new int[n];
 
        IniMatrix(Array,n);
        int value = 0;
        // считываем из матрицы
                for(int i = 0; i < n; i++){
                        for(int j = 0; j < n; j++)
                                if( in >> value ){
                                        Array[i][j] = value;
                                }else{
                                        cout << "Matrix ne polsost zapoln" << endl; break;
                                }
                }
        PrintMatrix(Array,n);
        in.close();
        if( !isGraf(Array,n) ){
            cout << "Graf neorientirov!" << endl; return -1;
        }
 
        int key = 0;
        do{
            cout << "Vvedite vershinu proverki" << endl;
        cin >> key;
        }while(key < 0 || key >= n);
 
        CheckMatrix(Array,n,key);
 
        for(int i = 0; i < n; i++)
                delete []Array[i];
        delete []Array;
        return 0;
}
 
//-------- Инициализация
void IniMatrix(int **&Array, int n){
        for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++)
                        Array[i][j] = 0;
        }
}
 
//-------------------
int *CheckMatrix(int **Array, int n, int key){
    int size = 1;
    for(int i = 0; i < n; i++){
        if( Array[key][i] == 1 )
            size++;
    }
 
    int **newArray = new int*[size];
    for(int i = 0; i < size; i++)
        newArray[i] = new int[size];
 
    int x = 0, y = 0;
    for(int i = 0; i < n; i++){
        if( isVersh(Array,n,key,i) ){
            for(int j = 0; j < n; j++){
                if( isVersh(Array,n,key,j) ){
                    newArray[x][y++] = Array[i][j];
                }
            }
            x++; y = 0;
        }
    }
 
    PrintMatrix(newArray,size);
    for(int i = 0; i < size; i++)
        delete []newArray[i];
    delete []newArray;
    return 0;
}
 
//-----------
bool isVersh(int **Array, int n, int key, int pos){
    if( (Array[pos][key] == 1) || ( (Array[pos][key] == 0) && (pos == key) ) )
        return true;
    return false;
}
 
//-----------
bool isGraf(int **Array, int n){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if( (Array[i][i] == 1) || (Array[i][j] != Array[j][i]) )
                return false;
        }
    }
    return true;
}
 
//-----------
int PrintMatrix(int **Array, int n){
        for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++)
                        cout << Array[i][j] <<" ";
                cout << endl;
        }
        return 0;
}
Тест для проверки:
4
0 1 1 0
1 0 0 0
1 0 0 0
0 0 0 0
Если мы выберем 0 вершину, то матрица будет размера 3х3
1. 1 вершина -> матрица 2x2
2. 2 вершина -> матрица 2x2
3. 3 вершина -> матрица размерности 1 (изолированная вершина)
Надеюсь условие задачи понял верно =)

Добавлено через 16 минут
Да простит меня форум, но я пост #8 я уже не имею право исправить, поэтому хочу сообщить об ошибке в данном посте
Матрица смежности для неориентированного графа должна быть симметричная и по главной диагонали стоять 0!
В посте #7 быстро сделал по аналогии, но для экономии памяти
C++
1
int *Check = new int[n];
C++
1
2
3
4
5
6
7
8
9
//-------- Инициализация
void IniMatrix(int **&Array, int n, int *&Check){
        for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++)
                        Array[i][j] = 0;
                Check[i] = 0;
        }
        //Check[n] = 0;
}
Yandex
Объявления
14.07.2010, 17:29     Графы
Ответ Создать тему
Опции темы

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