Java – adjacency matrix in java or c++ to find connected nodes

c++graph-theoryjava

I am given a problem where I have been given N nodes in a graph that are interconnected to each other then given a matrix which lists down a node being connected to another (1 if it is, 0 if not). I am wondering how to best approach this problem. I think these are adjacency matrix? But how would I implement that …

Basically what I am trying to get out of these is find whether a particular node is connected to all other nodes in a given set 'S'. And whether selected items are clique or not…

I'd appreciate any hints.

Best Solution

You can implement this using a 2-dimensional array of booleans. So, if node i is connected to node j, then myarray[i][j] would be true. If your edges are not directional, then myarray[j][i] would be true whenever myarray[i][j] is.

This can also be extended to weighted edges by using integers (or another numeric type) instead of booleans as the elements of the array.