@Rastr_0

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

Я понимаю, что матрица смежности неориентированного графа будет верной в том случае, если она будет симметрична относительно диагонали идущей из точки (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;
}

Почему такой код неверный?
  • Вопрос задан
  • 44 просмотра
Решения вопроса 1
@Akina
Сетевой и системный админ, SQL-программист.
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;
}
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы