How to traverse through a adjacency matrix?

algorithm, graph-algorithm, tree

Solution

Given the constraints of your example it doesn't take more than some 40 lines to code.

Essentially you just keep visiting nodes connected to the one you are currently inspecting. Tracking backing once you figure out there are no new nodes to visit.

Additionally you'll need some means to keep track of the path you traveled to the current node. In the example I just put this info onto the stack to safe me from some memory management headache.

#include <stdio.h>

#define N_NODES 4
#define NAME_OFFSET 1

int edges[N_NODES][N_NODES] = {
    { 0, 1, 1, 0 },
    { 1, 0, 1, 0 },
    { 1, 1, 0, 0 },
    { 0, 0, 0, 0 }
};

int visited[N_NODES] = { 0, 0, 0, 0 };

struct Node {
    int node;
    struct Node *prev;
};

void visit(int node, struct Node *prev_node) {
    struct Node n = { node, prev_node };
    struct Node *p = &n;

    do 
        printf("%d%s", p->node + NAME_OFFSET, (p->prev != NULL)?  "->" : "\n");
    while ((p = p->prev) != NULL);

    visited[node]=1;
    int i;
    for (i = 0; i < N_NODES; ++i)
        if ((visited[i] == 0) && (edges[node][i] == 1))
            visit(i, &n);
    visited[node] = 0;
}

int main (int argc, char *argv[]) {
    int i;
    for (i = 0; i < N_NODES; ++i) {
        visit(i, NULL);
    }
    return 0;
}

Produces:

1
2->1
3->2->1
3->1
2->3->1
2
1->2
3->1->2
3->2
1->3->2
3
1->3
2->1->3
2->3
1->2->3
4

I guess that's what you were looking for.

Problem

A adjacency matrix presents connections between nodes in a arbitrary tree. Here is a instance of adjacency matrix which presents a undirected graph: ``` 1 2 3 4 1 0 1 1 0 2 1 0 1 0 3 1 1 0 0 4 0 0 0 0 ``` This matrix presents a graph where nodes 1 and 2 are connected, 1 and 3 are connected, 2 and 3 are connected. How to bruteforce all combinations of possible paths in such a graph using this kind of matrix? I mean that picking just node 1 is a separate combination. Then, say, 1-2 is a separate combination. 1-2-3; 3-1-2. But 1-2-3-1 is not possible, because of double picking the same node. So how to bruteforce all combinations using these rules? I prefer C#, C++ or Java language samples)

Original source