Kapitel 5

• Informatik ist die Wissenschaft, die sich mit der Struktur, der Wirkungsweise, den Konstruktorenprinzipien und den Einsatzmöglichkeiten informationsverarbeitender Systeme sowie ihren Anwendungen beschäftigt

• Ein Graph ist ein Gebilde aus Knoten (engl. vertex), welche durch Kanten (engl. Edge) miteinander verbunden sind

• Ein Graph G ist ein geordnetes Paar (V, E) aus einer Menge V von Knoten und einer Menge E von Kanten. Jedes Element E ist ein geordnetes oder ungeordnetes Paar, das aus zwei Knoten von V gebildet wird

• Seien G=(V,E) und G’=(V’,E’) Graphen. G’ ist ein Untergraph (Subgraph) von G genau dann, wenn E’ teilmenge von E und V’ teilmenge von V ist

• 
  

• Ein Pfad pi in G ist eine Folge

• der Pfad pi in G ist ein Kreis genau dann,w enn Start(pi) = End(pi)

• Ein Pfad pi ist ein kanteneinfacher Kreis, wenn jede Kante auf dem Pfad pi nur einmal in pi enthalten ist

• Der Verzweigungsgrad d für einen Graphen G und einen Knoten V gibt die Anzahl der mit dem Knoten v verbundenen (ausgehenden!) Kanten an

• Der Verzweigungsgrad d für einen Graphen G gibt den maximalen verzweibungsgrad über alle Knoten an

  
  

• Ein gerichteter Graph G sit ein geordnetes Parr (V,R) aus einer Menge V von Knoten und einer Menge R von Bögen oder gerichteten Kanten

• Jedes Element von R besteht aus einem geordnetem Paar aus Elementen von V. Die Reihenfolge der Knoten im Paar gibt die Richtung der Kante an.

Ein Graph G lässt sich neben der bisheringen Beschreibung durch Mengen E und V auch durch die Angabe einer Gewichtsfunktion g beschreiben

• der Graph G=(V,E) ist ein Baum genau dann, wenn:

  • 1. G ist schleifenfrei

  • 2. G enthält keinen (kanteneinfachen) Kreis

  • 3. G ist zusammenhängend

Abstand von der Wurzel

• Ordnung = Verzweigungsgrad

• Interfaces bzw. Schnittstellendefinitonen sind etwas, das Klassen “implementieren” können

• Wenn eine Klasse ein interface implementiert, “verspricht” sie, dass sie alle Methoden aus dem Interface besitzt

• Hauptreihenfolge (preorder)

  • “WLR”

• Nebenreihenfolge (postorder)

  • “LRW”

• Symmetrische Reihenfolge (inorder)

  • “LWR”

Liste mit Array:

Einfach verkettete Liste:

Doppelt verkettete Liste:

• FIFO - First in, First out

• Die Elemente werden in der Reihenfolge entnommen, wie sie der Speicherstruktur hinzugefügt wurden

• meist mit doppelt verkettete Listen

• Anwendung: Verwaltung von Druckaufträgen, Prozessen oder Webserveranfragen

• LIFO - Last in, First out

• Die Elemente werden in umgekehrter Reihenfolge entnommen, wie sie der Speicherstruktur hinzugefügt wurden

• meist mit einfach verketteten Listen