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

@metaline · Регистрация: 09.03.2014

Author24 — интернет-сервис помощи студентам

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

Дан граф из 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

@__General__ · 04.05.2014, 14:02

metaline, У тебя есть граф, заданный списком смежности, т. е. есть список вершин графа, а в каждой вершине хранится список инцидентных ей ребер (т. е. фактически, в каждой вершине хранится список указателей на ее смежные вершины). Если ты имел дело со связными списками, то решение задачки не составит для тебя труда.

В твоей программе тебе понадобится:
1) найти вершины u и v в списке вершин (в цикле просматриваешь все вершины, пока не наткнешься на вершину с нужным номером);
2) добавить ребро между вершинами u и v (т. е. в список ребер, инцидентных вершине u добавить элемент: ребро с указателем на вершину v и наоборот);
3) В цикле просмотреть списки ребер, инцидентных вершинам u и v, и вывести номера смежных вершин.

@metaline · 04.05.2014, 20:33 **[ТС]**

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

@__General__ · 05.05.2014, 15:27

metaline, Ну например можно вместо того, чтобы считывать числа с помощью cin, считать данные из файла в массив символов с помощью getline(...). Это немного хлопотно, зато считаются все символы, включая пробелы и символ перехода на следующую строку. А из условия задачи мы знаем, что первое число после символа перехода на следующую строку - это номер самой вершины, а все последующие номера вершин до следующего символа перехода на следующую строку - номера вершин, смежных ей.

@metaline 1 / 1 / 1 Регистрация: 09.03.2014 Сообщений: 8
		1
	Добавить в граф ребро, соединяющее вершины u и v 04.05.2014, 13:21. Показов 5211. Ответов 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 0

@__General__ 25 / 25 / 12 Регистрация: 04.01.2014 Сообщений: 91
	04.05.2014, 14:02	2
	metaline, У тебя есть граф, заданный списком смежности, т. е. есть список вершин графа, а в каждой вершине хранится список инцидентных ей ребер (т. е. фактически, в каждой вершине хранится список указателей на ее смежные вершины). Если ты имел дело со связными списками, то решение задачки не составит для тебя труда. В твоей программе тебе понадобится: 1) найти вершины u и v в списке вершин (в цикле просматриваешь все вершины, пока не наткнешься на вершину с нужным номером); 2) добавить ребро между вершинами u и v (т. е. в список ребер, инцидентных вершине u добавить элемент: ребро с указателем на вершину v и наоборот); 3) В цикле просмотреть списки ребер, инцидентных вершинам u и v, и вывести номера смежных вершин. 0

@metaline 1 / 1 / 1 Регистрация: 09.03.2014 Сообщений: 8
	04.05.2014, 20:33 [ТС]	3
	__General__ спасибо большое за подсказку. но у меня есть еще вопрос, а именно, как считывать данные из файла, ведь они будут читаться сплошняком, и как отделить например номер вершины, от номеров смежной ей. 0

@__General__ 25 / 25 / 12 Регистрация: 04.01.2014 Сообщений: 91
	05.05.2014, 15:27	4
	metaline, Ну например можно вместо того, чтобы считывать числа с помощью cin, считать данные из файла в массив символов с помощью getline(...). Это немного хлопотно, зато считаются все символы, включая пробелы и символ перехода на следующую строку. А из условия задачи мы знаем, что первое число после символа перехода на следующую строку - это номер самой вершины, а все последующие номера вершин до следующего символа перехода на следующую строку - номера вершин, смежных ей. 0