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

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

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

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

24.10.2010, 20:50. Просмотров 2105. Ответов 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];
}

как дальше, как реализовать программно (вывод множества пар вершин)?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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. С...

24
dibilasd
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
25.10.2010, 00:04  [ТС] #16
да и в случае смежности получается тот же результат, ребра выводятся два раза
0
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 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;
}
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
0
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
25.10.2010, 00:18 #19
dibilasd, Ну да. Что и получается.
0
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
0
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
25.10.2010, 00:22 #21
А по инцидентности...

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

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

Добавлено через 29 секунд
dibilasd, Нет. Получается
1-2
1-3
2-3
Я как бэ поправил код. Еще раз попробуйте
0
dibilasd
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
25.10.2010, 00:23  [ТС] #22
ну так что, с матрицей инцидентности идей нет?
0
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
25.10.2010, 00:23 #23
dibilasd, Читайте выше ТТ.
0
dibilasd
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
25.10.2010, 00:28  [ТС] #24
вершины идут по столбцам, а названия ребер по строкам
0
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 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;
}
1
25.10.2010, 01:05
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.10.2010, 01:05
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
25
Ответ Создать тему
Опции темы

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