CODEWITHSUNDEEP
algorithmmatrixgraph
Dylan Czenski
Dylan Czenski

Reputation: 1375

In an adjacency matrix, how to find a given vertex's neighbor's neighbors?

Let's say we have an 4x4 adjacency matrix like this:

enter image description here

and a given vertex, let's say int v=1

how do I find vertex 1's neighbors' neighbors, and add them to a list? For example if I want to go from vertex 1 to vertex 4, I have to go to vertex 2 first, and then from vertex 2 to vertex 4, since there's no direct path from 1 to 4. And I want to add vertex 4 and alike to a list.

Right now here is what I got:

int v=1;
for(int i=0;i<adjmat.length;i++){
            if (i==v){
                for(int j=0;j<adjmat[i].length;j++){
                    if (j!=i){ // self loops do not count
                        // if adjmat[i][j] has a neighbor, add the neighbor to a list 
                    }
                }
            }
        }

Upvotes: 2

Views: 3327

Answers (2)

Gene
Gene

Reputation: 47020

If A is the adjacency matrix, consider A^2 constructed by matrix multiplication with AND for the inner product and summing with OR. The value of a member

A^2(i,j) = OR(k){ A(i,k) AND A(k,j) }

This says i is connected to j if there exists a k such that i is connected to k and k is connected to j. So this matrix is the graph formed by connecting every pair of vertices that can are connected by two edges in the original graph.

Upvotes: 1

synchronizer
synchronizer

Reputation: 2075

What you have seems to be correct.

Just a few notes: Your graphic has indices starting with 1 when your loops start at 0. You probably are not worried about this, but in any case, let's assume that the vertices are named starting with 1, and that your arrays start with 0.

Then the only real concern is your outermost loop. If you only need to find the neighbors of neighbors of one vertex v (your example, v = 1)

int v_i = v-1;
for(int j=0;j<adjmat[v_i].length;j++){
    if (v_i!=j){ // self loops do not count
        // if adjmat[i][j] has a neighbor, add the neighbor to a list 
        //*NOTE maybe only if that neighbor is also not a self loop, one of v's first neighbors, or v 
    }
}

Upvotes: 1

Related Questions