Aus ProgrammingWiki

Inhaltsverzeichnis

1 Datenstrukturen für Graphen
- 1.1 Aufgabe
- 1.2 Hilfestellung
2 Grundbegriffe

Datenstrukturen für Graphen

Gegeben ist folgendes IGraph Interface mit einer Hilfsklasse Edge zur einfacheren Behandlung von Kanten

interface IGraph{ // provides vertices as numbers (ascending, 0-based) // and edges between them (edges can be null if there is none) void setGraph(int[] vertices, Edge[] edges); // checks if IGraph returns correct vertices and edges int[] getVertices(); // returns vertices ascending Edge[] getEdges(); // returns edges boolean isAdjacent(int v1, int v2); // returns whether v1 is connected to v2 int getDegree(int vertex); // returns the degree of a certain vertex int getSize(); // returns the size of the class properties } class Edge{ public int v1; public int v2; public Edge(int v1, int v2){ // from smaller to greater for improved comparison this.v1 = v1 < v2 ? v1 : v2; this.v2 = v1 < v2 ? v2 : v1; } @Override public int hashCode() { return v1*31+v2; } @Override public boolean equals(Object o){ if(o instanceof Edge) { Edge e = (Edge) o; return (this.v1 == e.v1 && this.v2 == e.v2); } return false; } }

Aufgabe

Erstelle 2 Klassen die das IGraph Interface implementieren
1. als Adjazenzmatrix
2. als Adjazenzliste
Analysiere empirisch die Effizienz dieser beiden Datenstrukturen hinsichtlich
1. Speicherbedarf
2. Ermittlung des Knotengrades
3. Prüfung auf Adjazenz zweier Knoten

Hilfestellung

Es wird ein Graph-Generator bereitgestellt, der das IGraph Interface benutzt um zufällige Graphen zu erzeugen
Mit generate werden dem Graph g eine entsprechende Menge von Knoten (cntVertex) und Kanten (cntEdges) zur Initialisierung übergeben
Die richtige Umsetzung der Speicherung wird mit den Funktionen getVertices und getEdges automatisch geprüft

import java.util.Random; import java.util.HashSet; class GraphGenerator{ private GraphGenerator() { } private static Random r = new Random(); // isolated vertices possible // no loops possible // only one edge between a certain vertex pair public static boolean generate(IGraph g, int cntVertex, int cntEdges){ if (g == null || cntEdges > (long) cntVertex*(cntVertex-1)/2) return false; // no graph instance passed or invalid vertex/edge count int[] v = new int[cntVertex]; // the new list of vertices for(int i = 0; i < cntVertex; i++) v[i] = i; // enumerated 0-based HashSet<Edge> edges = new HashSet<Edge>(); // result set of edges while (edges.size() < cntEdges){ // edge count not reached int i1 = r.nextInt(cntVertex); // generate 2 indexes int i2 = r.nextInt(cntVertex); // within vertex count while (i1 == i2) // when a loop was generated i2 = r.nextInt(cntVertex); // generate another index Edge e = new Edge(i1, i2); // indexes used as an edge if (!edges.contains(e)) // edge not there already? edges.add(e); } try{ // try to set generated vertices and edges at the given graph instance Edge[] ed = cntEdges > 0 ? edges.toArray(new Edge[cntEdges]) : null; g.setGraph(v, ed); // Check for validity of the graph instance int[] gVert = g.getVertices(); // should deliver the same vertices as given if (gVert.length != v.length){ System.out.println("Wrong vertex count"); return false; } for(int i = 0; i < gVert.length; i++){ if (v[i] != gVert[i]){ System.out.println("Different vertex"); return false; } } Edge[] gEd = g.getEdges(); // should deliver the same edges as given if ((gEd == null && ed != null) || (gEd != null && ed == null)){ System.out.println("Different edge definition"); return false; } if (ed != null){ // compare edges if (ed.length != gEd.length){ System.out.println("Different edge count"); return false; } for(Edge ge : gEd){ if (!edges.contains(ge)){ System.out.println("Different edge"); return false; } edges.remove(ge); } } } catch(Exception ex){ // if anything goes wrong with the graph instance ex.printStackTrace(); return false; } return true; } }

Deine implementierte Klasse YourGraph könnte also folgendermaßen mit einem Zufallsgraphen getestet werden

public static void main(String[] args){ YourGraph graph = new YourGraph(); // instantiate your class if (!GraphGenerator.generate(graph,10,15)) // generate a random graph with 10 vertices and 15 edges System.out.println(graph.getClass().getSimpleName() + " generation failed!"); int d = graph.getDegree(5); // determine degree of vertex 5 boolean b = graph.isAdjacent(3,8); // determine whether vertices 3 and 8 are connected }

Lösungen anzeigen

Grundbegriffe

Aufgabe - Zuordnung

Knoten	Kantenzug	geschlossener Kantenzug	einfacher Weg	Weg	einfacher Kreis	Kreis
{A,B,C}	anzeigen verstecken nein	anzeigen verstecken nein	anzeigen verstecken ja	anzeigen verstecken ja	anzeigen verstecken nein	anzeigen verstecken nein
{M,G,H,M}	anzeigen verstecken nein	anzeigen verstecken nein	anzeigen verstecken nein	anzeigen verstecken nein	anzeigen verstecken ja	anzeigen verstecken ja
{L,M,G,H,M,L}	anzeigen verstecken nein	anzeigen verstecken ja	anzeigen verstecken nein	anzeigen verstecken nein	anzeigen verstecken nein	anzeigen verstecken nein
{Q,O,N,P,Q,M}	anzeigen verstecken nein	anzeigen verstecken nein	anzeigen verstecken nein	anzeigen verstecken ja	anzeigen verstecken nein	anzeigen verstecken nein
{G,E,D,G,F,D,G,E}	anzeigen verstecken ja	anzeigen verstecken nein	anzeigen verstecken nein	anzeigen verstecken nein	anzeigen verstecken nein	anzeigen verstecken nein
{L,H,G,E,D,G,M,L}	anzeigen verstecken nein	anzeigen verstecken nein	anzeigen verstecken nein	anzeigen verstecken nein	anzeigen verstecken nein	anzeigen verstecken ja