CODEWITHSUNDEEP
crecursionadjacency-matrix
user10830454
user10830454

Reputation:

C - Depth first search in adjacency matrix using recursion

I have a recursion problem I would like to solve using recursion.

For example, given this adjacency matrix 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

Say I would like to look at column 0 and all of its neighbors, and its neighbors' neighbors (distance of 2), and store all of the row indices > 0 into a linked list of ints.

Here is my updated code:

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;
}

It currently does not return the expected output (which is 0, 1, and 2 in the linked list), but I am not sure why. Any help or direction is appreciated.

Upvotes: 1

Views: 593

Answers (1)

M Oehm
M Oehm

Reputation: 29126

You have two major misconceptions in your code. The first is about recursion and the second is about how an adjacency matrix works.

The recursion basically works like this:

  • take a node and a max. distance: func(node, d);
  • if the distance is negative, return
  • add the node to the list;
  • for all adjacent nodes, call the function on that node and with a new, now shorter distance: func(next, d - dist(node, next).

To find all nodes in the vicinity of node #0, you'd start with an empty list and then call func(0, 2), which will lead to the following calls:

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

This recursion will eventually stop, because you diminish the distance in each step. This is important: Every recursion must have a termination condition otherwise it would recurse endlessly. (It is a matter of style whether you test the distance up front or when you recurse. Up font catches invalid input early, but may lead to useless "dead" recursions.)

The recursion as given has a subtle problem: When you call func(0, 2) the function will add node #0 twice, because going from node 0 to 1 and then back to 0 yields a distance of 2, which is within reach. There are several ways to solve this. For example you could look whether the given node is already in your list. Or you could flag nodes as visited as you go.

The adjacency matrix determines whether two nodes are connected. Two nodes a and b are connected if adj[a][b] != 0. That means that if you want to find all neighbours next of a given node node, you should do something like this:

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

You don't need two nested loops. The matrix has two dimensions, but the first one is always fixed: it's the source node. (If you look at your code, you'll see that you don't do anything with i.)

In your case, the adjacency matrix seems to have values of 0 and 1 only, but it could have other non-zero values to indicate the distances of a weighted graph.

Upvotes: 3

Related Questions