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

Работа с Ориентированным графом - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.78
jhendrix
0 / 0 / 0
Регистрация: 23.02.2010
Сообщений: 184
07.03.2012, 19:14     Работа с Ориентированным графом #1
Дан орграф. После удаления произвольных вершин может произойти всё что угодно,
вопрос таков: Для каждого компонета связности выделить матрицу смежности (т.е. создать массив
матриц для каждого подграфа). Есть ли алгоритм как можно это легко и компактно написать и если есть помогите с реализацией.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.03.2012, 22:38     Работа с Ориентированным графом #2
Алгоритм придумать не сложно. Если у Вас есть уже какие-то наработки: как хранятся входные данные о начальном графе и как собираетесь хранить полученный результат (массив матриц для каждого подграфа), то показывайте, подгоню под них алгоритм.
Если наработок нет, то напишите максимальное кол-во вершин и порядок ввода входных данных.
jhendrix
0 / 0 / 0
Регистрация: 23.02.2010
Сообщений: 184
07.03.2012, 23:05  [ТС]     Работа с Ориентированным графом #3
входные данные :
1. колличество вершин.
2. матрица смежности данного графа.
в принципе должно быть 3 входные данные, т.к. удаление конкретных вершин может повлиять
на результат программы, поэтому
3. вершины, кот. нужно удалить
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.03.2012, 23:18     Работа с Ориентированным графом #4
Цитата Сообщение от jhendrix Посмотреть сообщение
входные данные :
1. колличество вершин.
2. матрица смежности данного графа.
в принципе должно быть 3 входные данные, т.к. удаление конкретных вершин может повлиять
на результат программы, поэтому
3. вершины, кот. нужно удалить
Сможете написать начало кода (ввод входных данных)?
И еще напишите максимальное кол-во вершин.
jhendrix
0 / 0 / 0
Регистрация: 23.02.2010
Сообщений: 184
07.03.2012, 23:31  [ТС]     Работа с Ориентированным графом #5
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
////////////////////////////////////
#include <iostream>
#include <fstream>
#define v_max 100
using namespace std;
 
ifstream in("example.txt");
 
int n;
int A[v_max][v_max];
 
int main()
{
  int i,j;
  in >> n;
  for (i=1; i<=n; i++)
   for (j=1; j<=n; j++)
     in >> A[i][j];
 
}
////////////////////////////////////
 Комментарий модератора 
Используйте теги форматирования кода!

v_max - максимальное кол. вершин, хотя может быть и меньше (это зависит от примера)
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.03.2012, 23:41     Работа с Ориентированным графом #6
Цитата Сообщение от jhendrix Посмотреть сообщение
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
в паскале раньше писали?
сейчас накидаю как должен выглядеть код.
jhendrix
0 / 0 / 0
Регистрация: 23.02.2010
Сообщений: 184
07.03.2012, 23:44  [ТС]     Работа с Ориентированным графом #7
я работаю на c++
Байт
 Аватар для Байт
13974 / 8805 / 1227
Регистрация: 24.12.2010
Сообщений: 15,949
07.03.2012, 23:52     Работа с Ориентированным графом #8
Цитата Сообщение от valeriikozlov Посмотреть сообщение
в паскале раньше писали?
Как догадался? Из-за единички, да?
Мне досталось продолжать нехилый проект, там все было в Си, но использовались в массивах элементы, начиная с 1. Мне б, дураку, сразу этому конец положить, но в начале было не до этого.
И вот уже прошло много лет, и все матерюсь на того дурака, да и на себя тоже. Откуда я считаю здесь? От нуля? или от 1 ?

Добавлено через 1 минуту
Цитата Сообщение от jhendrix Посмотреть сообщение
я работаю на c++
Тогда пойми раз и навсегда, что первое число - 0
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.03.2012, 23:56     Работа с Ориентированным графом #9
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
#include <iostream>
 #include <fstream>
 #define v_max 100
 using namespace std;
 
 ifstream in("example.txt");
 
 int n, tmp;
 int m;// кол-во удаленных вершин
 int Q[v_max];// массив будем использовать в качестве очереди
 int i_st, i_end;// переменные для очереди (указывают начало очереди и конец очереди)
 bool mas_del[v_max];// для меток удаленных вершин
 int A[v_max][v_max];
 bool B[v_max][v_max];// аналог матрицы смежности, но если есть путь из вершины 1 в вершину 2, а обратного пути нет, то в этом массиве пометим оба пути (так нужно)
 
 int main()
 {
 int i,j;
 in >> n;
 for (i=0; i<n; i++)
     for (j=0; j<n; j++)
     {
         in >> A[i][j];
         if(A[i][j])
         {
             B[i][j]=B[j][i]=true;// заполняем массив B[][] значениями
         }
     }
 }
 in >> m;// ввод кол-ва удаленных вершин
 for(i=0; i<m; i++)
 {
     in>>tmp;
     mas_del[tmp]=true;
 }
 for(i=0; i<n; i++)
     if(!mas_del[i])// если вершина не была удалена
     {// здесь будем в mas_del[] помечать также и вершины которые уже вошли в состав какого-либо подграфа
         mas_del[i]=true;
         i_st=0; i_end=1; Q[0]=i;
         while(i_st<i_end)
         {
             for(j=0; j<n; j++)
                 if(B[Q[i_st]][j] && !mas_del[j])
                 {
                     mas_del[j]=true;
                     Q[i_end++]=j;
                 }
         }
         // вот здесь в Q[] по индексам от 0 до i_end(не включая сам индекс i_end) записаны вершины очередного подграфа
         // Вам осталось записать их как Вы хотите (используя данные о связях из A[][])
     }
Дальше справитесь?
jhendrix
0 / 0 / 0
Регистрация: 23.02.2010
Сообщений: 184
08.03.2012, 00:43  [ТС]     Работа с Ориентированным графом #10
Я понял вашу идею, но как говорится "Понял!? понял. Сделаешь!? нет" , можете доделать это до конца, если не трудно.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.03.2012, 01:01     Работа с Ориентированным графом #11
Цитата Сообщение от jhendrix Посмотреть сообщение
можете доделать это до конца, если не трудно.
могу. Только давайте решим вот что. Например есть очередной подграф с вершинами: 2 4 9. В приципе для его хранения нужен массив размером 3*3.
Единственный вопрос что делать с номерами вершин. Сами номера нужно сохранять?

Добавлено через 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
#include <iostream>
#include <vector>
 #include <fstream>
 #define v_max 100
 using namespace std;
 struct tt{
     int N, mas_num[v_max];
     int S[v_max][v_max];
 };
 
vector<tt> V;
 ifstream in("example.txt");
 
 int n, tmp;
 int m;// кол-во удаленных вершин
 int Q[v_max];// массив будем использовать в качестве очереди
 int i_st, i_end;// переменные для очереди (указывают начало очереди и конец очереди)
 bool mas_del[v_max];// для меток удаленных вершин
 int A[v_max][v_max];
 bool B[v_max][v_max];// аналог матрицы смежности, но если есть путь из вершины 1 в вершину 2, а обратного пути нет, то в этом массиве пометим оба пути (так нужно)
 
 int main()
 {
 int i, j, y;
 in >> n;
 for (i=0; i<n; i++)
         for (j=0; j<n; j++)
         {
                 in >> A[i][j];
                 if(A[i][j])
                 {
                         B[i][j]=B[j][i]=true;// заполняем массив B[][] значениями
                 }
         }
 in >> m;// ввод кол-ва удаленных вершин
 for(i=0; i<m; i++)
 {
         in>>tmp;
         mas_del[tmp]=true;
 }
 for(i=0; i<n; i++)
         if(!mas_del[i])// если вершина не была удалена
         {// здесь будем в mas_del[] помечать также и вершины которые уже вошли в состав какого-либо подграфа
                 mas_del[i]=true;
                 i_st=0; i_end=1; Q[0]=i;
                 while(i_st<i_end)
                 {
                         for(j=0; j<n; j++)
                                 if(B[Q[i_st]][j] && !mas_del[j])
                                 {
                                         mas_del[j]=true;
                                         Q[i_end++]=j;
                                 }
                 }
                 tt temp;
                 temp.N=i_end;
                 for(j=0; j<i_end; j++)
                 {
                     temp.mas_num[j]=Q[j];
                     for(y=0; y<i_end; y++)
                         temp.S[j][y]=A[Q[j]][Q[y]];
                 }
                 V.push_back(temp);                 
         }
    return 0;
}
Т.е. в векторе V каждый элемент представляет из себя подграф. А именно в переменной N хранится значение кол-ва вершин подграфа. В матрице смежности S[][] хранятся данные о связности. В массиве mas_num[] номера вершин (первоначальные номера вершин).
Т.е. например S[2][2] например такой:
0 1
0 0
а массив mas_num[2] такой:
25 46
то это будет означать что в данном подграфе всего две вершины с номерами 25 и 46 и путь есть только из вершины 25 в 46, а обратно нет.
jhendrix
0 / 0 / 0
Регистрация: 23.02.2010
Сообщений: 184
08.03.2012, 01:17  [ТС]     Работа с Ориентированным графом #12
в конце цикла while(i_st<i_end) кажется нужно добавить i_st++;
спасибо за идею;
Ничего, если будут вопросы, я обращусь к тебе;
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.03.2012, 01:19     Работа с Ориентированным графом
Еще ссылки по теме:

Написать калькулятор с объектно–ориентированным подходом C++
C++ Алгоритм поиска пути в лабиринте, заданном связным графом

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.03.2012, 01:19     Работа с Ориентированным графом #13
Цитата Сообщение от jhendrix Посмотреть сообщение
в конце цикла while(i_st<i_end) кажется нужно добавить i_st++;
да, все правильно. )

Добавлено через 29 секунд
Цитата Сообщение от jhendrix Посмотреть сообщение
Ничего, если будут вопросы, я обращусь к тебе;
можно прямо в личку.
Yandex
Объявления
08.03.2012, 01:19     Работа с Ориентированным графом
Ответ Создать тему
Опции темы

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