2354 / 1772 / 212
Регистрация: 07.01.2011
Сообщений: 10,342
1

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

08.01.2014, 20:00. Показов 3326. Ответов 7
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Графом называется совокупность точек ( узлов), некоторые из которых соединены между собой направленными ребрами. Граф , состоящий из 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;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.01.2014, 20:00
Ответы с готовыми решениями:

Лабиринт для матрицы соединений
Лабиринт задан матрицей соединений, в которой для каждой пары комнат указано, соединены ли они...

Дана матрица соединений некоторой сети из n узлов; получить матрицу связей этой сети
Сетью называется совокупность точек (узлов), некоторые из которых соединены между собой стрелками....

Графы: перевод матрицы инцидентности в список ребер
в ближайшие несколько дней нужна программа и блок-схема перевода матрицы инцидентности в список...

Матрицы. Найти и распечатать сумму элементов 5-го столбца матрицы А и сумму элементов последней строки матрицы В
Даны две матрицы А(mxn)и В(m1xn1).программа находит и распечатывает сумму элементов 5-го столбца...

7
162 / 162 / 42
Регистрация: 29.05.2010
Сообщений: 435
08.01.2014, 21:10 2
Можно с помощью поиска в глубину/в ширину реализовать.
1
2354 / 1772 / 212
Регистрация: 07.01.2011
Сообщений: 10,342
08.01.2014, 21:13  [ТС] 3
Цитата Сообщение от AnDrew_LP Посмотреть сообщение
Можно с помощью поиска в глубину/в ширину реализовать.
поподробней.
Я должен анализировать первую матрицу, и на ее основе сделать другую.
А как это сделать с помощью поисков?
0
162 / 162 / 42
Регистрация: 29.05.2010
Сообщений: 435
08.01.2014, 21:34 4
Цитата Сообщение от zewer Посмотреть сообщение
поподробней.
Я должен анализировать первую матрицу, и на ее основе сделать другую.
А как это сделать с помощью поисков?
Каждая строка матрицы связей будет создана с помощью одного прохода алгоритмом.
С помощью алгоритма поиска в ширину помечаем вершины, связанные с i-ой.
Создаем массив, заполненный нулями, кроме i-ого элемента - вершины, с которой начинается поиск(ее помечаем 1).
Для всех смежных вершин с вершинами, которые помечены 1, в массив ставим 2. На следующем шаге помечаем 3 все смежные вершины с такими, которые помечены 2. И т.д., пока на каком-либо шаге не найдется смежных вершин.
В матрицу связей записываем ноль, если в массиве записан ноль, если что-то другое - записываем единицу.
1
2354 / 1772 / 212
Регистрация: 07.01.2011
Сообщений: 10,342
08.01.2014, 21:41  [ТС] 5
Цитата Сообщение от AnDrew_LP Посмотреть сообщение
Каждая строка матрицы связей будет создана с помощью одного прохода алгоритмом.
С помощью алгоритма поиска в ширину помечаем вершины, связанные с i-ой.
Создаем массив, заполненный нулями, кроме i-ого элемента - вершины, с которой начинается поиск(ее помечаем 1).
Для всех смежных вершин с вершинами, которые помечены 1, в массив ставим 2. На следующем шаге помечаем 3 все смежные вершины с такими, которые помечены 2. И т.д., пока на каком-либо шаге не найдется смежных вершин.
В матрицу связей записываем ноль, если в массиве записан ноль, если что-то другое - записываем единицу.
хм спасибо, попробую вникнуть в суть.
а после построения другой матрицы, не подскажете как вывести сам граф?
0
162 / 162 / 42
Регистрация: 29.05.2010
Сообщений: 435
08.01.2014, 21:52 6
Цитата Сообщение от zewer Посмотреть сообщение
хм спасибо, попробую вникнуть в суть.
а после построения другой матрицы, не подскажете как вывести сам граф?
А что значит "графическое отображение графа" ? Я, честно говоря, не представляю, как его можно отобразить в консоли.
0
2354 / 1772 / 212
Регистрация: 07.01.2011
Сообщений: 10,342
08.01.2014, 22:24  [ТС] 7
Цитата Сообщение от AnDrew_LP Посмотреть сообщение
А что значит "графическое отображение графа" ? Я, честно говоря, не представляю, как его можно отобразить в консоли.
а если например это сделать на С#, не через консоль, а через GUI.
С помощью чего это можно реализовать?
0
162 / 162 / 42
Регистрация: 29.05.2010
Сообщений: 435
08.01.2014, 22:35 8
Цитата Сообщение от zewer Посмотреть сообщение
а если например это сделать на С#, не через консоль, а через GUI.
С помощью чего это можно реализовать?
Ну самый простой вариант - это разместить вершины графа на окружности (поделить 360 на количество вершин, с помощью формул переходить от полярной системы координат к декартовой). Ну и соединять вершины ребрами, где надо.
1
08.01.2014, 22:35
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.01.2014, 22:35
Помогаю со студенческими работами здесь

Зеркально отразить элементы матрицы относительно горизонтальной оси симметрии матрицы
Здравствуйте! Помогите написать 3 программмы на C++ на задачи с двумерными массивами 3. Дана...

Вычесть из элементов первого столбца матрицы значение максимального элемента матрицы
Составить программу, в которой 1) организовать ввод матрицы размера mxn из целых чисел;...

Разделить все элементы матрицы на максимальный по абсолютной величине элемент матрицы
Добрый день! Помогите пожалуйста с задачей -- напишите код... Если все элементы главной диагонали...

Поменять большие элементы в строке матрицы с маленькими элементами этой же матрицы
Дана мне задача надо заменить большие элементы в строке матрицы с маленькими элементами этой же...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru