Найти все возможные пути между двумя узлами в неориентированном графе - PullRequest
0 голосов
/ 21 мая 2010

Кто-нибудь может дать мне C-код, чтобы найти все возможные пути между двумя узлами? например. если граф имеет следующие ребра 1-2 1-3 2-3 2-4 3-4

все пути от 1 до 4:

1-2-3-4

1-2-4

1-3-4

1-3-2-4

Ответы [ 5 ]

3 голосов
/ 21 мая 2010

Поиск в глубину делает эту работу.

0 голосов
/ 11 апреля 2014

Слишком поздно и не код C, но может помочь другим. Этот алгоритм показывает, как я реализую его в Java.

findPath(start) 
    Childs = getDirectChildsOf(start)
    foreach child in Childs
        tempRoute;
        tempRoute.add(start)
        if (child == end)
            return tempRoute.add(child) 
        else 
            tempRoute.add(findPath(child))
            if (tempRoute.last() == end)
                return tempRoute;

Здесь tempRoute может быть классом Route, который поддерживает список узлов. Возможность добавить один node и другие route к tempRoute. Также не найти все возможные пути. для этого необходимо поддерживать флаг посещения для каждого узла.

0 голосов
/ 21 мая 2010

рекурсивный метод:

findPaths(path = startNode, goal)
    paths = []
    if the last node in path is goal:
        return path
    for each node n connected to the last node in path:
        if n is not already on the path:
            paths.append(findPaths(path.append(node), goal))
    return paths //may still be []
0 голосов
/ 21 мая 2010

Это простой алгоритм к проблеме. Это не оптимальный алгоритм.

static struct {
  int value1;
  int value2;
  int used;
} data[] = {
  { 1, 2 },
  { 1, 3 },
  { 2, 3 },
  { 2, 4 },
  { 3, 4 },
};

enum { DATA_SIZE = sizeof data / sizeof *data };

static int output[DATA_SIZE];

int traverse(int from, int to, int depth) {
  output[depth++] = from;

  int i;
  if (from == to) {
    for (i = 0; i < depth; i++) {
      if (i) {
        printf("-");
      }
      printf("%d", output[i]);
    }
    printf("\n");
  } else {
    for (i = 0; i < DATA_SIZE; i++) {
      if (!data[i].used) {
        data[i].used = 1;

        if (from == data[i].value1) {
          traverse(data[i].value2, to, depth);
        } else if (from == data[i].value2) {
          traverse(data[i].value1, to, depth);
        }

        data[i].used = 0;
      }
    }
  }
}

int main() {
  traverse(1, 4, 0);
}
0 голосов
/ 21 мая 2010

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

Вы можете сделать расслабление:

while (there is a change) {
  for (v in nodes(G)) {
    for (e in edges(v)) {
      paths_to[v] = paths_to[v] union ((paths_to[e.to] not containing v) append v)
    }
  }
}

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...