Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

определить является ли связанным граф - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Алгоритм (псевдокод) одномерного динамического массива http://www.cyberforum.ru/cpp-beginners/thread152915.html
Суть проблемы такова: Задан массив – А(10). Получить из него массив В, состоящий из элементов массива А, которые меньше 0. Массивы создаются с использованием операций NEW и DELETE. Ввод исходных...
C++ Граф задан мартрицей весов.Нужно определить ребра с максимальным весом и удалить их Нужна помощь в решении следующей задачи :friends: Задача следующая:Граф задан мартрицей весов.Нужно определить ребра с максимальным весом и удалить их..Если я правильно понял,то мне нужно будет... http://www.cyberforum.ru/cpp-beginners/thread152910.html
Удаление положительных элементов очереди C++
Нужно написать программу для удаления положительных элементов очереди :) ВВод очереди осуществляется так: void vvod_ochered(int mas,int *kol,int *end/*,int *start*/) { if((*kol)==N){...
C++ Структура в структуре!!!
Написать cписок кварталов города, с разбитием по районам. Количество районов и кварталов в каждом районе по 3.(Turbo C)
C++ Создать шаблонный класс-контейнер http://www.cyberforum.ru/cpp-beginners/thread152863.html
помогите срочно у меня задание оч нужнно Создать шаблонный класс-контейнер Array, который представляет собой массив, позволяющий хранить объекты заданного типа. Класс должен реализовывать...
C++ Компилятор для примеров из книги по С++ Я начал читать книгу "Джесс Либерти - Освой самостоятельно С++ за 21 день". Выбрал компилятор Borland C++ Builder 6, но сним возникли проблемы :( Подскажите какой нибудь компилятор для примеров из... подробнее

Показать сообщение отдельно
dxdy
97 / 97 / 5
Регистрация: 14.06.2010
Сообщений: 283
10.07.2010, 17:55
Можно двумя способами проверить, что граф связанный.
1 способ Берем любую вершину и с этой вершины пытаемся обойти всех его сыновей. Все вершины, которые мы будем обходить заносим в стек, затем когда обход будет завершен, мы достаем все точки из стека и считаем их количество, если количество будет равно количеству вершин в графе, то граф считается связанным.
2 способ У нас имеется матрица смежности, по которому строится граф. Пусть матрица смежности имеет N вершин. Не будем забывать, что 1 вершина без путей тоже является связанным графом, поэтому по главной диагонали матрицы смежности ставим 1. Затем данную матрицу будем возводим в N степень, хотя результат может быть уже известен и на шаге меньше, чем N. После возведения матрицы в N степень мы должны получить матрицу, состоящая из одних 1. Ели это условие выполняется, то граф связанный.
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru