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

Дана матрица инцидентности, вывести множество пар вершин - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.75
dibilasd
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
24.10.2010, 20:50     Дана матрица инцидентности, вывести множество пар вершин #1
есть матрица инцидентности графа, например:

//матрица инцидентности
1 1 0
1 0 1
0 1 1

как вывести множество пар вершин из этой матрицы и название ребра, то есть:

e1-e2 -1
e1-e3 -2
e2-e3 -3


код C++

C++
1
2
3
4
5
6
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
  cout<<"M["<<i+1<<","<<j+1<<"]: ";                                
  cin>>SMatrix[i][j];
}

как дальше, как реализовать программно (вывод множества пар вершин)?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
24.10.2010, 20:53     Дана матрица инцидентности, вывести множество пар вершин #2
dibilasd,
C++
1
2
3
4
5
6
std::vector<std::pair<int, int> > VecP;
for(std::vector<std::pair<int, int> >::const_iterator It=VecP.begin(),
It!=VecP.end(), ++It)
{
    std::cout<<It->first<<'-'<<It->second<<'\n';
}
Например
dibilasd
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
24.10.2010, 21:01  [ТС]     Дана матрица инцидентности, вывести множество пар вершин #3
а можно пояснения??
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
24.10.2010, 21:05     Дана матрица инцидентности, вывести множество пар вершин #4
dibilasd, Ну можно и книжку открыть или инет...

C++
1
2
3
4
5
6
7
8
9
//Объявление вектора пар. Пара - два значения. Стандартная шаблонная структура
std::vector<std::pair<int, int> > VecP;
//Цикл от начала до конца
for(std::vector<std::pair<int, int> >::const_iterator It=VecP.begin(),
It!=VecP.end(), ++It)
{
//Вывод первого и второго элемента каждой пары.
    std::cout<<It->first<<'-'<<It->second<<'\n';
}
dibilasd
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
24.10.2010, 22:16  [ТС]     Дана матрица инцидентности, вывести множество пар вершин #5
а как передать елементы Smatrix в Vecp??
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
24.10.2010, 22:23     Дана матрица инцидентности, вывести множество пар вершин #6
dibilasd, Smatrix? Це массив стандартных объектов или массив пользовательских (класс, структура) ?
dibilasd
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
24.10.2010, 22:25  [ТС]     Дана матрица инцидентности, вывести множество пар вершин #7
це массив (матрица инцидентности)

Добавлено через 53 секунды
int SMatrix [50][50];
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
24.10.2010, 22:32     Дана матрица инцидентности, вывести множество пар вершин #8
dibilasd, А зачем матрицу инцедентности туда загонять?
dibilasd
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
24.10.2010, 22:32  [ТС]     Дана матрица инцидентности, вывести множество пар вершин #9
ну а как вывести множество пар вершин из матрицы инцидентности??
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
24.10.2010, 22:38     Дана матрица инцидентности, вывести множество пар вершин #10
dibilasd, Смотри...

Есть матрица инцидентности.
Есть вектор пар ребер.
Матрица инцидентности заполненная.
Ребро связано с другим ребром только в том случае, если в матрице на этом месте стоит 1. Верно?
Тогда. Если нам нужно вывести инцидентные ребра, то записываем мы в вектор пар номера одного и другого ребра.

Итак псевдокод.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Matrix[n][n];
std::vector<std::pair<int, int> > VecP;
for(int i=0; i<n; ++i)
{
    for(int j=0; j<n; ++j)
    {
        if(Matrix[i][j]==1)
           VecP.push_back(std::make_pair<int, int>(i, j));
    }
}
for(std::vector<std::pair<int, int> >::const_iterator It=VecP.begin();
It!=VecP.end();
++It)
{
    std::cout<<It->first<<' '<<It->second<<'\n';
}
dibilasd
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
24.10.2010, 23:06  [ТС]     Дана матрица инцидентности, вывести множество пар вершин #11
например, если ввести матрицу инцидентности:
1 1 0
1 0 1
0 1 1

получится результат работы программы:
1-1
1-2
2-1
2-3
3-2
3-3

а меня интересует результат типа:
1-2 -1
1-3 -2
2-3 -3

