Поиск числа компонент свзности С++
Здравствуйте.
Очень нужна ваша помощь, сама уже устала этим заниматься. Неполучается. Мне нужно найти число компонент связности, т.е. колличество несвязных (под)графов в одном большом графе, который задан матрицей смежности. Делается это, вроде, поиском в глубину, но как это реализовать, я не знаю. Вообще, задание у меня - найти цикломатическое число графа, я кое-чего уже сделала, а именно чтение графа из файла и подсчет всех остальных переменных, необходимых, чтобы найти цикломатическое число, а вот число компонент связности никак, это самое сложное Вот мой код, но он не особо поможет с подсчетом числа компонент связности Код: [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] Если кто поможет, буду очень признательна |
Часовой пояс GMT +4, время: 05:24. |
Powered by vBulletin® Version 4.5.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.