C - Поиск глубины в матрице смежности с использованием рекурсии

Question

У меня есть проблема рекурсии, которую я хотел бы решить с помощью рекурсии.

Например, учитывая эту матрицу смежности AdjMat:

  0 1 2 3 
0 0 1 0 0
1 1 0 1 0
2 0 1 0 1
3 0 0 1 0

Скажем, я хотел бы взглянуть на столбец 0 ивсех его соседей и соседей его соседей (расстояние 2), и хранят все индексы строк> 0 в связанном списке целых.

Вот мой обновленный код:

intNode *Neighbors(intNode *head, int colOfInterest, int distance) {
    int x = colOfInterest; 

    if (distance == 0) {
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
               if (AdjMat[x][j] > 0) { 
                   head = insertInt(head, j);
               }
            }
            break;
        }
    }
    intNode *subpath = NULL;
    for (int i = 0; i < distance; i++) {
        subpath = Neighbors(head, colOfInterest, distance);
    }
    // Once the final neighbor column has been reached, add elements to the linked list.
    return head;
} 

В настоящее время он не возвращает ожидаемый результат (0, 1 и 2 в связанном списке), но я не уверен, почему,Любая помощь или направление приветствуется.

Answer 1

У вас есть два основных заблуждения в вашем коде.Первый - о рекурсии, а второй - о том, как работает матрица смежности.

Рекурсия в основном работает так:

• принимает узел и макс.расстояние: func(node, d);
• если расстояние отрицательное, верните
• , добавьте узел в список;
• для всех соседних узлов, вызовите функцию на этом узле ис новым, теперь более коротким расстоянием: func(next, d - dist(node, next).

Чтобы найти все узлы в окрестности узла # 0, вы должны начать с пустого списка, а затем вызвать func(0, 2), чтопривести к следующим вызовам:

func(0, 2)                  // list {0}
    func(1, 1)              // list {0, 1}
        func(0, 0)          // list {0, 1, 0}          error, see below
            func(1, -1)     // negative d, do nothing
        func(2, 0)          // list {0, 1, 0, 2}
             func(1, -1)    // negative d, do nothing
             func(3, -1)    // negative d, do nothing

--> recursion depth

Эта рекурсия в конечном итоге прекратится, потому что вы уменьшаете расстояние на каждом шаге.Это важно: каждая рекурсия должна иметь условие завершения, иначе она будет бесконечно повторяться.(Это вопрос стиля, независимо от того, тестируете ли вы дистанцию ​​впереди или когда выполняете рекурсию. Шрифт Up обнаруживает неверный ввод рано, но может привести к бесполезным «мертвым» рекурсиям.)

Рекурсия в том виде, в каком она естьпроблема: когда вы вызываете func(0, 2), функция добавит узел # 0 дважды, потому что переход от узла 0 к 1, а затем обратно к 0 дает расстояние 2, которое находится в пределах досягаемости.Есть несколько способов решить эту проблему.Например, вы можете посмотреть, есть ли данный узел в вашем списке.Или вы можете пометить узлы как посещенные на ходу.

Матрица смежности определяет, связаны ли два узла.Два узла a и b связаны, если adj[a][b] != 0.Это означает, что если вы хотите найти всех соседей next данного узла node, вы должны сделать что-то вроде этого:

for (int next = 0; next < N; next++) {
    if (adj[node][next]) {
        // do something with next
    }
}

Вам не нужно два вложенных цикла.Матрица имеет два измерения, но первое всегда фиксированное: это исходный узел.(Если вы посмотрите на свой код, вы увидите, что ничего не делаете с i.)

В вашем случае матрица смежности, кажется, имеет значения только 0 и 1, но онаможет иметь другие ненулевые значения для обозначения расстояний взвешенного графика.