то есть, первые две цифры - это названия вершин, а 3 цифра - это название ребра
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
24.10.2010, 23:20     Дана матрица инцидентности, вывести множество пар вершин #12
dibilasd, И я так понимаю, что ребро
1-2
2-1

Должно выводится 1 раз?
dibilasd
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
24.10.2010, 23:26  [ТС]     Дана матрица инцидентности, вывести множество пар вершин #13
да, один раз
dibilasd
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
24.10.2010, 23:34  [ТС]     Дана матрица инцидентности, вывести множество пар вершин #14
тобто,
матрица инцидентности:
1 1 0
1 0 1
0 1 1

и потому искомые множества будут такими:

1 - 2 - 1
1 - 3 - 2
2 - 3 - 3
Изображения
 
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
25.10.2010, 00:01     Дана матрица инцидентности, вывести множество пар вершин #15
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int Matrix[n][n];
std::vector<std::pair<int, int> > VecP;
std::vector<int> Edges;
int l=0;
for(int i=0; i<n; ++i)
{
    for(int j=0; j<n; ++j)
    {
        if(Matrix[i][j]==1&&i>=j)
        {
           VecP.push_back(std::make_pair<int, int>(i, j));
           Edges.push_back(l);
           l++;
        }
    }
}
for(std::vector<std::pair<int, int> >::const_iterator It=VecP.begin();
It!=VecP.end();
++It)
{
    std::cout<<It->first<<' '<<It->second<<"Number - "<< l<<'\n';
}
Добавлено через 48 секунд
dibilasd, М. Ща. Кажется неверно понял. Поправлю...
Да... Я неверно просек суть. Не исправлю видимо.

Добавлено через 22 минуты
То, что писал я вполне хорошо подходит для смежности...
dibilasd
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
25.10.2010, 00:04  [ТС]     Дана матрица инцидентности, вывести множество пар вершин #16
да и в случае смежности получается тот же результат, ребра выводятся два раза
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
25.10.2010, 00:10     Дана матрица инцидентности, вывести множество пар вершин #17
Вывод.
1-2
1-3
2-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
#include <iostream>
#include <vector>
#include <utility>
 
int main()
{
    const int n=3;
    int Matrix[n][n]={ {0, 1, 1}, {1, 0, 1}, {1, 1, 0} };
std::vector<std::pair<int, int> > VecP;
std::vector<int> Edges;
for(int i=0; i<n; ++i)
{
    for(int j=0; j<n; ++j)
    {
        if(Matrix[i][j]==1&&j>=i)
        {
           VecP.push_back(std::make_pair<int, int>(i+1, j+1));
        }
    }
}
for(std::vector<std::pair<int, int> >::const_iterator It=VecP.begin();
It!=VecP.end();
++It)
{
    std::cout<<It->first<<' '<<It->second<<'\n';
}
return 0;
}
dibilasd
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
25.10.2010, 00:18  [ТС]     Дана матрица инцидентности, вывести множество пар вершин #18
если ввести матрицу смежности:
0 1 1
1 0 1
1 1 0

должно получиться:
1-2
1-3
2-3
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
25.10.2010, 00:18     Дана матрица инцидентности, вывести множество пар вершин #19
dibilasd, Ну да. Что и получается.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.10.2010, 00:21     Дана матрица инцидентности, вывести множество пар вершин
Еще ссылки по теме:

Дана матрица А(7,4) Вывести все отрицательные элементы этой матрицы. Найти минимальный по модулю элемент C++
Дана матрица размерности nxm целых чисел. Найти наибольшее из них и вывести его индексы C++
Дана матрица Е[4,7]. В каждой строке найти и вывести максимальный элемент и сумму отрицательных элементов C++

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

Или воспользуйтесь поиском по форуму:
dibilasd
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
25.10.2010, 00:21  [ТС]     Дана матрица инцидентности, вывести множество пар вершин #20
и получается:
1-2
1-3
2-1
2-3
3-1
3-2
Yandex
Объявления
25.10.2010, 00:21     Дана матрица инцидентности, вывести множество пар вершин
Ответ Создать тему
Опции темы

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