1. Заголовок темы должен быть информативным. В противном случае тема удаляется ... 2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения. 3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали! 4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора). 5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM! 6. Одна тема - один вопрос (задача) 7.Проверяйте программы перед тем, как разместить их на форуме!!! 8.Спрашивайте и отвечайте четко и по существу!!!
Всем доброго времени суток мне нужна помощь по одной задачке, у самой не получается...
Нам дана матрица смежности n*n (n - количество врешин в графе.) Если путь из i в j есть, то массив[i,j]=1 и массив[j,i]=1, если нет - то 0. Как мне по такой вот матрице проверить правильность построения графа, то есть чтобы обязательно был хотя бы один путь из 1 в n вершину. ( граф НЕ обязательно должен быть связным, т е не обязательно, чтобы был путь из каждой вершины в каждую).
чтобы обязательно был хотя бы один путь из 1 в n вершину. ( граф НЕ обязательно должен быть связным, т е не обязательно, чтобы был путь из каждой вершины в каждую).
Погоди.. Если из вершины 1 можно попасть в любую другую - не значит ли это, что он связный? Ведь из любой можно попасть в 1-ую, а потом в любую другую. Разве не так?..
--------------------
я - ветер, я северный холодный ветер я час расставанья, я год возвращенья домой
не прошу текста, сама справлюсь, просто у меня что то даже идей нету.
Хм.. Я уважаю такой подход, но программеру проще накатать текст, чем объяснять.. Сначала я пытался найти простой признак (типа суммировать как-нить элементы), но потом оставил попытки и сделал в лоб. Процесс рекурсивный. Сначала множество 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)... *пошла думать =))
о, мне просто надо изменить, чтобы проверка шла не на содержание множеством всех вершин, а на содержание вершины n. (например 6)... *пошла думать =))
Да, именно так. Странно, почему-то я понял так, что тебе нужно в каждую.. глюки, извини. Если просто одну n-ную (ага, понял.. ты не пишешь окончания - видимо, "для краткости" - и я просто взял не ту форму от n) вершину - нет проблем. Просто последнюю группу операторов нужно заменить примерно на следующее:
if n in InReach then WriteLn('Connected!') else WriteLn('Disconnected..');
Все.
--------------------
я - ветер, я северный холодный ветер я час расставанья, я год возвращенья домой