Правильность построения графа. Опции

[mamba]

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

Нам дана матрица смежности n*n (n - количество врешин в графе.) Если путь из i в j есть, то массив[i,j]=1 и массив[j,i]=1, если нет - то 0. Как мне по такой вот матрице проверить правильность построения графа, то есть чтобы обязательно был хотя бы один путь из 1 в n вершину. ( граф НЕ обязательно должен быть связным, т е не обязательно, чтобы был путь из каждой вершины в каждую).

Заранее спасибо за помощь.

Сообщение отредактировано: mamba - 29.11.2007 1:38

[Гость]

В результате множество InReach содержит все вершины, доступные из первой. Если оно содержит все вершины графа, то ответ на вопрос задания положительный, если нет - то отрицательный

В результате множество InReach содержит все вершины, доступные из первой. Если оно содержит все вершины графа, то ответ на вопрос задания положительный, если нет - то отрицательный

о, мне просто надо изменить, чтобы проверка шла не на содержание множеством всех вершин, а на содержание вершины n. (например 6)... *пошла думать =))

[Lapp]

mamba, это ты? забыла пароль? выслать?

о, мне просто надо изменить, чтобы проверка шла не на содержание множеством всех вершин, а на содержание вершины n. (например 6)... *пошла думать =))

Да, именно так. Странно, почему-то я понял так, что тебе нужно в каждую.. глюки, извини. Если просто одну n-ную (ага, понял.. ты не пишешь окончания - видимо, "для краткости" - и я просто взял не ту форму от n) вершину - нет проблем. Просто последнюю группу операторов нужно заменить примерно на следующее:

if n in InReach then WriteLn('Connected!') else WriteLn('Disconnected..');

Все.