Здравствуйте.
Очень нужна ваша помощь, сама уже устала этим заниматься. Неполучается.
Мне нужно найти число компонент связности, т.е. колличество несвязных (под)графов в одном большом графе, который задан матрицей смежности.
Делается это, вроде, поиском в глубину, но как это реализовать, я не знаю.
Вообще, задание у меня - найти цикломатическое число графа, я кое-чего уже сделала, а именно чтение графа из файла и подсчет всех остальных переменных, необходимых, чтобы найти цикломатическое число, а вот число компонент связности никак, это самое сложное
Вот мой код, но он не особо поможет с подсчетом числа компонент связности
Код:
[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]
Если кто поможет, буду очень признательна