VPF::Как найти ексцентриситет вершины в графе?

Coder

Дата 23.5.2006, 01:35 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 733
Регистрация: 13.12.2004

Репутация: нет
Всего: 11

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

Это сообщение отредактировал(а) Coder - 23.5.2006, 01:45

maxim1000

Дата 23.5.2006, 01:46 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110

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

--------------------

qqq

Coder

Дата 23.5.2006, 01:58 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 733
Регистрация: 13.12.2004

Репутация: нет
Всего: 11

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

maxim1000

Дата 23.5.2006, 10:15 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110

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

)

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

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

--------------------

qqq

Coder

Дата 23.5.2006, 12:46 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 733
Регистрация: 13.12.2004

Репутация: нет
Всего: 11

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

maxim1000

Дата 23.5.2006, 15:15 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110

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

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

Код


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

--------------------

qqq

Coder

Дата 24.5.2006, 06:59 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 733
Регистрация: 13.12.2004

Репутация: нет
Всего: 11

Списибо, 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;

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »