Как проверить матрицу смежности неориентированного графа на верность?

Question

[rastr]

Я понимаю, что матрица смежности неориентированного графа будет верной в том случае, если она будет симметрична относительно диагонали идущей из точки (0; 0), но написать не выходит.

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;
}

Почему такой код неверный?

Comments

[Lynn «Кофеман»]

А кто-то гарантирует что матрица на входе квадратная? А так с ходу других проблем не вижу. Почему вы считаете что код неверный?

[Akina]

Lynn «Кофеман», матрица смежности квадратна по определению.

[Lynn «Кофеман»]

Akina, но автор нигде не проверяет что ему передали квадратную матрицу, а не какую-нибудь другую. Это может быть ок, а может быть нет, в зависимости от изначальных условий

[Wataru]

rastr, помимо проверки на квадратность, возможно в графе запрещены петли. Тогда надо проверить, что по диагонали стоят 0. А так, ваш код выглядит правильным.

[Akina]

Lynn «Кофеман», Вы забыли добавить про проверку на то, что в матрице только нули и единицы, и что там вообще числа, а не буквы "х" и "о"...

Answer 1

[Akina]

rastr, как понимать Ваше

написать не выходит

, если Вы тут же приводите код - который, кстати, способен решить задачу. Ну разве что:

1. Итерация идёт по отдельному столбцу либо строке - так что ставить верхнюю границу для i по всей матрице несколько неправильно
   
2. По i надо итерировать до предпоследнего значения, а по j - от значения на 1 больше текущего i до последнего. Ибо если проверена какая-то пара, то нет смысла проверять её ещё раз "с обратной стороны", а уж равенство элемента самому себе так и вовсе проверять бессмысленно.
   

В общем, приблизительно так (без точного соблюдения синтаксиса)

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;
}