Для каждой вершины графа найдите все вершины на расстоянии d - PullRequest
Новая
       47

Для каждой вершины графа найдите все вершины на расстоянии d

4 голосов
/ 16 апреля 2011

В моем конкретном случае график представлен в виде списка смежности и является ненаправленным и разреженным, n может быть в миллионах, а d равно 3. Вычисление A ^ d (где A - матрица смежности) и выборканенулевые записи работают, но я бы хотел что-то, что не связано с умножением матриц.Поиск в ширину по каждой вершине также возможен, но он медленный.

Ответы [ 4 ]

1 голос
/ 11 октября 2013 
def find_d(graph, start, st, d=0):

    if d == 0:
        st.add(start)
    else:
        st.add(start)
        for edge in graph[start]:
            find_d(graph, edge, st, d-1)

    return st

graph = { 1 : [2, 3],
      2 : [1, 4, 5, 6],
      3 : [1, 4],
      4 : [2, 3, 5],
      5 : [2, 4, 6],
      6 : [2, 5]
    }

print find_d(graph, 1, set(), 2)
0 голосов
/ 19 апреля 2011

Вы уже упомянули возможность расчета A^d, но это намного, намного больше, чем вам нужно (как вы уже заметили).

Однако, есть гораздо более дешевый способ использования этой идеи.,Предположим, у вас есть (столбец) вектор v нулей и единиц, представляющих набор вершин.Вектор w := A v теперь имеет единицу на каждом узле, которая может быть достигнута от начального узла ровно за один шаг.Итерируя, u := A w имеет по одному для каждого узла, который вы можете получить от начального узла ровно в два шага и т. Д.

Для d=3 вы можете сделать следующее (псевдокод MATLAB): 

v = j'th unit vector
w = v
for i = (1:d)
   v = A*v
   w = w + v
end

вектор w теперь имеет положительную запись для каждого узла, к которому можно получить доступ из j-го узла за самое большее d шагов.

0 голосов
/ 19 апреля 2011

Поиск в ширину, начиная с заданной вершины, является в этом случае оптимальным решением.Вы найдете все вершины, которые находятся на расстоянии d, и вы никогда не будете посещать вершины с расстоянием> = d + 2.

Вот рекурсивный код, хотя при желании рекурсию можно легко устранитьиспользуя очередь. 

// Returns a Set
Set<Node> getNodesWithinDist(Node x, int d)
{
  Set<Node> s = new HashSet<Node>();  // our return value
  if (d == 0) {
    s.add(x);
  } else {
    for (Node y: adjList(x)) {
       s.addAll(getNodesWithinDist(y,d-1);
    }
  }
  return s;
}
0 голосов
/ 16 апреля 2011

Скажем, у нас есть функция verticesWithin(d,x), которая находит все вершины на расстоянии d от вершины x.

Одной из хороших стратегий решения такой проблемы, как раскрытие возможностей кэширования / запоминания, является задание вопроса: Как подзадачи этой проблемы связаны друг с другом?

В этом случае мы можем видеть, что verticesWithin(d,x), если d >= 1 - это объединение vertices(d-1,y[i]) для всех i в пределах диапазона, где y=verticesWithin(1,x). Если d == 0, то это просто {x}. (Я предполагаю, что вершина считается на расстоянии 0 от себя.)

На практике вы захотите посмотреть список смежности для случая d == 1, а не использовать это отношение, чтобы избежать бесконечного цикла. Вы также захотите избежать избыточности, считая x самим членом y.

Кроме того, если тип возвращаемого значения verticesWithin(d,x) изменяется с простого списка или набора на список d наборов, представляющих увеличивающееся расстояние от x, то

verticesWithin(d,x) = init(verticesWithin(d+1,x))

где init - функция, которая возвращает все элементы списка, кроме последнего. Очевидно, что это будет неразрывное рекурсивное отношение, если оно будет транскрибировано буквально в коде, поэтому вы должны быть немного сообразительны о том, как вы его реализуете.

Благодаря этим отношениям между подзадачами мы можем теперь кэшировать результаты verticesWithin и использовать эти кэшированные результаты, чтобы избежать выполнения избыточных обходов (хотя и за счет выполнения некоторых операций над множествами - я не совсем уверен, что это победа). Я оставлю это как упражнение, чтобы заполнить детали реализации.

...