How to check the adjacency matrix of an undirected graph for correctness?

Question

C++ / C#

I understand that the adjacency matrix of an undirected graph will be correct if it is symmetrical with respect to the diagonal coming from the point (0; 0), but it doesn’t work out.

bool is_adjacency_matrix(const vector<string>& matrix) {
  for (auto i = 0; i < matrix.size(); i++) {
    for (auto j = i; j < matrix[i].size(); j++) {
      if (matrix[i][j] != matrix[j][i])
        return false;
    }
  }
  return true;
}

Why is this code wrong?

Answer 1

raster , how to understand your

write fails

, if you immediately give the code - which, by the way, is able to solve the problem. Well, unless:

1. Iteration goes over a separate column or row - so putting an upper bound for i over the entire matrix is ​​somewhat wrong
   
2. For i, iterate to the penultimate value, and for j - from a value 1 greater than the current i to the last one. For if some pair is checked, then it makes no sense to check it again "from the reverse side", and it makes no sense to check the equality of the element to itself.
   

In general, something like this (without exact syntax)

bool is_adjacency_matrix_correct(const vector<string>& matrix) {
  size=matrix[0].size();
  for (auto i = 0; i < size-1; i++) {
    for (auto j = i+1; j < size; j++) {
      if (matrix[i][j] != matrix[j][i])
        return false;
    }
  }
  return true;
}