C++ Графы
Добрый вечер!
у меня такая проблема: Поставили задачу:"проверить, является ли заданный граф связанный?" И я не знаю как это сделать. :(
Это мое первое знакомство с графами, и скажем прямо оно не завязалось успешно(с деревьями было куда лучше и намного интереснее)
Поэтому я хотел бы попросить обьяснить как с ними работать?
Как я понял графы можно представить несколькими способами(один из них - матрица смежности) я так и сделал- представил его как матрицу(смежные вершины -1, а не смежные-0)
И Вот теперь не знаю как делать дальше?Если кто-то работал с графами, подкиньте плиз идейку.
у меня такая проблема: Поставили задачу:"проверить, является ли заданный граф связанный?" И я не знаю как это сделать. :(
Это мое первое знакомство с графами, и скажем прямо оно не завязалось успешно(с деревьями было куда лучше и намного интереснее)
Поэтому я хотел бы попросить обьяснить как с ними работать?
Как я понял графы можно представить несколькими способами(один из них - матрица смежности) я так и сделал- представил его как матрицу(смежные вершины -1, а не смежные-0)
И Вот теперь не знаю как делать дальше?Если кто-то работал с графами, подкиньте плиз идейку.
Первое что приходит в голову - простой перебор.
Связный граф - граф у которого существует путь из любой вершины - в любую другую.
Берешь каждую вершину - и проверяешь существует-ли у неё связь со всеми остальными (есть путь в любую из оставшихся вершин).
Правда тут нужно применить алгоритм обхода графа. На тему обхода графов есть множество примеров и теории.
Связный граф - граф у которого существует путь из любой вершины - в любую другую.
Берешь каждую вершину - и проверяешь существует-ли у неё связь со всеми остальными (есть путь в любую из оставшихся вершин).
Правда тут нужно применить алгоритм обхода графа. На тему обхода графов есть множество примеров и теории.
Алгоритмы обхода графа? это такие как обход графа в глубину или в ширину? Вы о них говорили?
А как насчет составления матрицы достижимости?
можно же наверно и с ее помощью тоже проверить, является ли граф связанным?
можно же наверно и с ее помощью тоже проверить, является ли граф связанным?