20.04.2011, 02:30 | #1 (permalink) |
Новичок
Регистрация: 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] Если кто поможет, буду очень признательна |
20.04.2011, 02:30 | |
Helpmaster
Member
Регистрация: 08.03.2016
Сообщений: 0
|
Если проблема еще не решена, можете обратиться к похожим темам Даны три вещественных числа... Паскаль. Сумма цифр числа Паскаль. Обработка натурального числа Умножение длинного числа на короткое (Турбо Паскаль). Собственные числа на Delphi Компонент msxml4 sp2 не установлен |
Ads | |
Member
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
|
|
|