Algoritmusok 5


  1. Algoritmus: a Warshall-algoritmus. Az M darab pontot tartalmazó G irányított gráfot az A szomszédsági mátrixa valósítja meg a memóriában. Az algoritmus megkeresi a G gráf P útmátrixát (Bool-mátrix).
    1. Repeat for I, J=1, 2, ..., M: [A P inicializálása.]
      If A[I, J]=0, then: P[I, J]:=0;
      Else: P[I, J]:=1
      [A ciklus vége.]
    2. Repeat 3. and 4. lépés for K=1, 2 ..., M: [A P aktualizálása.]
    3. repeat 4. lépés for I=1, 2, ..., M:
    4. repeat for J=1, 2, ..., M:
      P[I, J]:=P[I, J] . (P[I, K] . P[K, J]).
      [A ciklus vége.]
      [A 3. lépésben elkezdődött ciklus vége.]
      [A 2. lépésben elkezdődött ciklus vége.]
    5. Exit.


  2. Algoritmus: a legrövidebb út algoritmus. Az M darab pontot tartalmazó G súlyozott gráfot a W súlymátrixa valósítja meg a memóriában. Az algoritmus azt a Q mátrixot állítja elő, amelyben a Q[I, J] elem a VI pontból a VJ pontba vezető legrövidebb út hosszúságát tartalmazza. Az algoritmusban a VÉGTELEN szóval egy igen nagy számot, a MIN rövidítéssel pedig a minimumérték-függvényt jelöltük.
    1. Repeat for I, J=1, 2 ..., M: [A Q inicializálása.]
      If W[I, J]=0, then: Q[I, J]:=VÉGTELEN;
      Else: Q[I, J]:= W[I, J].
      [A ciklus vége.]
    2. Repeat 3. and 4. lépés for K=1, 2 ..., M: [A Q aktualizálása.]
    3. Repeat 4. lépés for I=1, 2 ..., M:
    4. Repeat for J=1, 2 ..., M:
      Q[I, J]:= MIN(Q[I, J], Q[I, K]+Q[K, J]).
      [A ciklus vége.]
      [A 3. lépésben elkezdődött ciklus vége.]
      [A 2. lépésben elkezdődött ciklus vége.]
    5. Exit.


  3. Eljárás: FIND(INFO, LINK, START, ITEM, LOC). Az algoritmus megkeresi annak a pontnak a helyét (LOC), amelyben az ITEM információ először előfordul, vagy NULL-ra állítja be a LOC értéket.
    1. PTR:=START.
    2. Repeat while PTR.NULL:
      If ITEM=INFO[PTR], then: LOC:=PTR, Return.
      Else: PTR:=LINK[PTR].
      [Az If szerkezet vége.]
      [A 2. lépésben elkezdődött ciklus vége.]
    3. LOC:=NULL, Return.


  4. Eljárás: DELETE(INFO, LINK, START, AVAIL, ITEM, FLAG). Az algoritmus törli a kapcsolt listából az adott ITEM információt tartalmazó legelső pontot (N), vagy FALSE-ra állítja be a FLAG logikai változót, ha az ITEM nem szerepel a listában.
    1. [Üres a lista?] If START=NULL, then: FLAG:=FALSE, Return.
    2. [Az ITEM az első pontban van?] If INFO[START]=ITEM, then:
      PTR:=START, START:=LINK[START],
      LINK[PTR]:=AVAIL, AVAIL:=PTR,
      FLAG:=TRUE, Return.
      [Az If szerkezet vége.]
    3. PTR:=LINK[START], SAVE:=START. [A mutatók inicializálása.]
    4. repeat 5. and 6. lépés while PTR.NULL:
    5. If INFO[PTR]=ITEM, then:
      LINK[SAVE]:=LINK[PTR], LINK[PTR]:=AVAIL,
      AVAIL:=PTR, FLAG:=TRUE, Return.
      [Az If szerkezet vége.]
    6. SAVE:=PTR, PTR:=LINK[PTR]. [A mutatók aktualizálása.]
      [A 4. lépésben elkezdődött ciklus vége.]
    7. FLAG:=FALSE, Return.


  5. Eljárás: FINDEDGE(NODE, NEXT, ADJ, START, DEST, LINK, A, B, LOC). Az eljárás megkeresi az (A, B) él helyét (LOC) a G gráfban, vagy NULL-ra állítja be a LOC értékét.
    1. Call FIND(NODE, NEXT, START, A, LOCA).
    2. Call FIND(NODE, NEXT, START, B, LOCB).
    3. If LOCA=NULL or LOCB=NULL, then: LOC:=NULL.
      Else: Call FIND(DEST, LINK, ADJ[LOCA], LOCB, LOC).
    4. Return.


  6. Eljárás: INSNODE(NODE, NEXT, ADJ, START, AVAILN, N, FLAG). Az eljárás beszúrja a pontot (N) a G gráfba.
    1. [Túlcsordulás?] If AVAILN=NULL, then: FLAG:=FALSE, Return.
    2. ADJ[AVAILN]:=NULL.
    3. [A pont eltávolítása az AVAILN listából.]
      [NEW:=AVAILN, AVAILN:=NEXT[AVAILN].
    4. [Az N pont beszúrása a NODE listába.]
      NODE[NEW]:=N, NEXT[NEW]:=START, START:=NEW.
    5. FLAG:=TRUE, Return.


  7. Eljárás: INSEDGE(NODE, NEXT, ADJ, START, DEST, LINK, AVAILE, A, B, FLAG). Az eljárás beszúrja az (A, B) élt a G gráfba.
    1. Call FIND(NODE, NEXT, START, A, LOCA).
    2. Call FIND(NODE, NEXT, START, B, LOCB).
    3. [Túlcsordulás?] If AVAILE=NULL, then: FLAG:=FALSE, Return.
    4. [A pont eltávolítása az AVAILE listából.] NEW:=AVAILE,
      AVAILE:=LINK[AVAILE].
    5. [A LOCB beszúrása az A szukcesszorainak listájába.]
      DEST[NEW]:=LOCB, LINK[NEW]:=ADJ[LOCA], ADJ[LOCA]:=NEW.
    6. FLAG:=TRUE, Return.


  8. Eljárás: DELEDGE(NODE, NEXT, ADJ, START, DEST, LINK, AVAILE, A, B, FLAG). Az eljárás törli a G gráfból az (A, B) élt.
    1. Call FIND(NODE, NEXT, START, A, LOCA). [Az A helyének megkeresése.]
    2. Call FIND(NODE, NEXT, START, B, LOCB). [Az B helyének megkeresése.]
    3. Call DELETE(DEST, LINK, ADJ[LOCA], AVAILE, LOCB, FLAG).
      [A IV. eljárás használata.]
    4. Return.


  9. Eljárás: DELNODE(NODE, NEXT, ADJ, START, AVAILN, DEST, LINK, AVAILE, N, FLAG). Az eljárás törli az N pontot a G gráfból.
    1. Call FIND(NODE, NEXT, START, N, LOC). [Az N pont megkeresése.]
    2. If LOC=NULL, then: FLAG:=FALSE, Return.
    3. [Az N-ben végződő élek törlése.]
      1. PTR:=START.
      2. Repeat while PTR.NULL:
        1. Call DELETE(DEST, LINK, ADJ[PTR], AVAILE, LOC, FLAG).
        2. PTR:=NEXT[PTR].
          [A ciklus vége.]
    4. [A szukcesszorok listája üres?] If ADJ[LOC]=NULL, then:
      Go to 7. lépés.
    5. [Az N első és utolsó szukcesszorának megkeresése.]
      1. BEG:=ADJ[LOC], END:=ADJ[LOC], PTR:=LINK[END].
      2. Repeat while PTR.NULL:
        END:=PTR,PTR:=LINK[PTR].
        [A ciklus vége.]
    6. [Az N szukcesszorlistájának hozzákapcsolása az AVAILE listához.]
      LINK[END]:=AVAILE, AVAILE:=BEG.
    7. [Az N törlése a IV. Eljárás felhasználásával.]
      Call DELETE(NODE, NEXT, START, AVAILN, N, FLAG).
    8. Return.


    Egy szintet vissza, vagy vissza a főmenübe.