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

Добавить в граф ребро, соединяющее вершины u и v - C++

Восстановить пароль Регистрация
 
metaline
1 / 1 / 0
Регистрация: 09.03.2014
Сообщений: 8
04.05.2014, 13:21     Добавить в граф ребро, соединяющее вершины u и v #1
Доброго дня, друзья!)
Нужно решить задачку, но, к сожаления, не знаю даже с какой стороны подойти, тк с графами ранее не сталкивался. Не могли бы вы помочь решением или идеей как это можно сделать.

Дан граф из N вершин, заданный списком смежности. Необходимо добавить в него ребро, соединяющее вершины u и v и Вывести вершины смежные с u и смежные с v.

Ввод и вывод осуществляется с помощью файла.
В первой строке входного файла записано число N. Следующие N строк имеют следующую структуру: первое число в строке - номер вершины, затем через пробел перечислены смежные с ней вершины. В последней строке через пробел записаны номера вершин u и v.

Вход
4
1 2
2 1 3
3 2 4
4 3
1 3
Выход
2 3
1 2 4
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.05.2014, 13:21     Добавить в граф ребро, соединяющее вершины u и v
Посмотрите здесь:

Граф задается своей матрицей смежностей вывести на экране окружения каждой его вершины C++
Дано ребро куба C++
Найти все вершины графа, к которым существует путь заданной длины от вершины, номер которой вводится с клавиатуры. C++
C++ Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной
C++ Задача на графы. Удалить ребро, соединяющее вершины a и b
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
__General__
24 / 24 / 3
Регистрация: 04.01.2014
Сообщений: 91
Завершенные тесты: 2
04.05.2014, 14:02     Добавить в граф ребро, соединяющее вершины u и v #2
metaline, У тебя есть граф, заданный списком смежности, т. е. есть список вершин графа, а в каждой вершине хранится список инцидентных ей ребер (т. е. фактически, в каждой вершине хранится список указателей на ее смежные вершины). Если ты имел дело со связными списками, то решение задачки не составит для тебя труда.

В твоей программе тебе понадобится:
1) найти вершины u и v в списке вершин (в цикле просматриваешь все вершины, пока не наткнешься на вершину с нужным номером);
2) добавить ребро между вершинами u и v (т. е. в список ребер, инцидентных вершине u добавить элемент: ребро с указателем на вершину v и наоборот);
3) В цикле просмотреть списки ребер, инцидентных вершинам u и v, и вывести номера смежных вершин.
metaline
1 / 1 / 0
Регистрация: 09.03.2014
Сообщений: 8
04.05.2014, 20:33  [ТС]     Добавить в граф ребро, соединяющее вершины u и v #3
__General__ спасибо большое за подсказку. но у меня есть еще вопрос, а именно, как считывать данные из файла, ведь они будут читаться сплошняком, и как отделить например номер вершины, от номеров смежной ей.
__General__
24 / 24 / 3
Регистрация: 04.01.2014
Сообщений: 91
Завершенные тесты: 2
05.05.2014, 15:27     Добавить в граф ребро, соединяющее вершины u и v #4
metaline, Ну например можно вместо того, чтобы считывать числа с помощью cin, считать данные из файла в массив символов с помощью getline(...). Это немного хлопотно, зато считаются все символы, включая пробелы и символ перехода на следующую строку. А из условия задачи мы знаем, что первое число после символа перехода на следующую строку - это номер самой вершины, а все последующие номера вершин до следующего символа перехода на следующую строку - номера вершин, смежных ей.
Yandex
Объявления
05.05.2014, 15:27     Добавить в граф ребро, соединяющее вершины u и v
Ответ Создать тему
Опции темы

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