LINUX.ORG.RU
ФорумTalks

нужна помощь.


0

0

привет всем,

ребят у меня следующея проблема:

дано:

1,7|1,2|1,3|3,5|2,4|7,6|5,6

нужно найти цилк в который для данного примера выглядел бы так:

1,3|3,5|5,6|7,6|1,7

подкиньте пожалусто пару идей, как мне это сделать?

буду очень благодарен.

★★

Ответ на: комментарий от Deleted

да именно графы, то что сверху то нам дан граф, и в нём нужно найти цилк.

хотя, я не совсем правельно показал

дано вот что:

1,7|1,2|1,3|3,5|2,4|7,6

в этот граф мы добавляем ребро 5,6, потом нужно найти цикл, иммено от этого ребра.

как условие можно понять, что после добавления нового ребра, будет обязательно образован цикл. вот его и надо найти. надеюсь понятно обяснил =)

djung ★★
() автор топика
Ответ на: комментарий от djung

> как условие можно понять, что после добавления нового ребра, будет обязательно образован цикл. вот его и надо найти. надеюсь понятно обяснил =)

Определяешь, к какой компоненте связности принадлежит каждая вершина. потом, если у добавляемого ребра начало и конец лежат в одной компоненте связности и ранее между ними ребра не было, то цикл обязательно появится. В случае дерева --- ровно один.

Если этого мало, то берёшь любую из конечных вершин и находишь цикл, содержащий её. Если компонента связности бфла деревом, то найденный цикл будет единственным циклом, содержащим данное ребро. Иначе придётся перебрать все циклы, проходящие через выбранную вершину и выбираешь те, которые проходят через добавленное ребро.

Определения и алгоритмы поиска можно найти даже в русской википедии.

gaa ★★
()
Ответ на: комментарий от gaa

И ещё: в случае, если ребро было добавлено в дерево, то цикл легко найти простым подъёмом от выбранных вершин до корня.

gaa ★★
()
Ответ на: комментарий от djung

> пасиба, сделал , не совсем так как ты написал, но всё равно помогло =)

"... Огромное спасибо Вам за рецепт. Дома мы тоже приготовили это блюдо. Правда все компоненты мы заменили вареной картошкой, а вместо "Божоле" урожая 1978 года мы влили столовый уксус. Но было очень вкусно. Спасибо!!!"

gaa ★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.