Datenstruktur Netz

ffprogramming · Beiträge: 44 Win XP C# Java C PHP

Ich programmiere schon seit einiger Zeit und stehe gerade total auf dem Schlauch.
Ich brauche eine flexible Datenstruktur, die ein Netz abbildet. Ich habe mich hiermit noch nie befasst.
Wichtig ist, dass das Netz Flexibel ist: Man sollte ohne große Probleme neue Verknüpfungen herstellen können oder auch bei bedarf welche löschen.

Beispielsweise soll man einfach Verbindungen ändern/erstellen können.
Das Einzige, was in jedem Knoten (?) gespeichert sein muss, ist ein Wert vom Type Integer.
Die Verbindungen dienen dazu "Reize", dass heißt im Prinzip Zahlenwerte weiter zu leiten.

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

        Wurzel
          /\
         /  \
        l    r
              \
               r2
                \
                 r3       
        Wurzel           Änderung von Verknüpfungen
          /\             
         /  \
        l----r
              \
               r2
                \
                 r3

Mein Problem ist es, dass ich beim Programmieren, noch nicht weiß, wie sich das Netz mal verändern wird. Das soll heißen
ich kann nicht einfach das Netz als starre Struktur wie bei einem einfachen Baum implementieren.

Ich hatte schon daran gedacht ein STRUCT zu nutzen und jedem Knoten eine Liste, die die mit dem Knoten verbundenen Knoten beinhaltet, zu "geben". Praktisch ein Struct im Struct im Struct,...

markieren

C#-Quelltext

1:
2:
3:
4:
5:

public unsafe struct knoten
        {
            public int wert;
            public List<knoten> list;
        }

Aber ich glaube nicht, dass das so gut ist.
Ich erwarte nicht, dass ihr mir eine vollständige Datenstruktur implementiert sondern Denkanstöße liefert oder ggf. geeignetes Material (Links,...) postet.
Danke schon im vorraus.
Filip

Kha · Verfasst: Mo 18.10.10 21:28

unsafe

?

Ein Struct ist hier Unsinn, aber wenn du ihn durch eine Klasse ersetzt, ist das die normale Implementation als Adjazenzliste.

_________________
>λ=

ffprogramming · Beiträge: 44 Win XP C# Java C PHP

Kha hat folgendes geschrieben :

unsafe

?

Ein Struct ist hier Unsinn, aber wenn du ihn durch eine Klasse ersetzt, ist das die normale Implementation als [url=de.wikipedia.org/wik...Adjazenzliste[/url].

Danke. Das unsafe ist von einem Versuch mit Zeigern übrig geblieben.

Trashkid2000 · Beiträge: 561 Erhaltene Danke: 137

Hi,

wie wäre es denn, wenn man sich zu jedem Knoten nur den Rootknoten merkt?

Also so:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

public class Node
{
  public Nullable<Guid> RootNode { get; private set; }
  public Guid Id {get; private set;}
  public int Value { get; private set; }

  public Node(Nullable<Guid> rootNode, Guid id, int nodeValue)
  {
    RootNode = rootNode;
    Id= id;
    Value = nodeValue;
  }
}

Wenn man nun eine List<Node> hätte, wo also alle Knoten mit ihren Rootknoten drin sind, so könnte man einfach die Struktur ändern, und sie auch durch eine Logik abbilden.

Das setzt allerdings vorraus, dass jeder Knoten eine eindeutige Kennung hat. Wie hier z.B. eine Guid.

Wieleicht brint es Dir ja was,

LG, Marko

Kha · Verfasst: Sa 23.10.10 15:25

Es geht nicht um Bäume, sondern beliebige Graphen. Und warum bitte RootNode nicht vom Typ Node machen :gruebel:

?

_________________
>λ=

Trashkid2000 · Beiträge: 561 Erhaltene Danke: 137

Kha hat folgendes geschrieben :

Und warum bitte RootNode nicht vom Typ Node machen :gruebel:

?

Ja, da hast Du natürlich recht. Aber anders gesehen, wenn die Struktur aus z.B. einer Datenbank gelesen wird (weil sie sich ja immer ändern kann), dann müssten die Knoten ja auch in der richtigen Reihenfolge erstellt werden. So ist es vieleicht flexibler!?

Kha hat folgendes geschrieben :

Es geht nicht um Bäume, sondern beliebige Graphen.

Ok, aber bei der 2.Variante von oben wäre doch Knoten l der RootNode von r, und r der RootNode von l, oder?
Und beide haben auch als RootNode noch die Wurzel. Kann doch alles abgebildet werden.

Oder verstehe ich was falsch?
Marko

Kha · Verfasst: Sa 23.10.10 16:27

Trashkid2000 hat folgendes geschrieben :

Aber anders gesehen, wenn die Struktur aus z.B. einer Datenbank gelesen wird (weil sie sich ja immer ändern kann), dann müssten die Knoten ja auch in der richtigen Reihenfolge erstellt werden.

Selbst wenn es in einem beliebigen Graphen so etwas wie eine "richtige Reihenfolge" gäbe (du denkst hier wohl an einen DAG): Nein, das ist nicht nötig; die Adjazenzliste lässt sich ja auch noch später während des Einlesens verändern. Man braucht nur ein Dictionary<Guid, Node> dazu.

Trashkid2000 hat folgendes geschrieben :

Und beide haben auch als RootNode noch die Wurzel.

Also hat ein Knoten beliebig viele Eltern (nicht Wurzeln!)? Glückwunsch, du hast gerade eine Adjazenzliste (wie auch immer gerichtet) beschrieben

.

_________________
>λ=

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme