Задча на граф Опции

[r-d-v2008]

Люди помогите пожалуйста решить задачу: Проверьте, содержит ли граф, заданный с помощью списков инцидентности, вершину, в которую входят дуги от всех остальных вершин графа, но из которой не исходит ни одна дуга.

[volvo]

Что такое список инцидентности - знаешь? Реализация этого списка есть у тебя? Где, собственно, граф, который надо проверить?

Если знаешь, что такое списки инцидентности - то задачу решишь без труда. Достаточно просто пройти по массиву указателей, и проверить, есть ли там указатели, равные Nil... Если таких нет - то из каждой вершины что-то да выходит, ответ на твой вопрос - "Нет". Если nil есть (причем ровно 1 - больше тоже быть не должно, подумай, почему) - то ходить по всем указателям, не равным Nil, как по спискам, и проверять, есть ли в каждом из списков вершина с индексом, равным индексу того самого злополучного Nil-а. Если везде, во всех просмотренных списках есть такая вершина - значит, ответ "Да", иначе - опять "Нет". На этот раз ответ окончательный, больше ничего проверять не надо...

Все просто, как видишь. Осталось всего лишь этот алгоритм запрограммировать...

[-r-d-v2008-]

За алгоритм спасибо, а как это организовать на паскале?

[volvo]

Вообще-то задачу дали тебе, а не мне, правда?

Вот так реализуется алгоритм:

function f(const mx: TIncidence): boolean;
var
  count: integer;
  i, Vx: Vertexes;
  found: boolean;
  p: PList;
begin
  f := false;

  count := 0;
  for i := 1 to LastVertex do
    if mx[i] = nil then
    begin
      Inc(count); Vx := i;
    end;

  if count > 1 then exit { <-- result = false }
  else begin

    for i := 1 to LastVertex do
      if i <> Vx then
      begin
        p := mx[i];
        found := false;
        while (p <> nil) and (not found) do
        begin
          if p^.Vertex = Vx then found := true;
          p := p^.next;
        end;

        if not found then exit; { <-- result = false }
      end;

  end;

  f := true;
end;

Но чтобы проверить его работоспособность, тебе придется самому описать тип TIncidence и все остальные, а также написать основную программу так, чтобы эта программа хотя бы откомпилировалась. Кроме этого, матрицу инцидентности еще придется заполнить, чтобы проверить, правильно ли функция отрабатывает (на нескольких вариантах, разумеется, когда она должна возвращать "истину", и когда - "ложь"). Но все это - уже самостоятельно. Я ни за кого задачи не решаю полностью. Халявы не будет...

[r-d-v2008]

Спасибо за реализацию алгоритма на паскале, премного благодарен!!!!!! Все остальное я сделаю сам.