Нахождение количества вершин на меньшем или равном расстоянии d от вершины x

Я должен использовать обход графа (я думал о BST), чтобы определить, сколько вершин в g находится на расстоянии v меньше или равно N, это путешествие, на котором расстояние равно N ou меньше ребер.

int succN (Grafo g, int v, int N)

У меня есть эта структура для работы:

#define MAX 100

typedef int WEIGHT;

struct edge {
   int dest;
   WEIGHT weight;
   struct edge *next;
};

typedef struct edge Edge;
typedef struct edge *GraphL[MAX];

Мне трудно сделать эффективное решение в c. Единственный способ, который я вижу сейчас, это сделать рекурсивный вызов вспомогательной функции с помощью BST.


c graph algorithm graph-traversal
person Community    schedule 25.12.2016    source источник
comment
Вы можете изучить алгоритм Дейкстры. В зависимости от условия цикла вы можете либо найти кратчайший путь к целевому узлу, не обязательно посещая все узлы; или посетить все узлы (один раз) и найти кратчайшее расстояние до каждого с самого начала. Оба варианта использования составляют эффективный алгоритм.   -  person Weather Vane    schedule 25.12.2016
comment
@WeatherVane В данном конкретном случае вес равен 1, потому что это не взвешенный график. Могу ли я по-прежнему использовать алгоритм Дейкстры?   -  person    schedule 25.12.2016
comment
Да, вы можете сделать.   -  person Weather Vane    schedule 25.12.2016
comment
Можете ли вы изменить структуру? Например, добавить поля для стека.   -  person David Eisenstat    schedule 25.12.2016
comment
Вот пример Dijkstra's алгоритм в другом контексте, но идеи будут теми же. Обычно мне не нужен вызов для изучения соседей (Дейкстра не рекурсивен), но здесь это было удобно. То, как вы исследуете связанные узлы, зависит от их метода кодирования — например, связанного списка связанных узлов. Пример находит один кратчайший маршрут, но если основной цикл изменить на while(1) и вы прерветесь, когда listlen == 0 вы найдете расстояние всех узлов от начального узла.   -  person Weather Vane    schedule 25.12.2016
comment
@DavidEisenstat, к сожалению, я не могу изменить структуру.   -  person    schedule 25.12.2016
comment
@WeatherVane, я собираюсь взглянуть на это решение   -  person    schedule 25.12.2016

Ответы (1)


arrow_upward
1
arrow_downward

Если ваши веса неотрицательны, вы можете использовать алгоритм Дейкстры Вот простой псевдокод. Он имеет временную сложность O(n^2) (n = количество узлов).

ans = 0
dist[0 .. n-1, None] = {INF, ..., INF}
dist[v] = 0
iterate n times
   best = None

   for each node u
      if not seen[u] and dist[u] < dist[best]
         best = u

   if dist[best] > N
      break

   seen[best] = true
   ans++
   for each edge from best (going to v, of weight w)
      if dist[best] + w < dist[v]
         dist[v] = dist[best] + w

return ans

Если все ваши веса равны 1 (как вы указываете в комментариях), то breadth- первого поиска будет достаточно.

person md5    schedule 26.12.2016