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

[mamba]

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

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

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

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

[mamba]

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

[Lapp]

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

Погоди.. Если из вершины 1 можно попасть в любую другую - не значит ли это, что он связный? Ведь из любой можно попасть в 1-ую, а потом в любую другую. Разве не так?..

[Lapp]

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

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

Данная реализация использует множества и поэтому ограничена по количеству вершин графа числом 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
Мне по-прежнему кажется, что более простой признак должен существовать.. Кто-нить знает его?

[Гость]

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

[Гость]

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

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

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

[Lapp]

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

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

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

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

Все.

[mamba]

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

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