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

Question

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.

Solution 1

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.

Solution 2

The easiest way to do this would be to use a square matrix (2d array), either of booleans to show the presence or absence of a connection or integers to represent the cost of traversal. For a sparse graph, however, you may get better compression by using jagged arrays and then storing which nodes are adjacent to the first one. In Java, I'd probably do this by having a List<List<Integer>> where the outer list corresponds to the node in question and the inner list is all of the nodes adjacent to this one.

Assuming you decide to use a standard (uncompressed) matrix, you could find out whether a node i is adjacent to every node j in a list by iterating through the list, and then looking up A[i][j]. If any of them are false, then it is not adjacent to every item in the list, otherwise it is true. For a clique, you just have to do this for every item in the list (dropping the case where i=j and making some optimizations for an undirected graph).

An example (again in Java)

public boolean isClique(boolean[][] A, List<Integer> nodes){
  for(int i : nodes){
    for(int j : nodes){
      if(i != j){
        if(!A[i][j]) return false;
      }
    }
  }
  return true;
}

Optimizations and a solution to the Max-Clique problem are left as an exercise to the reader.

Solution 3

Hint: So you have your adjacency matrix M which tells you if two nodes are directly connected. Then what does M^2 gives you? It tells you if there is a path of length 2 between two nodes.

I let you imagine what are M^3,... , M^inf (when you reach the fixpoint)

Solution 4

Using your adjacency matrix, applying the Floyd-Warshall algorithm will give you all your paths between nodes. Then you can check for particular sets.

View more solutions