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

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

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

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