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

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

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

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

04.05.2014, 13:21. Просмотров 691. Ответов 3
Метки нет (Все метки)

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

Дан граф из 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
Посмотрите здесь:

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

Граф задается своей матрицей смежностей вывести на экране окружения каждой его вершины - C++
Привет, ребят! Прошу Очень помочь! Граф задается своей матрицей смежностей. Вывести на экране окружения каждой его вершины. ...

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

Подскажите как добавить элемент в стек и вывести адрес новой вершины стека - C++
Dynamic3 . Дано число D и указатель P1 на вершину непустого стека. Добавить элемент со значением D в стек и вывести адрес P2 новой вершины...

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
__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__ спасибо большое за подсказку. но у меня есть еще вопрос, а именно, как считывать данные из файла, ведь они будут читаться сплошняком, и как отделить например номер вершины, от номеров смежной ей.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.05.2014, 15:27     Добавить в граф ребро, соединяющее вершины u и v
Еще ссылки по теме:

Найти все вершины неориентированного графа, к которым существует путь заданной длины от выделенной его вершины - C++
Здравствуйте! Помогите пожалуйста решить задачу. Найти все вершины неориентированного графа, к которым существует путь заданной...

Определить, какие вершины достижимы из заданной вершины S - C++
Подскажите алгоритм для этой задачи, пожалуйста. Достижимые вершины Имя входного файла: graph.in Имя выходного файла: graph.out...

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

Считать граф из файла (граф задан матрицей) представить его в виде списка и записать список заново в файл - C++
помогите очень срочно надо. считать граф из файла (граф задан матрицей) представить его в виде списка и записать список заново в файл ...

Дано ребро куба - C++
Помогите!!!! Нужно сделать в С++ 1. Дано ребро куба. Вычислить площадь поверхности шара, вписанного в него. 2. Найти сумму натуральных...

Как удалить ребро в графе? - C++
Имеется граф с N вершинами и заданный списком смежности. Требуется удалить ребро, который соединяет вершины a и b. Ребро задается...


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

Или воспользуйтесь поиском по форуму:
__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
Ответ Создать тему
Опции темы

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