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

Матрицы инцидентнности и смежности - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
ulian
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
06.02.2013, 18:38     Матрицы инцидентнности и смежности #1
Помогите написать программу, на входе дан текстовый файл вида:
n m
v1 u1
v2 u2
.........
vm um
где n - количество вершин графа, m - количество ребер, v и u - начальное и конечное значение ребра(целые числа >1)

а на вывод функции должно вывести матрицу инцидентнности и смежную матрицу. Не имеет значение куда, на экран либо в текстовый файл.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.02.2013, 18:38     Матрицы инцидентнности и смежности
Посмотрите здесь:

генерация матрицы смежности C++
C++ Определение матрицы смежности графа по заданной матрице инцидентности
Как из матрицы смежности получить матрицу инцидентности? C++
Простой неориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности C++
C++ список смежности в матрицу смежности
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ulian
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
07.02.2013, 19:42  [ТС]     Матрицы инцидентнности и смежности #2
кто-то может помочь?
palva
 Аватар для palva
2373 / 1595 / 190
Регистрация: 08.06.2007
Сообщений: 6,364
Записей в блоге: 4
07.02.2013, 20:03     Матрицы инцидентнности и смежности #3
А ребра больше единицы, они что, не подряд идут? Например, возможен такой набор всех ребер графа: 3 6 29 33002
ulian
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
07.02.2013, 20:04  [ТС]     Матрицы инцидентнности и смежности #4
да, там имеется в виду начальное и конечное значение вершины, но можно ограничится числами до 100)
palva
 Аватар для palva
2373 / 1595 / 190
Регистрация: 08.06.2007
Сообщений: 6,364
Записей в блоге: 4
07.02.2013, 20:15     Матрицы инцидентнности и смежности #5
Вы не ответили на вопрос. У вас написано, что номер вершины больше 1. Значит ли это, что номера вершин идут не подряд, типа 1,2,3,...,15, когда n=15, а в разбивку, так как я написал.
ulian
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
07.02.2013, 20:27  [ТС]     Матрицы инцидентнности и смежности #6
они должны идти по-порядку
palva
 Аватар для palva
2373 / 1595 / 190
Регистрация: 08.06.2007
Сообщений: 6,364
Записей в блоге: 4
07.02.2013, 20:38     Матрицы инцидентнности и смежности #7
Я пытаюсь понять нужен ли предварительный просмотр номеров. То есть, если я прочитал n=4, то номера вершин не могут быть 1,2,3,4, поскольку они должны быть больше единицы. Может ли оказаться, что номера вершин следующие: 20,21,22,23 ? Или начальный номер обязательно 2?

Тот же вопрос с номерами ребер. Можно ли считать, что их номера 1, 2, ..., m, или их номера тоже должны быть больше единицы?
ulian
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
07.02.2013, 21:43  [ТС]     Матрицы инцидентнности и смежности #8
вершин должно быть больше единицы, начиная с 2 и так далее 3,4,5,... до н
ребер же начиная с единицы 1,2,3,... до м
1≤V≤n, 1≤U≤ в таком диапазоне вершины
palva
 Аватар для palva
2373 / 1595 / 190
Регистрация: 08.06.2007
Сообщений: 6,364
Записей в блоге: 4
07.02.2013, 22:28     Матрицы инцидентнности и смежности #9
Цитата Сообщение от ulian Посмотреть сообщение
1≤V≤n, 1≤U≤ в таком диапазоне вершины
Я скоро заплачу! Ну невозможно такое, чтобы вершин было n и их номера находились в диапазоне 1≤V≤n, потому что номеров больших единицы в этом диапазоне всего n-1.
ulian
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
07.02.2013, 22:32  [ТС]     Матрицы инцидентнности и смежности #10
не знаю, возможно я не правильно понял задание. Переписал заданиев точную с книги.
1. Считывание графа из входного файла. На вход подается текстовый файл следующего
вид:
n m
v1 u1
v2 u2
....
vm um
Здесь n - количество вершин графа (целое число, больше нуля), m - количество ребер графа
(целое число, больше нуля), vi и ui
* - Начальная и конечная вершина ребра i (1 ≤ vi ≤ n,
1 ≤ ui ≤ n, целые числа). Индексация вершин в файле ведется с 1. Считается, что граф является
ориентированным.
Таким образом можно сказать, что граф задается в файле списком ребер.
Требуется сделать вывод матриц инцидентности и смежности.
palva
 Аватар для palva
2373 / 1595 / 190
Регистрация: 08.06.2007
Сообщений: 6,364
Записей в блоге: 4
07.02.2013, 22:36     Матрицы инцидентнности и смежности #11
Цитата Сообщение от ulian Посмотреть сообщение
(целое число, больше нуля)
А вы сначала написали, что больше единицы. Теперь всё встало на своё место.
Подождите немного, сейчас попробую написать вариант, если никто раньше не напишет.
ulian
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
07.02.2013, 22:37  [ТС]     Матрицы инцидентнности и смежности #12
да, спасибо большое.
palva
 Аватар для palva
2373 / 1595 / 190
Регистрация: 08.06.2007
Сообщений: 6,364
Записей в блоге: 4
07.02.2013, 23:54     Матрицы инцидентнности и смежности #13
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
#include <fstream>
 
using namespace std;
 
int main()
{
    int n, m, i1, i2, i, j;
    ifstream inf("infile.txt");
    ofstream outf("outfile.txt");
    inf >> n >> m;
    char *a, *b;
    a=new char[n*n];
    for(i=0; i<n*n; i++) a[i]='0';
    b=new char[n*m];
    for(i=0; i<n*m; i++) b[i]='0';
    for(i=0; i<m; i++) {
        inf >> i1 >> i2;
        a[(i1-1)*n+i2-1]='1';
        a[(i2-1)*n+i1-1]='1';
        b[(i1-1)*m+i]='1';
        b[(i2-1)*m+i]='1';
    }
    outf << "Матрица смежности\n";
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) outf << a[i*n+j] << ' ';
        outf << '\n';
    }
    outf << "Матрица инцидентности\n";
    for(i=0; i<n; i++) {
        for(j=0; j<m; j++) outf << b[i*m+j] << ' ';
        outf << '\n';
    }
    delete a;
    delete b;
    return 0;
}
infile.txt
Код
5 7
1 2
2 3
3 4
4 5
5 1
1 3
2 4
outfile.txt
Код
Матрица смежности
0 1 1 0 1 
1 0 1 1 0 
1 1 0 1 0 
0 1 1 0 1 
1 0 0 1 0 
Матрица инцидентности
1 0 0 0 1 1 0 
1 1 0 0 0 0 1 
0 1 1 0 0 1 0 
0 0 1 1 0 0 1 
0 0 0 1 1 0 0
Добавлено через 14 минут
Извините, сейчас еще раз прочитал задачу и увидел, что граф ориентированный. Тогда нужно внести следующие исправления в программу. центральный цикл
C++
1
2
3
4
5
6
7
    for(i=0; i<m; i++) {
        inf >> i1 >> i2;
        a[(i1-1)*n+i2-1]='1';
        a[(i2-1)*n+i1-1]='1';
        b[(i1-1)*m+i]='1';
        b[(i2-1)*m+i]='1';
    }
надо заменить на
C++
1
2
3
4
5
6
    for(i=0; i<m; i++) {
        inf >> i1 >> i2;
        a[(i1-1)*n+i2-1]='1';
        b[(i1-1)*m+i]='-';
        b[(i2-1)*m+i]='+';
    }
Добавлено через 22 минуты
Еще одна версия. Теперь поддерживаются кратные ребра
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
#include <fstream>
#include <iomanip>
 
using namespace std;
 
int main()
{
    int n, m, i1, i2, i, j;
    ifstream inf("infile.txt");
    ofstream outf("outfile.txt");
    inf >> n >> m;
    int *a, *b;
    a=new int[n*n];
    for(i=0; i<n*n; i++) a[i]=0;
    b=new int[n*m];
    for(i=0; i<n*m; i++) b[i]=0;
    for(i=0; i<m; i++) {
        inf >> i1 >> i2;
        a[(i1-1)*n+i2-1]++;
        b[(i1-1)*m+i]--;
        b[(i2-1)*m+i]++;
    }
    outf << "Матрица смежности\n";
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) outf << a[i*n+j] << ' ';
        outf << '\n';
    }
    outf << "Матрица инцидентности\n";
    for(i=0; i<n; i++) {
        for(j=0; j<m; j++) outf << setw(3) << b[i*m+j];
        outf << '\n';
    }
    delete a;
    delete b;
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.02.2013, 00:32     Матрицы инцидентнности и смежности
Еще ссылки по теме:

C++ Построение матрицы смежности
C++ Граф в виде матрицы смежности и количества вершин
C++ Алгоритм Дейкстры для матрицы смежности А размером NxN, нарисовать блок-схему по коду

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

Или воспользуйтесь поиском по форуму:
ulian
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
08.02.2013, 00:32  [ТС]     Матрицы инцидентнности и смежности #14
Спасибо вам большое!
Yandex
Объявления
08.02.2013, 00:32     Матрицы инцидентнности и смежности
Ответ Создать тему
Опции темы

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