Adjazenzlisten als Hash oder als Array? - #120782 (Allgemeines zu Perl)

Crian

2009-04-21 08:44

User since
2003-08-04
5873 Artikel
ModeratorIn

Nein. Hier sollte man die Ebenen nicht durcheinander bringen:

Adjazenzlisten - Matrix

Hash - Array

Es ging darum, Adjazenzlisten zu speichern, diese beinhalten zu jedem Knoten seine Nachbarn.

Die Frage war wohl, ob man es als HoA oder als AoA löst. Dass eine komplette Matrix, die in der Regel zu 90% Nullen enthält, speicherfressender und langsamer ist, sollte klar sein.

Beispiel:

Wir betrachten den Gerichteten Graphen G = (E, K) mit
E = (V1, V2, V3, V4)
und
K = ((V1, V2), (V2,V3), (V2,V4))

Code: (dl )

                 V2
V1  *------------>*----------->* V3
                  |
                  |
                  |
                  v
                  *
                 V4

Matrix:

Code: (dl )

  | V1| V2| V3| V4
--+---+---+---+---
V1| 0 | 1 | 0 | 0 
--+---+---+---+---
V2| 0 | 0 | 1 | 1 
--+---+---+---+---
V3| 0 | 0 | 0 | 0 
--+---+---+---+---
V4| 0 | 0 | 0 | 0

Adjazenzlisten:

Code: (dl )

a(v1) = (V2)
a(v2) = (V3, V4)
a(v3) = ()
a(v4) = ()

mögliche Darstellung als AoA:

Code: (dl )

my @adjazenz = (
    [2],
    [3, 4],
    [],
    [],
);

mögliche Darstellung als HoA:

Code: (dl )

my %adjazenz = (
    V1 => ['V2'],
    V2 => ['V3', 'V4'],
    V3 => [],
    V4 => [],
);

Last edited: 2009-04-21 08:46:08 +0200 (CEST)

s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite