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

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

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

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

24.10.2010, 20:50. Просмотров 2000. Ответов 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++ Максимальное множество вершин графа
Дана матрица размера MxN. Вывести ее элементы, расположенные в столбцах с нечетными номерами C++
Дана действительная квадратная матрица X размером n*n. Транспонировать X. Не разрешается использовать вспомогательные массивы. Результат вывести в мат C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
25.10.2010, 00:22     Дана матрица инцидентности, вывести множество пар вершин #21
А по инцидентности...

У нас по строкам идут вершины, по столбцам ребра или наоборот?

Вообщем если чисто теоретически, тот код надо переделать не особо сильно.
Надо просто проверять какие вершины инцидентны данному ребру в матрице, записывать их номера в вектор пар + записывать в вектор ребер - номер этого ребра. Выводить собственно понятно как.

Добавлено через 29 секунд
dibilasd, Нет. Получается
1-2
1-3
2-3
Я как бэ поправил код. Еще раз попробуйте
dibilasd
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
25.10.2010, 00:23  [ТС]     Дана матрица инцидентности, вывести множество пар вершин #22
ну так что, с матрицей инцидентности идей нет?
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
25.10.2010, 00:23     Дана матрица инцидентности, вывести множество пар вершин #23
dibilasd, Читайте выше ТТ.
dibilasd
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
25.10.2010, 00:28  [ТС]     Дана матрица инцидентности, вывести множество пар вершин #24
вершины идут по столбцам, а названия ребер по строкам
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.10.2010, 01:05     Дана матрица инцидентности, вывести множество пар вершин
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
25.10.2010, 01:05     Дана матрица инцидентности, вывести множество пар вершин #25
Ага?

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
#include <iostream>
#include <vector>
#include <utility>
 
int main()
{
    const int n=3;
    int Matrix[n][n]={ {1, 1, 0}, {1, 0, 1}, {0, 1, 1} };
std::vector<std::pair<int, int> > VecP;
std::vector<int> Edges;
for(int i=0; i<n; ++i)
{
    int cnt=0, temp;
    for(int j=0; j<n; ++j)
    {
        if(Matrix[i][j]==1)
        {
           if(cnt==0)
              temp=j;
           cnt++;
        }
        if(cnt==2)
        {
            VecP.push_back(std::make_pair<int, int>(temp+1, j+1));
            Edges.push_back(i+1);
            break;
        }
    }
}
std::vector<int>::const_iterator Iter=Edges.begin();
for(std::vector<std::pair<int, int> >::const_iterator It=VecP.begin();
It!=VecP.end(), Iter!=Edges.end();
++It, ++Iter)
{
    std::cout<<It->first<<'-'<<It->second<<' '<<*Iter<<'\n';
}
return 0;
}
Добавлено через 25 минут
Хотя пожалуй так можно избежать лишних проверок уникальности вершин в ребрах.

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
#include <iostream>
#include <vector>
#include <utility>
#include <set>
 
int main()
{
    const int n=3;
    int Matrix[n][n]={ {1, 1, 0}, {1, 0, 1}, {0, 1, 1} };
    std::set<std::pair<int, int> > VecP;
    std::vector<int> Edges;
    for(int i=0; i<n; ++i)
    {
        int cnt=0, temp;
        for(int j=0; j<n; ++j)
        {
            if(Matrix[i][j]==1)
            {
                if(cnt==0)
                    temp=j;
                cnt++;
            }
            if(cnt==2)
            {
                VecP.insert(std::make_pair<int, int>(temp+1, j+1));
                Edges.push_back(i+1);
                break;
            }
        }
    }
    std::vector<int>::const_iterator Iter=Edges.begin();
    for(std::set<std::pair<int, int> >::const_iterator It=VecP.begin();
    It!=VecP.end();
    ++It, ++Iter)
    {
        std::cout<<It->first<<'-'<<It->second<<' '<<*Iter<<'\n';
    }
    return 0;
}
Yandex
Объявления
25.10.2010, 01:05     Дана матрица инцидентности, вывести множество пар вершин
Ответ Создать тему
Опции темы

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