Implementace grafu (nejvhodnejsi struktura) – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Jaroslava
~ Anonymní uživatel
3 příspěvky
24. 3. 2015   #1
-
0
-

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? 

Nahlásit jako SPAM
IP: 195.178.73.–
Reklama
Reklama
ingiraxo+15
Grafoman
24. 3. 2015   #2
-
0
-

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í

Nahlásit jako SPAM
IP: 213.168.183.–
Moje aplikace: http://ophite.cz
Tutoriály na: C#
Jaroslava
~ Anonymní uživatel
3 příspěvky
24. 3. 2015   #3
-
0
-

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

Nahlásit jako SPAM
IP: 195.178.73.–
ingiraxo+15
Grafoman
24. 3. 2015   #4
-
0
-

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.

Nahlásit jako SPAM
IP: 213.168.183.–
Moje aplikace: http://ophite.cz
Tutoriály na: C#
Jaroslava
~ Anonymní uživatel
3 příspěvky
24. 3. 2015   #5
-
0
-

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

Nahlásit jako SPAM
IP: 195.178.73.–
Judegarek0
Newbie
24. 3. 2015   #6
-
0
-

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

Nahlásit jako SPAM
IP: 109.73.212.–
Ježíš zaplatil za naše hříchy a tím nás zachránil od věčné smrti a zatracení. Čtěte bibli, napravte se. Zde zdarma v češtině: http://bible21.cz/wp-content/uploads/2010/12/BIBLE21.pdf
ingiraxo+15
Grafoman
24. 3. 2015   #7
-
0
-

#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.

Nahlásit jako SPAM
IP: 213.168.183.–
Moje aplikace: http://ophite.cz
Tutoriály na: C#
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 188 hostů

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý