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

Графы: матрицы соединений и матрицы связей - C++

Восстановить пароль Регистрация
 
zewer
 Аватар для zewer
1018 / 709 / 71
Регистрация: 07.01.2011
Сообщений: 5,355
08.01.2014, 20:00     Графы: матрицы соединений и матрицы связей #1
Графом называется совокупность точек ( узлов), некоторые из которых соединены между собой направленными ребрами. Граф , состоящий из n узлов можно описать двумя матрицами порядка n : матрицей соединений и матрицей связей. Элемент матрицы соединений a[i,j] = 1, если граф содержит ребро направлено от узла i к узлу j и a[i,j] = 0 в другом случае . Элемент матрицы связей b[i,j] = 1, если с узла i можно попасть в узел j , двигаясь по ребрам и b[i,j] = 0 в другом случае .
Задача : ввести количество узлов некоторого графа. Задав произвольно матрицу соединений ( в интерактивном режиме или случайным образом ) , построить матрицу связей для этого графу . Предусмотреть графическое отображение такого графа и числовой вывод обеих матриц .

Я реализовал генерацию/ручной ввод матрицы соединений, и немножко написал о матрицы связей, но не могу правильно задать алгоритм для ее создания. Прошу помочь, и так же подсказать как сделать графическое отображение такого графа. Написан мной код привожу:

C++
1
2
3
4
5
//---head.h
void manual_input(int &N, int **&Matrix);
void auto_input (int &N,int **&Matrix);
void matrix(int size, int**&M);
void create_matrix(int &N, int **&Matrix_2, int **&Matrix);

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//----input.cpp
#include "iostream"
#include "head.h"
#include <time.h>
 
using namespace std;
 
void manual_input(int &N, int **&Matrix) //ручной ввод
{
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            cin>>Matrix[i][j];
            cout<<"\t";
        }
        cout<<endl;
    }
}
 
void auto_input (int &N,int **&Matrix)//случайная генераций матрицы
{
    srand(time(0));
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            if (i == j)
                Matrix[i][j] = 0;
            else
                Matrix[i][j] = rand()%2;
        }
    }
}
 
void matrix(int size, int**&M)//инициализация и выделения памяти под матрицы
{
    M=new int*[size];
    for(int i=0;i<size;i++)
        M[i] = new int[size];
}
 
void create_matrix(int &N, int **&Matrix_2, int **&Matrix)//создание матрицы связей
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (i == j)
                Matrix_2[i][j] = 0;
            else
            {
                int ii=i;
                int jj=j+1;
                if (Matrix[i][j] == 1)
                    Matrix_2[i][j] = 1;
                else if (Matrix[i][j] == 0)
                {//--------не могу придумать алгоритм
                    while (ii<N)
                    {
                        for (jj; jj<N; jj++)
                        {
                            if (Matrix[ii][jj] == 1)
                            {
                            
                            }
                        }
                    }
 
                }//-------------------
            }
        }
    }
}

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
40
41
42
43
44
//-----main.cpp
#include "iostream"
#include <locale>
#include "head.h"
 
using namespace std;
 
int main ()
{
    setlocale(LC_ALL,"Russian");
    cout << "Введiть порядок матрицi: ";
    int g = 0;
    cin >> g;
    int** Matrix; //Матриця з'єднаннь
    matrix(g, Matrix);
    cout << "\n";
    cout << "Автогенерацiя(1) чи ручний ввiд(2)? - ";
    int t;
    cin >> t;
 
    //----------------Матриця з'єднаннь--------------соединений
    if (t == 1)
        auto_input(g, Matrix);
    else if (t == 2)
        manual_input(g, Matrix);
    //-----------------------------------------------
 
    //----------------Матриця зв'язків--------------связей
    int** matrix_2;
    matrix(g, matrix_2);
    create_matrix(g, matrix_2, Matrix);
    //-----------------------------------------------
 
    for(int i=0;i<g;i++)
    {
        for(int j=0;j<g;j++)
        {
            cout << matrix_2[i][j] << " ";
        }
        cout << "\n";
    }
 
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.01.2014, 20:00     Графы: матрицы соединений и матрицы связей
Посмотрите здесь:

C++ На главной диагонали новой матрицы разместить элементы заданного столбца исходной матрицы
C++ какими средствами пользоваться для того, чтобы умножать матрицы, складывать матрицы?
Если след матрицы A[n][m] больше 50, то все эелементы матрицы увеличить на 2. C++
Матрицы: нахождение сумм положительных элементов строк каждой матрицы C++
Матрицы: удалить из матрицы столбцы, в которых есть равные элементы C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
AnDrew_LP
160 / 162 / 9
Регистрация: 29.05.2010
Сообщений: 435
08.01.2014, 21:10     Графы: матрицы соединений и матрицы связей #2
Можно с помощью поиска в глубину/в ширину реализовать.
zewer
 Аватар для zewer
1018 / 709 / 71
Регистрация: 07.01.2011
Сообщений: 5,355
08.01.2014, 21:13  [ТС]     Графы: матрицы соединений и матрицы связей #3
Цитата Сообщение от AnDrew_LP Посмотреть сообщение
Можно с помощью поиска в глубину/в ширину реализовать.
поподробней.
Я должен анализировать первую матрицу, и на ее основе сделать другую.
А как это сделать с помощью поисков?
AnDrew_LP
160 / 162 / 9
Регистрация: 29.05.2010
Сообщений: 435
08.01.2014, 21:34     Графы: матрицы соединений и матрицы связей #4
Цитата Сообщение от zewer Посмотреть сообщение
поподробней.
Я должен анализировать первую матрицу, и на ее основе сделать другую.
А как это сделать с помощью поисков?
Каждая строка матрицы связей будет создана с помощью одного прохода алгоритмом.
С помощью алгоритма поиска в ширину помечаем вершины, связанные с i-ой.
Создаем массив, заполненный нулями, кроме i-ого элемента - вершины, с которой начинается поиск(ее помечаем 1).
Для всех смежных вершин с вершинами, которые помечены 1, в массив ставим 2. На следующем шаге помечаем 3 все смежные вершины с такими, которые помечены 2. И т.д., пока на каком-либо шаге не найдется смежных вершин.
В матрицу связей записываем ноль, если в массиве записан ноль, если что-то другое - записываем единицу.
zewer
 Аватар для zewer
1018 / 709 / 71
Регистрация: 07.01.2011
Сообщений: 5,355
08.01.2014, 21:41  [ТС]     Графы: матрицы соединений и матрицы связей #5
Цитата Сообщение от AnDrew_LP Посмотреть сообщение
Каждая строка матрицы связей будет создана с помощью одного прохода алгоритмом.
С помощью алгоритма поиска в ширину помечаем вершины, связанные с i-ой.
Создаем массив, заполненный нулями, кроме i-ого элемента - вершины, с которой начинается поиск(ее помечаем 1).
Для всех смежных вершин с вершинами, которые помечены 1, в массив ставим 2. На следующем шаге помечаем 3 все смежные вершины с такими, которые помечены 2. И т.д., пока на каком-либо шаге не найдется смежных вершин.
В матрицу связей записываем ноль, если в массиве записан ноль, если что-то другое - записываем единицу.
хм спасибо, попробую вникнуть в суть.
а после построения другой матрицы, не подскажете как вывести сам граф?
AnDrew_LP
160 / 162 / 9
Регистрация: 29.05.2010
Сообщений: 435
08.01.2014, 21:52     Графы: матрицы соединений и матрицы связей #6
Цитата Сообщение от zewer Посмотреть сообщение
хм спасибо, попробую вникнуть в суть.
а после построения другой матрицы, не подскажете как вывести сам граф?
А что значит "графическое отображение графа" ? Я, честно говоря, не представляю, как его можно отобразить в консоли.
zewer
 Аватар для zewer
1018 / 709 / 71
Регистрация: 07.01.2011
Сообщений: 5,355
08.01.2014, 22:24  [ТС]     Графы: матрицы соединений и матрицы связей #7
Цитата Сообщение от AnDrew_LP Посмотреть сообщение
А что значит "графическое отображение графа" ? Я, честно говоря, не представляю, как его можно отобразить в консоли.
а если например это сделать на С#, не через консоль, а через GUI.
С помощью чего это можно реализовать?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.01.2014, 22:35     Графы: матрицы соединений и матрицы связей
Еще ссылки по теме:

Поменять большие элементы в строке матрицы с маленькими элементами этой же матрицы C++
C++ В заданной матрицы А (6, 4) найти значение крупнейшего по модулю элемента матрицы
Дана матрица соединений некоторой сети из n узлов; получить матрицу связей этой сети C++

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

Или воспользуйтесь поиском по форуму:
AnDrew_LP
160 / 162 / 9
Регистрация: 29.05.2010
Сообщений: 435
08.01.2014, 22:35     Графы: матрицы соединений и матрицы связей #8
Цитата Сообщение от zewer Посмотреть сообщение
а если например это сделать на С#, не через консоль, а через GUI.
С помощью чего это можно реализовать?
Ну самый простой вариант - это разместить вершины графа на окружности (поделить 360 на количество вершин, с помощью формул переходить от полярной системы координат к декартовой). Ну и соединять вершины ребрами, где надо.
Yandex
Объявления
08.01.2014, 22:35     Графы: матрицы соединений и матрицы связей
Ответ Создать тему
Опции темы

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