Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Правильность построения графа.

Автор: mamba 29.11.2007 1:36

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

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

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

Автор: mamba 29.11.2007 2:02

и я не прошу текста, сама справлюсь, просто у меня что то даже идей нету. Ну они есть, но неправильные) очень прошу помочь)

Автор: Lapp 29.11.2007 8:31

Цитата(mamba @ 28.11.2007 21:36) *
чтобы обязательно был хотя бы один путь из 1 в n вершину. ( граф НЕ обязательно должен быть связным, т е не обязательно, чтобы был путь из каждой вершины в каждую).
Погоди.. Если из вершины 1 можно попасть в любую другую - не значит ли это, что он связный? Ведь из любой можно попасть в 1-ую, а потом в любую другую. Разве не так?..

Автор: Lapp 29.11.2007 11:14

Цитата(mamba @ 28.11.2007 22:02) *

не прошу текста, сама справлюсь, просто у меня что то даже идей нету.

Хм.. Я уважаю такой подход, но программеру проще накатать текст, чем объяснять.. smile.gif
Сначала я пытался найти простой признак (типа суммировать как-нить элементы), но потом оставил попытки и сделал в лоб.
Процесс рекурсивный.
Сначала множество InReach (Доступные) пусто.
Берем первую вершину, от которой мы отталкиваемся (в данном случае - первую), добавляем ее к множеству InReach и проходим по строке с ее номером. Если встречаем связь с вершиной, которая еще не в числе доступных - прыгаем на эту вершину и делаем с ней то же самое (рекурсия).
В результате множество InReach содержит все вершины, доступные из первой. Если оно содержит все вершины графа, то ответ на вопрос задания положительный, если нет - то отрицательный smile.gif.

Данная реализация использует множества и поэтому ограничена по количеству вершин графа числом 255. Это можно обойти при желании..

Вот, что получилось:
const
m=100;

var
Link: array[1..m,1..m]of byte;
InReach: set of byte;
v,i,j,k,n: byte;
AllReached: boolean;
f: text;

procedure Reached(v:byte);
var
i: byte;
begin
Include(InReach,v);
for i:=1 to n do begin
if (Link[v,i]=1) and not (i in InReach) then Reached(i)
end;
end;

begin
{Reading File}
Assign(f,'mamba.txt');
Reset(f);
ReadLn(f,n);
for i:=1 to n-1 do begin
for j:=i+1 to n do begin
Read(f,Link[i,j]);
Link[j,i]:=Link[i,j]
end;
ReadLn(f)
end;
Close(f);

{Printing the Matrix}
for i:=1 to n do begin
for j:=1 to n do Write(Link[i,j]:2);
WriteLn
end;

{Work}
InReach:=[];
Reached(1);

{Pribting the result}
AllReached:=true;
for i:=1 to n do AllReached:=AllReached and (i in InReach);
if AllReached then WriteLn('All verteces are in reach') else WriteLn('Some vertices are unreachable');
ReadLn
end.

В качестве входных данных используется файл mamba.txt, в котором сначала идет число вершин в графе, а потом верхняя половинка матрицы (без главной диагонали). Вот пример входного файла для графа из 6 вершин:
6
1 1 0 1 0
0 1 0 0
0 0 0
0 0
0

Для этой матрицы ответ отрицательный.

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

Автор: Гость 29.11.2007 18:51

из 1 в n - то есть из первой в последнюю.Просто,чтобы можно было попасть, пусть за несколько переходов. Т.е у нас, допустим, 4 вершины. есть пути 1--2 и 3--4. Нельзя попасть из 1ой в четвертую никак. А если бы было 1--2 2--3 3--4, то видно, что можно. Вот пытаюсь сделать проверку.

Автор: Гость 29.11.2007 18:56

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

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


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

Автор: Lapp 29.11.2007 19:09

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

Цитата(Гость @ 29.11.2007 14:56) *
о, мне просто надо изменить, чтобы проверка шла не на содержание множеством всех вершин, а на содержание вершины n. (например 6)... *пошла думать =))
Да, именно так. Странно, почему-то я понял так, что тебе нужно в каждую.. глюки, извини. Если просто одну n-ную (ага, понял.. ты не пишешь окончания - видимо, "для краткости" - и я просто взял не ту форму от n) вершину - нет проблем. Просто последнюю группу операторов нужно заменить примерно на следующее:

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

Все.

Автор: mamba 30.11.2007 1:19

Огромное спасибо! rolleyes.gif

З.Ы: да,забыла, но уже вспомнила =)