Привет, ребята, поэтому я делаю функцию для своих графиков (матриц смежности), чтобы возвращать количество связанных компонентов, используя алгоритм поиска в ширину.
Почти нормально работает. Он возвращает правильное значение, если количество компонентов равно количеству вершин, но если количество компонентов меньше, чем количество вершин, он возвращает (правильное значение +1). Я понятия не имею, как это исправить, поэтому, если бы вы могли взглянуть и сказать мне, я был бы рад. Вот ссылка на код, он выглядит более прилично, чем приведенный ниже http://wklej.org/id/861341/
int Graph::getNumberOfConnectedComponents()
{
int components=0;
queue<int> S;
int n = getVerticesCount();//as name indicates it returns number of vertices in graph
bool* visited = new bool[n];
for(int i=1;i<n;i++)
visited[i]=false;
visited[0]=true;
S.push(0);
while(!S.empty())
{
int v = S.front();
S.pop();
list<int> x = getNeighbors(v);//as name indicates this function returns list of neighbours of given vertice
if(!x.empty())
{
list<int>::iterator it;
for (it=x.begin(); it!=x.end(); it++)
{
if(visited[*it]==false)
{
S.push(*it);
visited[*it]=true;
}
}
}
if(S.empty())
{
components++;
for(int i=1;i<n;i++)
{
if(visited[i]==false)
{
S.push(i);
visited[i]=true;
break;
}
}
}
}
return components;
}
Я объяснил, что делают эти функции в комментариях, надеюсь, вы сможете мне помочь :/ . Кстати, если вы измените место компонентов++; и поместите его в if(visited[i]==false) он дает правильное значение для всех графов, кроме тех, у которых количество компонентов = количеству вершин (для тех это значение "правильное значение-1").
@Изменить 1, вот эта функция, Джон
list<int> AdjacencyMatrixGraph::getNeighbors(int v)
{
list<int> x;
if(v==0||v>=n)
return x;
for(int j=0;j<n;j++)
{
if(matrix[v][j]!=0)
x.push_front(j);
}
return x;
}
getNeighbors
по какой-то причине прослушивается. Таким образом, каждая вершина действует как собственный компонент. - person john   schedule 04.11.2012