Adjazenzliste nur "key" prüfen



  • Hallo,

    ich habe eine Adjazenzliste als map vorgegeben z.B:

    map<int, vector<int>> adj = {
            {1,{2,3}},
            {2,{}},
            {3,{1,4,6}},
            {4,{1}},
            {5,{3,5}},
            {6,{2,4,5}}
        };
    

    Wie kann ich ueberpruefen, ob ein Key in der Liste enthalten ist?
    Ich kann nur anhand des Keys auf den vector zugreifen. Also:
    adj[3][1] wuerde mir den Wert 4 zurueckgeben.
    Ich moechte aber zunaechst schauen, ob die 3 ueberhaupt ein Key in der Liste ist.

    Lieben Gruss

    Kleo



  • Siehe map::find (und vergleiche das Ergebnis mit adj.end()) oder map::count

    Wenn du nur wissen willst, ob der Key vorhanden ist, nimm count. Wenn du nach dem (erfolgreichen) Test auch auf den Wert zugreifen willst, dann nimm find, damit du den Map-Lookup nicht doppelt machen musst.



  • Als allgemeiner Hinweis: das was du da machst ist relativ aufwendig! Gerade wenn die Listen länger sind, muss man mehrfach quer durch den Speicher lesen, um an die Daten zu kommen. Effektiver ist bei n Knoten einfach nxn Bits reservieren und darin dann abspeichern: adj[a+b*n] = 0|1. std::vector<bool> sollte so spezialisiert sein, das es recht einfach umsetzbar ist.


Log in to reply