Чтобы проверить, связан ли граф, используя BFS, и выведите MST
Я сохранил граф с узлами 1, 2, 3, 4, … в списке смежности.
Я написал этот код для поиска в ширину (BFS). BFS работает отлично, но я не знаю, какова процедура, чтобы выяснить, подключен или отключен граф, а затем распечатать минимальное остовное дерево графа, если он подключен?
Пример графа, который я сохранил в списке смежности:
1 3 4
2 4
3 1 4
4 2 1 3
И код для BFS:
int visit[999] = { 0 };
Q.enqueue(0);
while (!Q.isEmpty())
{
y = Q.dequeue();
traverse = g[y];
while (traverse->link != 0)
{
if (visit[traverse->data-1] == 0)
{
visit[traverse->data-1] = 1;
parent = traverse->data;
Q.enqueue(traverse->data-1);
}
traverse = traverse->link;}
if (visit[traverse->data - 1] == 0)
{
visit[traverse->data - 1] = 1;
parent = traverse->data;
Q.enqueue(traverse->data - 1);
}
}
Решение
Так что я понял это и поставил его как справку для других 🙂
int parent = 1;
gcounter++;
p = 0;
int visit[999] = { 0 };
int c[999] = { 0 };
int k = 0;
int z = 0;
Queue Q;
Q.enqueue(0);
while (!Q.isEmpty())
{
y = Q.dequeue();
traverse = g[y];
while (traverse->link != 0)
{
if (visit[traverse->data-1] == 0)
{
if (y + 1 != traverse->data)
{
c[z] = y + 1;z++;
c[z] = traverse->data; z++;
}
p++;
visit[traverse->data-1] = 1;
parent = traverse->data;
Q.enqueue(traverse->data-1);
}
traverse = traverse->link;}
if (visit[traverse->data - 1] == 0)
{
if (y + 1 != traverse->data)
{
c[z] = y + 1; z++;
c[z] = traverse->data; z++;
}
p++;
visit[traverse->data - 1] = 1;
parent = traverse->data;
Q.enqueue(traverse->data - 1);
}
}if (p < lcounter) //lcounter-> the lines -> total number of nodes
{
writeFile << "The Graph is disconnected" << endl;}
else
{
writeFile << "The Graph is connected and it's MST is: ";
for (z = 0; c[z+1] != 0; z++)
{
writeFile << "(" << c[z] << "," << c[z + 1] << ") ";
z++;
}
writeFile << endl;
}
Другие решения
Других решений пока нет …