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

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

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

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

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

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

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

Графы - C++
Задан граф матрицей смежности Заданы две вершины, начальная и конечная, требуется найти первую вершину в пути между ними

С++ и графы - C++
Доброго времени суток. Хотел бы попросить помощи в написании программы. Нужно создать программу которая будет проводить расчет сетевого...

Графы - C++
Суть задачи: дан ориентированный граф, у которого каждая вершина (не ребро) имеет вес. Нужно найти путь из любой точки в любую, но чтобы он...

графы - C++
помогите пожалуйста написать программу! Составить программу печати всех циклов ориентированного графа Добавлено через 2 часа 21...

графы - C++
помогите пожалуйста начинающему((, вот задачка: Задана система односторонних дорог. Определить, можно ли, построив еще четыре новые...

Графы - C++
Написать на C++ класс, описывающий граф/орграф. Класс должен поддерживать следующую функциональность: • определение числа вершин; ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
kravam
быдлокодер
1691 / 878 / 44
Регистрация: 04.06.2008
Сообщений: 5,424
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

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

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

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

а ты ему скажи, что принесешь потом как-нибудь
corri
1 / 1 / 0
Регистрация: 07.09.2009
Сообщений: 32
03.10.2009, 00:45  [ТС]     Графы на С++ #7
А это вариант
Ток лектор и практик разные..(((((
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
03.10.2009, 00:54     Графы на С++ #8
Думаю алгоритм такой.
Нужно разбить на области связности.
Потом области связности сливать между собой в одну БОЛЬШУЮ область связности
путем создания новой пары.
Когда будет только одна область связности - задача решена.
Если областей связности N, то нужно образовать новых N-1 пар.
kravam
быдлокодер
1691 / 878 / 44
Регистрация: 04.06.2008
Сообщений: 5,424
03.10.2009, 00:56     Графы на С++ #9
Я решу эту задачу, автор.
И безо всяких графов.
В печку графы.
corri
1 / 1 / 0
Регистрация: 07.09.2009
Сообщений: 32
03.10.2009, 00:59  [ТС]     Графы на С++ #10
Я буду очень счастлив увидев хоть какой-нить код))
ПАСИБА зараннее..!!
Пойду дочитывать матрицы смежности и всё в том же духе1!
valeriikozlov
Эксперт C++
4669 / 2495 / 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 Посмотреть сообщение
Но у каждого есть знакомые.
kravam
быдлокодер
1691 / 878 / 44
Регистрация: 04.06.2008
Сообщений: 5,424
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). То есть подсчитывать нужно будет всегда вручную?
Впрочем, я уверен, что неправильно Вас понял и Вы этот вопрос проясните.
valeriikozlov
Эксперт C++
4669 / 2495 / 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.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.10.2009, 15:11     Графы на С++
Еще ссылки по теме:

Графы - C++
добрый день! помогите решить задачу: Соединением графов G1 и G2 называется граф G=(V,E), для которого V=V1объединениеV2,...

Графы (с++) - C++
Помогите с задачей: граф задается своей матрицей смежностей; вывести на экран матрицу инцидентности графа. Добавлено через 1 час 34...

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

Графы - C++
Задана система односторонних дорог(вбивается рандомно или вручную). Найти два города и соединяющий их путь, который проходит через каждую...

Графы - C++
помогите пожалуйста написать программу удаления вершины: а)с сохранением связей б)без сохранения связей желательно на с билдер


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

Или воспользуйтесь поиском по форуму:
corri
1 / 1 / 0
Регистрация: 07.09.2009
Сообщений: 32
03.10.2009, 15:11  [ТС]     Графы на С++ #14
ОООО!!!!!
Пасиба!!!!
И за комменты как для чайника спасиба!!!!!!!!!
Отличнейше всё написано!!!!!!
ЗАЧЁТ!!!!
Yandex
Объявления
03.10.2009, 15:11     Графы на С++
Ответ Создать тему
Опции темы

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