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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.67
corri
1 / 1 / 0
Регистрация: 07.09.2009
Сообщений: 32
#1

Графы на С++ - C++

02.10.2009, 22:01. Просмотров 1583. Ответов 13
Метки нет (Все метки)

Помогите плиз!
Есть задача:
Посвящение в студенты.Есть n студентов.НЕ ВСЕ знают друг друга.Но у каждого есть знакомые..Действует принцип:"Знакомые моих знакомых - мои знакомые" Задача найти пары студентов которых надо познакомить для того чтобы все студенты знали друг дрга...
По идее реализуется через Граф,вот только у меня не получается граф на С++ построить.....
Помогите кто может...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.10.2009, 22:01
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Графы на С++ (C++):

Графы - C++
помогите с реализацией алгоритма Дейкстры для нахождения расстояния от узла 1 в каждый узел. матрица весов такая...

Графы - C++
Написать программу, реализующую алгоритм Беллмана-Форда.

Графы в С++ - C++
Как можно в программу на С++ ввести граф??моей задачей является определить оптимальное расположение остановок в городе,ну и город в виде...

Графы - C++
Прочитал про обход графа в глубину, посмотрел реализацию, и тут вопрос а как можно использовать этот обход в глубину?

Графы - C++
1) Построить граф, используя язык С++ (или Си), согласно данной схеме на рис.1. 2) По запросу пользователя должны удаляться: • все...

Графы - C++
Помогите написать программу: Модель работы некоторой системы представлена ориентированным графом, где вершины – это состояния системы,...

13
kravam
быдлокодер
1697 / 884 / 45
Регистрация: 04.06.2008
Сообщений: 5,482
02.10.2009, 22:24 #2
Давай определимся по входным данным.
Пусть имеются 10 студентов, от 0 до 9.
Очевидно, если действует принцип "знакомые моих знакомых- мои знакомые", то имеются группы знакомцев. В каждой может быть от 1-го до 10 человек, (если все друг с другом знакомы)

Пусть группы такие.
0, 5, 9
1, 2
4
6
3, 7, 8

Теперь по вводу данных. Если вводятся данные так, как я представил (группами то есть), то дело не стоит выведнного яйца.
Но они могут вводиться и по другому. Парами.
0 5
5 9
1 2
3 7
7 8

Это посложнее будет уже.
Ворос: как вводятся входные данные? С ответом не затягивай, а то решу, как Бог на душу положит.
0
corri
1 / 1 / 0
Регистрация: 07.09.2009
Сообщений: 32
02.10.2009, 22:25  [ТС] #3
вводятся парами - (n,m)
Где n и m - номера студентов
0
odip
Эксперт С++
7158 / 3220 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
03.10.2009, 00:19 #4
Какая разница как вводится ?
Граф представляется с помощью матрицы смежности.
(1) Можно напрямую подгружать матрицу смежности.
(2) Можно вводить с помощью групп.
(3) Можно с помощью пар.
В любом варианте можем построить матрицу смежности.

Но это все не приближает нас к собственно алгоритму

Добавлено через 2 минуты
И задача не очень корректно поставлена.
Я могу сказать что нужно просто познакомить всех пары, которые еще не знакомы друг с другом напрямую - без посредников.
Скорее всего в условии имеется в виду - найти МИНИМАЛЬНОЕ кол-во пар, которых надо познакомить для того чтобы все студенты знали друг друга...
0
corri
1 / 1 / 0
Регистрация: 07.09.2009
Сообщений: 32
03.10.2009, 00:40  [ТС] #5
"...Скорее всего в условии имеется в виду - найти МИНИМАЛЬНОЕ кол-во пар, которых надо познакомить для того чтобы все студенты знали друг друга..."
ну дык да....))
звиняюсь за кривые объяснения условия...((
Прост на практике сказали сделать,и что объяснения будут на лекции,а лектор сказал,что объяснит потом как-нибудь)))))))))))
Пойду погуглю матрицу скважности))
0
Rififi
2359 / 1052 / 44
Регистрация: 03.05.2009
Сообщений: 2,656
03.10.2009, 00:43 #6
corri
лектор сказал,что объяснит потом как-нибудь)))))))))))

