Технический форум
Вернуться   Технический форум > Программирование > Форум программистов > Помощь студентам


Ответ
 
Опции темы Опции просмотра
Старый 20.04.2011, 02:30   #1 (permalink)
Li*zA
Новичок
 
Регистрация: 20.04.2011
Сообщений: 1
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
По умолчанию Поиск числа компонент свзности С++

Здравствуйте.
Очень нужна ваша помощь, сама уже устала этим заниматься. Неполучается.

Мне нужно найти число компонент связности, т.е. колличество несвязных (под)графов в одном большом графе, который задан матрицей смежности.
Делается это, вроде, поиском в глубину, но как это реализовать, я не знаю.

Вообще, задание у меня - найти цикломатическое число графа, я кое-чего уже сделала, а именно чтение графа из файла и подсчет всех остальных переменных, необходимых, чтобы найти цикломатическое число, а вот число компонент связности никак, это самое сложное

Вот мой код, но он не особо поможет с подсчетом числа компонент связности

Код:
[code]
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;

int main ()
{
setlocale(LC_ALL,"rus");
int vert; // Колличество вершин
int rib = 0; // Удвоенное колличество ребер + колличество петель (т.е. единиц в матрице)
int loop = 0; // Колличество петель
ifstream fin("1.txt");
fin>>vert;
if (vert < 1)
{
cout << "ERROR(это не граф) ";
return 1;
}
int **graph = new int*[vert];
for(int i=0;i<vert; i++)
{
graph[i] = new int[vert];
}
//Ввод таблицы из файла
for (int i = 0; i < vert; i++ )
{
for (int j = 0; j < vert; j++ )
{
fin >> graph[i][j];
if (graph[i][j] == 1)
{
rib++;
}
else if (graph[i][j] == 0){}
else
{
cout << "ERROR(некорректные входные данные) ";
return 1;
}
}
if (graph[i][i] == 1)
{
loop=loop+1;
}
}
cout << "Матирца смежности заданного графа:\n" ;
//Вывод таблицы
for (int i = 0; i < vert; i++ )
{
for (int j = 0; j < vert; j++ )
{
cout<<setw(5)<< graph[i][j] ;
}
cout<<"\n" ;
}
int result;
result = 1 + (rib+loop)/2 - vert; // вместо еденички надо число компонент связности
cout << "Цикломатическое число заданного графа = " ;
cout << result << "\n";
}
[code]
Если кто поможет, буду очень признательна
Li*zA вне форума   Ответить с цитированием

Старый 20.04.2011, 02:30
Helpmaster
Member
 
Аватар для Helpmaster
 
Регистрация: 08.03.2016
Сообщений: 0

Если проблема еще не решена, можете обратиться к похожим темам

Даны три вещественных числа...
Паскаль. Сумма цифр числа
Паскаль. Обработка натурального числа
Умножение длинного числа на короткое (Турбо Паскаль).
Собственные числа на Delphi
Компонент msxml4 sp2 не установлен

Ads

Яндекс

Member
 
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Выкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.




Часовой пояс GMT +4, время: 05:00.

Powered by vBulletin® Version 6.2.5.
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.