Souvislost grafu – C / C++ – Fórum – Programujte.com

Chtěl jsem se zeptat, zda by mi někdo nepomohl s vyřešením níže uvedeného příkladu zabývající se problematikou kódu pro "souvislost grafu".

Vyskakovala mi tam chyba na řádku: bool navstiven[point];

Když jsem přepsal point na hodnotu třeba 3 (bool navstiven[3];) tak stejně po debugging se tam nějaké chybové hlášky objevily.

Dělám to ve Visual Studio 2013. 

Děkuji za reakce.

Kód:

/******************************************
* Program pro zjisteni, zda je graf souvisly
******************************************/

// potrebne knihovny
#include <iostream>    //vstup, vystup
#include <list>        //seznamy
#include <queue>    //fronta
using namespace std;

/*
* Třída pro vytvoření grafu
*/
class MyGraph
{
    private:
        int point;            // uzel grafu
        list<int> *adj;        // 
    public:
        MyGraph(int point)    // konstruktor - vytvoří nový graf pro zadaný počáteční uzel
        {
            this->point = point;    // počáteční uzel
            adj = new list<int>[point];    // seznam dalších uzlů
        }
        ~MyGraph() { delete [] adj; }    // destruktor
        void addPath(int point1, int point2);    // přidá do grafu cestu mezi dvěma uzly
        void BFS(int s, bool navstiven[]);        // zjistí, zda lze navštívit všechny uzly
        MyGraph getTranspose();
        bool jeSouvisly();                        // pokud je graf souvislý, vrátí True
};
 
/*
 * Přidáme cestu
 */
void MyGraph::addPath(int point1, int point2)
{
    adj[point1].push_back(point2);    // z bodu 1 do bodu 2
    adj[point2].push_back(point1);    // z bodu 2 do bodu 1
}
 
void MyGraph::BFS(int s, bool navstiven[])
{
    list<int> q;
    list<int>::iterator i;
    navstiven[s] = true;
    q.push_back(s);
    while (!q.empty())
    {
        s = q.front();
        q.pop_front();
        for(i = adj[s].begin(); i != adj[s].end(); ++i)
        {
            if(!navstiven[*i])
            {
                navstiven[*i] = true;
                q.push_back(*i);
            }
        }
    }
}

/*
* Funkce pro vytvoření otočeného grafu
*/
MyGraph MyGraph::getTranspose()
{
    MyGraph g(point);
    for (int v = 0; v < point; v++)
    {
        list<int>::iterator i;
        for(i = adj[v].begin(); i != adj[v].end(); ++i)
        {
            g.adj[*i].push_back(v);
        }
    }
    return g;
}

/*
* Pokud je graf souvislý, vrátí True, jinak False
*/
bool MyGraph::jeSouvisly()
{
    // u všech uzlů nastavíme, že nebyl navštíven
    bool navstiven[point];
    for (int i = 0; i < point; i++)
        navstiven[i] = false;
    // provedeme BFS od startovního uzlu
    BFS(0, navstiven);
    // pokud BFS nenavštíví všechny uzly, vrátíme false (graf není souvislý)
    for (int i = 0; i < point; i++)
        if (navstiven[i] == false)
            return false;
    // vytvoříme opačný graf (musíme se dostat k jednotlivým uzlům i z opačné strany)
    MyGraph gr = getTranspose();
    // opět všechny uzly označíme jako nenavštívené
    for(int i = 0; i < point; i++)
        navstiven[i] = false;
    // provedeme BFS od startovního uzlu
    gr.BFS(0, navstiven);
    // pokud BFS nenavštíví všechny uzly, vrátíme false (graf není souvislý)
    for (int i = 0; i < point; i++)
        if (navstiven[i] == false)
            return false;
    // pokud jsme doposud neskončili, tak BFS navštívil všechny uzly a graf je souvislý
    return true;
}

int main()
{
    // otestujeme funkčnost
    MyGraph g(4);        // vytvoříme nový graf
    g.addPath(0, 1);    // přidáme jednotlivé cesty
    g.addPath(0, 3);
    g.addPath(1, 2);
    g.addPath(1, 3);
    g.addPath(3, 3);
    if (g.jeSouvisly())    // a zjistíme, zda je graf souvislý
        cout<<"Graf je souvislý."<<endl;
    else
        cout<<"Graf není souvislý."<<endl;
 
    MyGraph g1(5);    // vytvoříme nový graf
    g1.addPath(0, 1);    // přidáme jednotlivé cesty
    g1.addPath(0, 2);
    g1.addPath(0, 3);
    g1.addPath(3, 1);
    g1.addPath(2, 3);
    g1.addPath(4, 2);
    if (g1.jeSouvisly())    // a zjistíme, zda je graf souvislý
        cout<<"Graf je souvislý."<<endl;
    else
        cout<<"Graf není souvislý."<<endl;
    return 0;
}

První graf má 4 body a druhý 5. Takže 3 samozřejmě stačit nebudou :-)

A při getTranspose pravděpodobně proběhne vytváření a kopírování instance, takže nová bude mít stejnou hodnotu adj a ta stará ho v destruktoru smaže i té nové. Udělej kopírovací konstruktor, nebo pro adj použij něco, co se umí zkopírovat "samo".

vector<list<int>> adj;
public:
    MyGraph(int point)
    {
        this->point = point;
        adj.resize(point);
    }


...

bool MyGraph::jeSouvisly()
{
    unique_ptr<bool[]> navstiven(new bool[point]);

    for (int i = 0; i < point; i++)
        navstiven[i] = false;

    BFS(0, navstiven.get());
...