а ты ему скажи, что принесешь потом как-нибудь
1
corri
1 / 1 / 0
Регистрация: 07.09.2009
Сообщений: 32
03.10.2009, 00:45  [ТС] #7
А это вариант
Ток лектор и практик разные..(((((
0
odip
Эксперт С++
7158 / 3220 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
03.10.2009, 00:54 #8
Думаю алгоритм такой.
Нужно разбить на области связности.
Потом области связности сливать между собой в одну БОЛЬШУЮ область связности
путем создания новой пары.
Когда будет только одна область связности - задача решена.
Если областей связности N, то нужно образовать новых N-1 пар.
0
kravam
быдлокодер
1697 / 884 / 45
Регистрация: 04.06.2008
Сообщений: 5,482
03.10.2009, 00:56 #9
Я решу эту задачу, автор.
И безо всяких графов.
В печку графы.
0
corri
1 / 1 / 0
Регистрация: 07.09.2009
Сообщений: 32
03.10.2009, 00:59  [ТС] #10
Я буду очень счастлив увидев хоть какой-нить код))
ПАСИБА зараннее..!!
Пойду дочитывать матрицы смежности и всё в том же духе1!
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.10.2009, 07:21 #11
corri,
Вот решение без графов:
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
#include <iostream.h>
#include <Windows.h>
#include <iomanip>
#include <process.h> 
 
int kol_par, i, first, gl, count, **mas1; 
int main ()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    cout<<"Ââåäèòå êîëè÷åñòâî Г§Г*Г*êîìûõ ГЇГ*Г°"<<endl;
    cin>>kol_par;
    mas1=new int*[kol_par];
    for(i=0; i<kol_par; i++)
        mas1[i]=new int[2];
    cout<<"Ââåäèòå Г§Г*Г*êîìûå ГЇГ*ðû"<<endl;
    for(i=0; i<kol_par; i++)
        cin>>mas1[i][0]>>mas1[i][1];
    cout<<"Г*ГіГ¦Г*Г® ïîçГ*Г*êîìèòü:"<<endl;
    count=0;
    first=gl=mas1[0][0];
    int a;
    do
    {
        for(i=0; i<kol_par; i++)
        {
            if(mas1[i][0]==gl)
                mas1[i][0]=-1;
            if(mas1[i][1]==gl)
                mas1[i][1]=-1;
        }
        a=0;
        for(i=0; i<kol_par; i++)
        {
            if(mas1[i][0]==-1 && mas1[i][1]!=-1)
            {
                gl=mas1[i][1];
                a=1;
                break;
            }
            if(mas1[i][0]!=-1 && mas1[i][1]==-1)
            {
                gl=mas1[i][0];
                a=1;
                break;
            }
        }
        if(a==0)
        {
            for(i=0; i<kol_par; i++)
                if(mas1[i][0]!=-1)
                {
                    gl=mas1[i][0];
                    cout<<first<<"   "<<gl<<endl;
                    count++;
                    break;
                }
 
        }
        a=0;
        for(i=0; i<kol_par; i++)
            if(mas1[i][0]!=-1 || mas1[i][1]!=-1)
                a=1;
    }while(a==1);
        cout<<"Êîëè÷åñòâî ГЇГ*Г° Г*ГіГ¦Г*Г® ïîçГ*Г*êîìèòü: "<<count<<endl;
    system("pause");
    return 0;
}
В данном коде нет проверки на студентов одиночек, т.к. по условию задачи написанному Вами:
Цитата Сообщение от corri Посмотреть сообщение
Но у каждого есть знакомые.
0
kravam
быдлокодер
1697 / 884 / 45
Регистрация: 04.06.2008
Сообщений: 5,482
03.10.2009, 09:32 #12
Автор, лови:
Значит, идея такова. Все студенты очевидно разбиваются на группы. Каждая группа- связный список. Формируем связные списки. В конце работы выводятся по одному члену из каждого списка.
Знакомь их между собой и всё.
Одиночки тоже выведутся (если будут). Так что вот.

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <stdio.h>
#include <iostream>
using namespace std;
 
 
int main(){
 
 int kol_studentov;
 
 //Это вот один и второй, будем их вводить.
 int odin;
 int vtoroi;
 
 //Вот по этой переменной мы либо выходим из цикла, либо нет. 
 char vihod_i_tsikla;
 
 //Эта штука будет содержать информацию о студенте.
 //Адрес нулевого элемента это адрес нулевого элемента
 //списка, к которому принадлежит студент
 //если адрес указывает в никуда, студнт не принадлежит ни одному из списков
 struct student {
  student* adres_nachalnogo_elementa;
  student* adres_ego_druga;
 }*pstudent;
 
 
 
 cout<<"Вводи количество студентов"<< endl;
 cin>> kol_studentov;
 
 
 
 
 //Это вот под студентов мы объявляем массив
 student* pMassivStudentov= new student [kol_studentov]; 
 
 
 //Все элементы будем обнулять принудительно. Это очень важно!
 for (int i= 0; i< kol_studentov;i++ ) {
  pMassivStudentov[i].adres_nachalnogo_elementa= 0;
  pMassivStudentov[i].adres_ego_druga= 0;
 }
 printf ("&pMassivStudentov[0]=  %d\n\n", &pMassivStudentov[0]);
 
 
 
 //Будем формировать связные списки.
 //По окончании задачи нас будет интересовать только один какой-нибудь 
 //элемент каждого связного списка
 //Допустим, организовалось 5 групп (5 связных списков) и 3 свободных студента
 //Пусть номера ПОСЛЕДНИХ (почему последних- объяснение внизу.) элементов в связных списках 1, 2, 34, 23, 5
 //Пусть номера свободных студентов 7, 20, 56
 //Тогда вот тебе минимальное количество пар-знакомств, чтобы все были знакомы друг с другом.
 //1- 2, 2-34, 34- 23, 23- 5, 5- 7, 7-20, 20-56
 
 //Главное- правильно заполнить массив pMassivStudentov
 //В путь!
 
 
 while (1) {
 
  cout<< "Вводи пару"<< endl;
  cin>>odin;
  cin>>vtoroi;
   
  //Рассмотрим имеющиеся у нас связные списки и наличие в них первогои второго студентов
  //Варианты: 
  //1) если студенты не присутствуют ни в каких списках, составляем из них
  //новый связный список
  //2) ЕСли студенты присутствуют в одном каком-нибудь списке, то ничё не делем.
  //3) если студенты присутствуют в разных списках, "соединяем эти списки"
  //4) Если какой-то из студентов присутствует в каком-нибудь списке, то присоединяем второго
  //к этому списку
  //фишка в том, что ни один студент не может присутствовать более, чем в одном связном списке
 
    
  //Теперь вопрос- как узнать, принадлежит студент к какому-нибудь связному списку?
  //Правильно, надо посмотреть на adres_nachalnogo_elementa
  //на поле adres_ego_druga смотреть не надо, т. к. если чел последним в списке, то
  //оно также будет указыватьв никуда, как если бы он ни в каком списке не состоял
  
  //сюда идём, если первый чел состоит в каком-нибудь связном списке
  if (pMassivStudentov[odin].adres_nachalnogo_elementa) {
 
   //Cюда идём, если второй чел состоит в этом же связном списке
   if (pMassivStudentov[odin].adres_nachalnogo_elementa==pMassivStudentov[vtoroi].adres_nachalnogo_elementa) {
    //Кстати, тут ничё делать не надо. Исправлять не буду. Зато иллюстративно
   }
 
   //сюда идём, если второй чел не стостоит в том списке, что и первый.
   //кстати, не факт, что второй состоит в каком-нибудь списке
   else     {
 
    //Сюда идём, если второй чел состоит в списке, отличным от того, в каком состоит первый
    //Тут фишка в том, что если он вобще
    //нигде не состоит, то выполняются одни и те же действия, как если бы он состоял в 
    //каком-нибудь списке ВоТ они
    //Значит, их надо запихать в один список. Соединить то есть списки.
    //делаем это так
    //Берём список, которому принадлежит студент odin и добираемся до его последнего элемента
    //И вот здесь нам понадобится pstudent
    pstudent= &pMassivStudentov[odin];
    while (pstudent->adres_ego_druga)
     pstudent=pstudent->adres_ego_druga;
 
    //Всё, теперь pstudent указыват на последний элемент в списке
    //Теперь делаем так
    pstudent->adres_ego_druga= &pMassivStudentov[vtoroi];
      
    //Всё, связный список сформирован
    //Теперь в элементах, что раньше принадлежали второй половине списка, исправим поля
    //adres_nachalnogo_elementa и всё на этом
    pstudent= &pMassivStudentov[vtoroi];
    pstudent->adres_nachalnogo_elementa= pMassivStudentov[odin].adres_nachalnogo_elementa;
    while (pstudent->adres_ego_druga) {
     pstudent=pstudent->adres_ego_druga;
     pstudent->adres_nachalnogo_elementa= pMassivStudentov[odin].adres_nachalnogo_elementa;
    }
    ; 
 
   }
  }   
 
  //а сюда идём, если не состоит (первый)
  else {
 
   //сюда пойдём, если второй чел состоит в каком-нибудь списке
   if (pMassivStudentov[vtoroi].adres_nachalnogo_elementa) {
    //Действия описывать не буду, они уже выше описаны, толко там наоборот было
    //Первый состоял в спписке. а второй нет
    pstudent= &pMassivStudentov[vtoroi];
    while (pstudent->adres_ego_druga)
     pstudent=pstudent->adres_ego_druga;
    pstudent->adres_ego_druga= &pMassivStudentov[odin];
    pstudent= &pMassivStudentov[odin];
    pstudent->adres_nachalnogo_elementa= pMassivStudentov[vtoroi].adres_nachalnogo_elementa;
    while (pstudent->adres_ego_druga) {
     pstudent=pstudent->adres_ego_druga;
     pstudent->adres_nachalnogo_elementa= pMassivStudentov[vtoroi].adres_nachalnogo_elementa;
    }
   }
 
   //а сюда пойдём, если не состоит ни тот, ни другой
   //значит, формируем из них двух связный список
   else {
    pMassivStudentov[odin].adres_nachalnogo_elementa=&pMassivStudentov[odin];
    pMassivStudentov[odin].adres_ego_druga=&pMassivStudentov[vtoroi];
    pMassivStudentov[vtoroi].adres_nachalnogo_elementa=&pMassivStudentov[odin];
   }
  } 
  
 
 
  //Так, здесь смотрим, будем вводить дальше пару или нет
  cout<< "Работаем дольше? (y или любой другой знак)"<< endl;
  fflush (stdin);
  if (vihod_i_tsikla= getchar ()!= 'y') 
   break;
 }
 
 //Всё. Теперь пробегаемя по всем связным спискам и из каждого берём по одному студенту.
 //Делается это так.
 //Только у последних студентов всех связных списков поле adres_ego_druga
 //указывает в никуда
 //Кроме того,в никуда оно указывает и у всех свободных студентв
 //Короче,  берём тех студентов, у уоторых это поле указывает в никуда, знакомими
 //их меж собой и всё, аля-улю, гони гусей.
 
 cout<< "Лови номера студентов. Ты их уж перезнакомь как-нибудь сам..."<< endl;
 
 for (int i= 0; i< kol_studentov; i++) {
  if (!pMassivStudentov[i].adres_ego_druga) {
   printf ("%d   ", i);
  }
 }
 printf ("\n");
 getchar ();
 getchar ();
 return 0;
}
Добавлено через 28 минут
Добавление. В моём коде слабое место это ввод. Ну, то есть он безошибочен, но громоздко сделан.
Это потому, что я не шарю в cin вообще!
valeriikozlov, простите. Ситуация такая. Если имеется 8 студентов, разбитых на такие группы знакомых:
0, 1, 2, 3, 4, 5 и 6, 7, 8

Это мне по приглашению ввести количество знакомых пар, чего вводить надо?
Ну, то есть, я хотел сказать, что ВООБЩЕ количество знакомых пар тут равно 18 (в первой группе 15 и во второй 3). То есть подсчитывать нужно будет всегда вручную?
Впрочем, я уверен, что неправильно Вас понял и Вы этот вопрос проясните.
1
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.10.2009, 12:43 #13
kravam,
"Ввести количество знакомых пар", это значит следущее:
Немного ранее Вы спрашивали как делать ввод у Corri:
"Но они могут вводиться и по другому. Парами.
0 5
5 9
1 2
3 7
7 8"
и он давал ответ "да, парами".
Так вот имеенно под этот вариант и был сделан код.
Т.е. если пары такие:
0 5
5 9
1 2
3 7
7 8
то количество пар здесь 5.

Добавлено через 1 час 47 минут
Извиняюсь, нужно было отлучиться. Еще немного поясню к предыдущему:
"Ввести количество знакомых пар" наверное точнее будет - ввести количество вводимых пар.
Т.е. если вводимые пары такие:
0 5
5 9
1 2
3 7
7 8
то на предложение "ввести количество знакомых пар" нужно ввести - 5.
0
corri
1 / 1 / 0
Регистрация: 07.09.2009
Сообщений: 32
03.10.2009, 15:11  [ТС] #14
ОООО!!!!!
Пасиба!!!!
И за комменты как для чайника спасиба!!!!!!!!!
Отличнейше всё написано!!!!!!
ЗАЧЁТ!!!!
0
03.10.2009, 15:11
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.10.2009, 15:11
Привет! Вот еще темы с ответами:

Графы - C++
Граф задан своей матрицей смежностей. Вывести на экран все связные вершины...очень скоро нужно...извините за срочность

Графы - C++
Имеется сеть автомобильных дорог. Известны расстояния всех участков дорог. Некоторые участки аварийноопасны. Требуется найти путь из пункта...

[C++] графы - C++
Алгоритм фронт фолны в графе Помогите.. Дана матрица Ag (Матрица смежности графа) И координаты начальной вершины i,j и кординаты...

Графы - C++
Люди скиньте пожалуйста какую нибудь программку на С++ по графам, или дайте ссылку на темку на форему...


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

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

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