Implementace grafu (nejvhodnejsi struktura) – C / C++ – Fórum – Programujte.com

Ahoj 

Jakou nejvhodnejsi strukturu byste pouzili pro implementaci grafu a naslednych operaci (cyklus, prosty graf, minimalni kostra, dijsktr, bipartitni graf, klika grafu)?

Ja pouzila nasledujici strukturu: (hash -> pole sousedu)

Uzel -> [seznam sousedu] 

Uzel -> [seznam sousedu]

Na tvorbu operaci se to ukazalo jako hodne nevhodne. Mohli byste mi poradit neco lepsiho? 

Proč se to ukázalo jako nevhodný? Mě přijde v pohodě tohle řešení. 

struct Vrchol
{
    int vid;
    vector<Vrchol *> sousedi;

    Vrchol(int vid) : vid(vid) {}
};

static vector<Vrchol *> g_vrcholy;

Vrchol* ziskejVrchol(int vid)
{
    vector<Vrchol *>::iterator it = g_vrcholy.begin();
    for (; it != g_vrcholy.end(); it++) {
        if ((*it)->vid == vid) {
            return *it;
        }
    }
    return NULL;
}

void spoj(int vid1, int vid2)
{
    if (vid1 == vid2) return;

    Vrchol* v1 = ziskejVrchol(vid1);
    Vrchol* v2 = ziskejVrchol(vid2);

    if (v1 != NULL && v2 != NULL) {
        v1->sousedi.push_back(v2);
        v2->sousedi.push_back(v1);
    }
}

int main()
{
    g_vrcholy.push_back(new Vrchol(1));
    g_vrcholy.push_back(new Vrchol(2));
    g_vrcholy.push_back(new Vrchol(3));

    spoj(1, 2);
    spoj(1, 3);
    spoj(2, 3);

    return EXIT_SUCCESS;
}

PS: místo vektoru by byl lepší set + přidat další ošetření

#2 ingiraxo
Bipartitni graf, Cyklus, Klika, Artikulace se v tom strasne blbe hleda

To že se to špatně hledá je věc jiná. Přijde mi, že hledáš nějaký univerzální řešení, na kterým půjde všechno snadno, ale obávám se, že nic takovýho neexistuje.

Můžeš udělat částečně univerzální řešení, který půjde použít na všechny zmíněné grafy, kde tomu předhodíš třeba jinou strategii, ale opět je potřeba to naimplementovat a samotná implementace bude pravděpodobně postavená na nějakým setu, stromu, mapě apod. případně jejich kombinací.

Nemusí to být úplně snadný, ale takový jsou hold algoritmy.

#4 ingiraxo
A ty bys volil jakou implemtaci pro orientovany a neorientovany graf ? 

Já bych zkusil matici sousednosti. Takže pole.

#5 Jaroslava
Tu kterou jen napsal v ukázce. Takže set vrcholů, kde každej vrchol bude mít vlastní set s ukazateli na vrcholy na který ukazuje.

V té ukázce mám ve funkci spoj zrovna případ neorientovanýho grafu, kde oba vrholy ukazují jeden na druhého.