Форум программистов [Powered by Invision Power Board]

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

Форум программистов > Алгоритмы > Как найти ексцентриситет вершины в графе?

Автор: Coder 23.5.2006, 01:35

Помогите с алгоритмом. я пытался свой изобрести ни к чему не привело.
эксцентриситет - это наиболее удаленая вершина от данной.

Автор: maxim1000 23.5.2006, 01:46

хм... вообще-то на первый взгляд проблем не видно...
пускаем волну из начальной точки:
ей даём метку 0
всем её соседям - метку 1
всем их непомеченным соседям метку 2
и т.д., пока есть, что метить
потом просто берём вершину с максимальной меткой...

Автор: Coder 23.5.2006, 01:58

я только начал знакомиться с теорией графов. примерчик бы. я нашел вот такой алгоритм http://alice.stup.ac.ru/math/extensions/analize/index.html, но язык меня не устраивает. многие процедуры не понятны. мне бы на C или Pascal

Автор: maxim1000 23.5.2006, 10:15

Цитата(Coder @ 23.5.2006, 00:58

)

я только начал знакомиться с теорией графов. примерчик бы.

так а что не понятно в реализации той последовательности, которую я описал?

Автор: Coder 23.5.2006, 12:46

если вершина 1 соеденина с 2 и 3, то они имеют одинаковый "вес" = 1. Я их нумерую. Далее перехожу на вершину 2 и смотрю что соединено с ней и присваиваю вес = 2 и т.д. , но как мне потом правильно вернуться на вершину 3?
Это мне нужно сдела

Автор: maxim1000 23.5.2006, 15:15

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

Добавлено @ 15:17
что-то типа

Код


for(x - вершина графа)
  if(метка x==n)
    for(y - сосед x)
      if(y без метки)
        установить метку y=n+1

Автор: Coder 24.5.2006, 06:59

Списибо, maxim1000, за первый топик! Я все же написал алгоритм опираясь на него. Получилось думаю не оптимально, но все работает!
Проблема была в том что я не мог "запомнить" в прграмме с какой вершины ушел для пометки ее соседей, но я создал массив-стек и запихивал туда все вершины к тором еще нужно возвратиться.
вот основной кусок кода:

Код


  while (replay) do
  begin
    replay:=false;
    for j:=1 to v do // ищем вершины с текущим уровнем
      if (point[j]=lev) then
        begin
          inc(t_count); // запоминаем их кол-во
          tt[t_count]:=j; // и записываем каждую в массив
        end;
    inc(lev); // увеличиваем уровень

    for q:=1 to t_count do // здесь меняются вершины с одним уровнем
      for i:=1 to v do // заполняем окрестности текущей вершины
       if (matrix[tt[q],i]=1) and (point[i]=$ff) then
          begin
            replay:=true;
            point[i]:=lev;
          end;
    t_count:=0;
  end;