Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
eternalenvy
0 / 0 / 1
Регистрация: 01.07.2014
Сообщений: 27
#1

Неориентированный граф, вывести порядки вершин графа - C++

08.06.2015, 15:20. Просмотров 613. Ответов 5
Метки нет (Все метки)

Доброго времени суток. Прошу помощи. С алгоритмами работал мало, решил взяться за сложную(для меня) задачу. Можете дать подсказку какую-нибудь?
Дан двумерный[5][5] массив. Это и будет матрица смежности - значения 1, 0. Нужно вывести порядки вершин графа.

Неориентированный граф, вывести порядки вершин графа

Допустим из вершины 1 в вершину 5 двое путей: 1245 и 1345. Из вершины 2 в вершину 3 двое путей: 243, 213. И так далее. Надеюсь, суть понятна.
А вот набросок, в котором я смог вывести доступные пути для вершин:

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
#include <iostream>
#include <conio.h>
#include <string>
using namespace std;
 
const int n=5;
 
int main () {
    setlocale(0, "");
        int arr[n][n] =
        {               
               {0,1,1,0,0},
 
               {1,0,0,1,0},
 
               {1,0,0,1,0},
 
               {0,1,1,0,1},
 
               {0,0,0,1,0}
        };
        int count;
        int tempI;
        int tempJ;
        int temp;
    
        for(int i = 0; i < n; i++) 
        {
            for(int j = 0; j < n; j++)
            {
                if ( arr[i][j] == 1 ) // ищем в массиве значение 1
                {
                    temp = arr[i][j];
                    tempI = i;
                    tempJ = j;
                    cout << temp+tempI << temp+tempJ << " ";
                
                }
            }
        }
        _getch();
}
Но вывод таков: 12 13 21 24 31 34 42 43 45 54
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.06.2015, 15:20
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Неориентированный граф, вывести порядки вершин графа (C++):

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

Неориентированный невзвешенный граф: найти количество вершин, лежащих в одной компоненте связности с данной вершиной
Дан неориентированный невзвешенный граф. Для него вам необходимо найти...

Неориентированный граф
Есть такое задание &quot;Реализация АТД « Неориентированный граф» через класс. Граф...

Неориентированный граф!!!
Еще раз обращаюсь за помощью к форуму..от этих задач зависит стипендия!...

Вывести количество вершин неориентированного графа, смежных с данной
Есть задание по с++ совершенно не понимаю как делать. Кому не сложно,...

Граф задается своей матрицей смежностей; вывести на экран матрицу инцидентности графа.
Пожалуйста помогите с задачкой: Граф задается своей матрицей смежностей;...

5
eternalenvy
0 / 0 / 1
Регистрация: 01.07.2014
Сообщений: 27
08.06.2015, 18:08  [ТС] #2
Ну неужели никто не может помочь?

Добавлено через 2 часа 35 минут
UP.
0
Dimension
Dimension
573 / 442 / 221
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
08.06.2015, 18:23 #3
Цитата Сообщение от eternalenvy Посмотреть сообщение
5 двое путей: 1245 и 1345
про цикл забыли
0
eternalenvy
0 / 0 / 1
Регистрация: 01.07.2014
Сообщений: 27
08.06.2015, 18:27  [ТС] #4
Dimension, не совсем понял ответа. Я знаю, что все через цикл делается, но не понимаю как.
0
Ромаха
335 / 117 / 27
Регистрация: 16.12.2012
Сообщений: 553
Записей в блоге: 1
Завершенные тесты: 1
09.06.2015, 14:31 #5
Dimension, не совсем понял ответа. Я знаю, что все через цикл делается, но не понимаю как.
Разговор про то, что существует бесконечное кол-во путей, если в графе присутствует цикл.
Поэтому нужно или проверить наличие цикла (и тогда сказать, что решения не будет) или ввести ограничения на вид графа

Теперь про поиск путей.
Очень просто.
Вы знаете dfs? (Если нет, прямая дорога к вике)
Вам нужно изменить пару строк в нем и радоваться
1
eternalenvy
0 / 0 / 1
Регистрация: 01.07.2014
Сообщений: 27
09.06.2015, 17:19  [ТС] #6
Ромаха, спасибо за ответ! буду думать над решением.
0
09.06.2015, 17:19
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.06.2015, 17:19
Привет! Вот еще темы с решениями:

Вставить в неориентированный граф ребро, соединяющее вершины a и b
Создать граф, используя список смежности. Дан неориентированный граф. Вставить...

Дан неориентированный граф. Необходимо определить, является ли он деревом
Дан неориентированный граф. Необходимо определить, является ли он деревом. ...

Проверить, содержит ли заданный неориентированный граф хотя бы один цикл
Циклом в графе называется маршрут, начальная и конечная вершины которого...

Ввести из файла неориентированный нагруженный граф в список смежности, используя вектор векторов
Доброго времени суток, уважаемые форумчане. Нуждаюсь в вашей помощи)...


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

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

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