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

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

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

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

24.10.2010, 20:50. Просмотров 2059. Ответов 24
Метки нет (Все метки)

есть матрица инцидентности графа, например:

//матрица инцидентности
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];
}

как дальше, как реализовать программно (вывод множества пар вершин)?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.10.2010, 20:50
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Дана матрица инцидентности, вывести множество пар вершин (C++):

Построить множество пар вершин по матрице инцидентности - C++
задано матрицу инцидентности. построить множество пар вершин. как реализовать?? //вводим...

Задано множество пар вершин, построить матрицу инцидентности - C++
матрица инцидентности задано множество пар вершин, построить матрицу инцидентности как вывести матрицу инцидентности?? ...

С матрицы смежности в матрицу инцидентности, список рёбер и вершин, диаграмма - C++
Помогите, пожалуйста. На C# или C++ нужна такая программа, что когда задается матрица смежности (5 на 5 можно) и выводились: 1) матрица...

матрица инцидентности - C++
матрица инцидентности задано множество пар вершин, построить матрицу инцидентности как вывести матрицу инцидентности?? ...

Матрица инцидентности и смежностей - C++
скажите пожалуйста, есть ли какая нибудь закономерность между матрицей смежностей и матрицей инцидентности? или лучше способ как вывести на...

Дана матрица вывести номер ее последней строки - C++
Дана матрица вывести номер ее последней строки, содержащей хотя бы один элемент, равный 0. Если такой строки нет вывести -1. С...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 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
В астрале
Эксперт С++
7970 / 4732 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 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
В астрале
Эксперт С++
7970 / 4732 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 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
В астрале
Эксперт С++
7970 / 4732 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
24.10.2010, 22:32 #8
dibilasd, А зачем матрицу инцедентности туда загонять?
dibilasd
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
24.10.2010, 22:32  [ТС] #9
ну а как вывести множество пар вершин из матрицы инцидентности??
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 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
В астрале
Эксперт С++
7970 / 4732 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 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
В астрале
Эксперт С++
7970 / 4732 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 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 минуты
То, что писал я вполне хорошо подходит для смежности...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.10.2010, 00:01
Привет! Вот еще темы с ответами:

Ориентированный граф и матрица инцидентности - C++
Вот у меня есть такое прекрасное задание: Базовый класс: Элемент ориентированного графа. Производные классы: дуга и вершина...

дана квадратичная матрица z[n][n]. составить программу, которая если матрица симметричная(транспонированная матрица равна исходной), сделает ее не сим - C++
помогите пожалуйста. условие: дана квадратичная матрица z. составить программу, которая если матрица симметричная(транспонированная...

Дана матрица размера MxN. Вывести ее элементы, расположенные в столбцах с нечетными номерами - C++
Дана матрица размера MxN. Вывести ее элементы, расположенные в столбцах с нечетными номерами (1, 3, …). Вывод элементов производить по...

Дана матрица Е[4,7]. В каждой строке найти и вывести максимальный элемент и сумму отрицательных элементов - C++
Дана матрица Е. В каждой строке найти и вывести максимальный элемент и сумму отрицательных элементов. Если эта сумма меньше -20, то все...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
25.10.2010, 00:01
Ответ Создать тему
Опции темы

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