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

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

Войти
Регистрация
Восстановить пароль
 
eternalenvy
0 / 0 / 0
Регистрация: 01.07.2014
Сообщений: 27
#1

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

08.06.2015, 15:20. Просмотров 480. Ответов 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++):

Определить степени вершин графа и если граф однородный - вывести степень однородности - C++
Помогите пожалуйста с кодом - на входе у нас есть файл с параметрами графа вида: n m v1 u1 v2 u2 .... vm um Здесь n -...

Неориентированный граф!!! - C++
Еще раз обращаюсь за помощью к форуму..от этих задач зависит стипендия! Помогите пожалуйста! Задача 1. Для неориентированного графа...

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

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

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

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

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

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

Теперь про поиск путей.
Очень просто.
Вы знаете dfs? (Если нет, прямая дорога к вике)
Вам нужно изменить пару строк в нем и радоваться
1
eternalenvy
0 / 0 / 0
Регистрация: 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
Привет! Вот еще темы с ответами:

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

Простой неориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности - C++
Нужно задать граф списком ребер и вывести его в виде матрицы смежности. Знаю что в i строке j столбце ставят 1 если между вершинами i...

Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной - C++
народ помогите пожалуйста написать программу на с++ на графы дана матрица смежности и неориентированный граф. выяснить соседствуют ли...

итератор вершин АТД граф - C++
Здравствуйте Есть класс Graph, абстрактный класс Form, и наследники L и M (формы представления графа) Делаю итератор вершин...


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

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

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