Graph - Versionsgeschichte

Akaibel am 23. Januar 2022 um 16:58 Uhr

2022-01-23T16:58:32Z

← Nächstältere Version		Version vom 23. Januar 2022, 16:58 Uhr
Zeile 66:		Zeile 66:
	Der oben dargestelle Graph hat folgende Adjazenzliste:		Der oben dargestelle Graph hat folgende Adjazenzliste:

	<code>		<code>
	'''Berlin''' → Hamburg (289) → Hannover (290)		'''Berlin''' → Hamburg (289) → Hannover (290)
	↓		↓
Zeile 82:		Zeile 82:
	↓		↓
	'''Koeln''' → Dortmund (93) → Frankfurt (189)		'''Koeln''' → Dortmund (93) → Frankfurt (189)
	</code>		</code>

	==Traversierungen von Graphen==		==Traversierungen von Graphen==
Zeile 118:		Zeile 118:
	Voraussetzung: kein Knoten ist markiert!		Voraussetzung: kein Knoten ist markiert!

	<code>		<code>
	public List<Vertex> tiefendurchlauf(Graph pGraph, Vertex pNode){		public List<Vertex> tiefendurchlauf(Graph pGraph, Vertex pNode){
	List<Vertex> ergebnis = new List<>();		List<Vertex> ergebnis = new List<>();
Zeile 143:		Zeile 143:
	return ergebnis;		return ergebnis;
	}		}
	</code>		</code>

	=== Breitendurchlauf===		=== Breitendurchlauf===
Zeile 192:		Zeile 192:
	So wächst die <code>knotenListe</code> von einem Element (=dem Startknoten) beginnend immer weiter an, während sie durchlaufen wird. Die [[Schleife (Informatik)\|Schleife]] kommt zum Ende, wenn alle Knoten eingefügt und als ''besucht'' gekennzeichnet sind.		So wächst die <code>knotenListe</code> von einem Element (=dem Startknoten) beginnend immer weiter an, während sie durchlaufen wird. Die [[Schleife (Informatik)\|Schleife]] kommt zum Ende, wenn alle Knoten eingefügt und als ''besucht'' gekennzeichnet sind.

	<code>		<code>
	public List<Vertex> breitenDurchlauf(Graph pGraph, Vertex pStart){		public List<Vertex> breitenDurchlauf(Graph pGraph, Vertex pStart){
	List<Vertex> ergebnis = new List<Vertex>();		List<Vertex> ergebnis = new List<Vertex>();
Zeile 222:		Zeile 222:
	return ergebnis;		return ergebnis;
	}		}
	</code>		</code>

	== Backtracking: kürzeste Wege auf Graphen ==		== Backtracking: kürzeste Wege auf Graphen ==

Akaibel: /* Erklärvideos */

2020-11-03T20:32:50Z

Erklärvideos

← Nächstältere Version		Version vom 3. November 2020, 20:32 Uhr
Zeile 18:		Zeile 18:
	* [https://youtu.be/2mHKVXy0xqo Breitendurchlauf: Implementierung]		* [https://youtu.be/2mHKVXy0xqo Breitendurchlauf: Implementierung]

	* [https://youtu.be/cdNonZrj_WE] Tiefendurchlauf: Implementierung]		* [https://youtu.be/cdNonZrj_WE Tiefendurchlauf: Implementierung]

	=Fachbegriffe=		=Fachbegriffe=

Akaibel: /* Fachbegriffe */

2020-05-26T14:04:03Z

Fachbegriffe

← Nächstältere Version		Version vom 26. Mai 2020, 14:04 Uhr
Zeile 11:		Zeile 11:

	Ein Graph kann entweder als Graph, als '''Adjazenzliste''' oder als '''Adjazenzmatrix''' dargestellt werden.		Ein Graph kann entweder als Graph, als '''Adjazenzliste''' oder als '''Adjazenzmatrix''' dargestellt werden.

			=Erklärvideos=

			* [https://youtu.be/bZLxTuG8cY0 Breiten- und Tiefendurchlauf: Theorie]

			* [https://youtu.be/2mHKVXy0xqo Breitendurchlauf: Implementierung]

			* [https://youtu.be/cdNonZrj_WE] Tiefendurchlauf: Implementierung]

	=Fachbegriffe=		=Fachbegriffe=

	Graph, Knoten, markieren, Kante, Gewicht, Traversierung, Breitendurchlauf, Tiefendurchlauf		Graph, Knoten, markieren, Kante, Gewicht, Traversierung, Breitendurchlauf, Tiefendurchlauf

	=Schnittstellenbeschreibung=		=Schnittstellenbeschreibung=

Akaibel am 29. März 2020 um 14:39 Uhr

2020-03-29T14:39:12Z

← Nächstältere Version		Version vom 29. März 2020, 14:39 Uhr
Zeile 5:		Zeile 5:

	[[File:Graph_staedte_entfernungen.png\|thumb\|Graph für die Distanzen zwischen Städten \|400px]]		[[File:Graph_staedte_entfernungen.png\|thumb\|Graph für die Distanzen zwischen Städten \|400px]]
			<font color='red'>'''nur relevant für den Leistungskurs!'''</font>
	<font color='red'>'''~~Diese Seite entspricht~~ den ~~Vorgaben des Abi 18 (und folgenden).~~'''</font>

	Ein Graph ist in der Graphentheorie eine Struktur, die eine Menge von Objekten zusammen mit den zwischen diesen Objekten bestehenden Verbindungen repräsentiert.		Ein Graph ist in der Graphentheorie eine Struktur, die eine Menge von Objekten zusammen mit den zwischen diesen Objekten bestehenden Verbindungen repräsentiert.

	Die mathematischen Abstraktionen der Objekte werden dabei '''Knoten''' des Graphen genannt. Die paarweisen Verbindungen zwischen Knoten heißen '''Kanten'''.		Die mathematischen Abstraktionen der Objekte werden dabei '''Knoten''' des Graphen genannt. Die paarweisen Verbindungen zwischen Knoten heißen '''Kanten'''.

Akaibel: /* Implementierung */

2019-09-12T17:10:09Z

Implementierung

← Nächstältere Version		Version vom 12. September 2019, 17:10 Uhr
Zeile 112:		Zeile 112:
	<code>		<code>
	public List<Vertex> tiefendurchlauf(Graph pGraph, Vertex pNode){		public List<Vertex> tiefendurchlauf(Graph pGraph, Vertex pNode){
	List<Vertex> ergebnis = new List();		List<Vertex> ergebnis = new List<>();

	'''//Abbruchbedingung'''		'''//Abbruchbedingung'''
Zeile 128:		Zeile 128:
	//Nachbarn mit for-Schleife durchlaufen		//Nachbarn mit for-Schleife durchlaufen
	'''for(nachbarn.toFirst(); nachbarn.hasAccess(); nachbarn.next()){'''		'''for(nachbarn.toFirst(); nachbarn.hasAccess(); nachbarn.next()){'''
	Vertex aktuellerNachbar = ~~(Vertex)~~nachbarn.getContent();		Vertex aktuellerNachbar = nachbarn.getContent();
	'''//Rekursiver Aufruf'''		'''//Rekursiver Aufruf'''
	List<Vertex> erg2 = <b><u>tiefendurchlauf(pGraph, aktuellerNachbar)</u></b>;		List<Vertex> erg2 = <b><u>tiefendurchlauf(pGraph, aktuellerNachbar)</u></b>;

Akaibel: /* Implementierung */

2019-09-12T09:46:08Z

Implementierung

← Nächstältere Version		Version vom 12. September 2019, 09:46 Uhr
Zeile 111:		Zeile 111:

	<code>		<code>
	public List tiefendurchlauf(Graph pGraph, Vertex pNode){		public List<Vertex> tiefendurchlauf(Graph pGraph, Vertex pNode){
	List<Vertex> ergebnis = new List();		List<Vertex> ergebnis = new List();

Akaibel: /* Schnittstellenbeschreibung */

2019-06-23T13:30:40Z

Schnittstellenbeschreibung

← Nächstältere Version		Version vom 23. Juni 2019, 13:30 Uhr
Zeile 14:		Zeile 14:
	Ein Graph kann entweder als Graph, als '''Adjazenzliste''' oder als '''Adjazenzmatrix''' dargestellt werden.		Ein Graph kann entweder als Graph, als '''Adjazenzliste''' oder als '''Adjazenzmatrix''' dargestellt werden.

	==Schnittstellenbeschreibung==		=Fachbegriffe=
			Graph, Knoten, markieren, Kante, Gewicht, Traversierung, Breitendurchlauf, Tiefendurchlauf
			=Schnittstellenbeschreibung=

	[[Medium:Graph_Schnittstellen_Abitur_2018.pdf\|Graph Schnittstellenbeschreibung (ab Abi 2018)]]		[[Medium:Graph_Schnittstellen_Abitur_2018.pdf\|Graph Schnittstellenbeschreibung (ab Abi 2018)]]

Akaibel: /* Implementierung */

2017-09-13T17:39:46Z

Implementierung

← Nächstältere Version		Version vom 13. September 2017, 17:39 Uhr
Zeile 110:		Zeile 110:
	public List tiefendurchlauf(Graph pGraph, Vertex pNode){		public List tiefendurchlauf(Graph pGraph, Vertex pNode){
	List<Vertex> ergebnis = new List();		List<Vertex> ergebnis = new List();

	'''//Abbruchbedingung'''		'''//Abbruchbedingung'''
	if(pNode.isMarked()){		if(pNode.isMarked()){
	return ergebnis;		return ergebnis;
	}		}

	// pNode an die ergebnis-Liste anhaengen und markieren		// pNode an die ergebnis-Liste anhaengen und markieren
	ergebnis.append(pNode);		ergebnis.append(pNode);
	pNode.setMark(true);		pNode.setMark(true);

	//Alle Nachbarn von pNode		//Alle Nachbarn von pNode
	List<Vertex> nachbarn = pGraph.getNeighbours(pNode);		List<Vertex> nachbarn = pGraph.getNeighbours(pNode);

	//Nachbarn mit for-Schleife durchlaufen		//Nachbarn mit for-Schleife durchlaufen
	for(nachbarn.toFirst(); nachbarn.hasAccess(); nachbarn.next()){		'''for(nachbarn.toFirst(); nachbarn.hasAccess(); nachbarn.next()){'''
	Vertex aktuellerNachbar = (Vertex)nachbarn.getContent();		Vertex aktuellerNachbar = (Vertex)nachbarn.getContent();
	'''//Rekursiver Aufruf'''		'''//Rekursiver Aufruf'''

Akaibel: /* Implementierung */

2017-09-13T17:38:38Z

Implementierung

← Nächstältere Version		Version vom 13. September 2017, 17:38 Uhr
Zeile 180:		Zeile 180:
	public List<Vertex> breitenDurchlauf(Graph pGraph, Vertex pStart){		public List<Vertex> breitenDurchlauf(Graph pGraph, Vertex pStart){
	List<Vertex> ergebnis = new List<Vertex>();		List<Vertex> ergebnis = new List<Vertex>();
			// alle Markierungen loeschen
	pGraph.setAllVertexMarks(false);		pGraph.setAllVertexMarks(false);
	pGraph.setAllEdgeMarks(false);		pGraph.setAllEdgeMarks(false);
	pStart.setMark(true);		// den Startknoten markieren und in ergebnis einfuegen
	ergebnis.append(pStart);		'''pStart.setMark(true);'''
	ergebnis.toFirst();		'''ergebnis.append(pStart);'''
	~~while~~(ergebnis.~~hasAccess~~()){		// ergebnis durchlaufen:
			// ergebnis hat zu Anfang nur ein Element...
			// ... waechst dann aber immer weiter!
			'''for(ergebnis.toFirst(); ergebnis.hasAccess(); ergebnis.next()){'''
	Vertex aktuell = ergebnis.getContent();		Vertex aktuell = ergebnis.getContent();
	List<Vertex> nachbarn = pGraph.getNeighbours(aktuell);		List<Vertex> nachbarn = pGraph.getNeighbours(aktuell);
	for(nachbarn.toFirst(); nachbarn.hasAccess(); nachbarn.next()){		// die Nachbarn mit einer Schleife durchlaufen
			'''for(nachbarn.toFirst(); nachbarn.hasAccess(); nachbarn.next()){'''
	Vertex aktuellerNachbar = nachbarn.getContent();		Vertex aktuellerNachbar = nachbarn.getContent();
	if(!aktuellerNachbar.isMarked()){		// Wenn der aktuelleNachbar nicht markiert ist,
			// wird er zu ergebnis hinzugefuegt
			'''if(!aktuellerNachbar.isMarked()){'''
	Edge kante = pGraph.getEdge(aktuell, aktuellerNachbar);		Edge kante = pGraph.getEdge(aktuell, aktuellerNachbar);
	kante.setMark(true);		kante.setMark(true);
	aktuellerNachbar.setMark(true);		aktuellerNachbar.setMark(true);
	ergebnis.append(aktuellerNachbar);		'''ergebnis.append(aktuellerNachbar);'''
	}		}
	} // ~~end for~~		} // ende des Durchlaufs durch die Nachbarn.
	~~ergebnis~~.~~next();~~		} // ende des Durchlaufs durch ergebnis
	} // ~~end while~~
	return ergebnis;		return ergebnis;
	}		}

Akaibel: /* Implementierung */

2017-09-13T17:33:22Z

Implementierung

← Nächstältere Version		Version vom 13. September 2017, 17:33 Uhr
Zeile 104:		Zeile 104:
	====Implementierung====		====Implementierung====
	Der Tiefendurchlauf durch einen Graphen wird am einfachsten '''rekursiv''' programmiert.		Der Tiefendurchlauf durch einen Graphen wird am einfachsten '''rekursiv''' programmiert.

			Voraussetzung: kein Knoten ist markiert!

	<code>		<code>
	public List tiefendurchlauf(Graph pGraph, Vertex pNode){		public List tiefendurchlauf(Graph pGraph, Vertex pNode){
	List<Vertex> ergebnis = new List();		List<Vertex> ergebnis = new List();
			'''//Abbruchbedingung'''
			if(pNode.isMarked()){
			return ergebnis;
			}
			// pNode an die ergebnis-Liste anhaengen und markieren
	ergebnis.append(pNode);		ergebnis.append(pNode);
	pNode.setMark(true);		pNode.setMark(true);
Zeile 115:		Zeile 122:
	for(nachbarn.toFirst(); nachbarn.hasAccess(); nachbarn.next()){		for(nachbarn.toFirst(); nachbarn.hasAccess(); nachbarn.next()){
	Vertex aktuellerNachbar = (Vertex)nachbarn.getContent();		Vertex aktuellerNachbar = (Vertex)nachbarn.getContent();
	~~//Wenn der aktuelle Nachbar nicht markiert ist, also noch nicht besucht wurde,~~		'''//Rekursiver Aufruf'''
	~~//zur Liste hinzufuegen und auch seine Nachbarn durch den rekursiven Aufruf besuchen.~~		List<Vertex> erg2 = <b><u>tiefendurchlauf(pGraph, aktuellerNachbar)</u></b>;
	~~if( !aktuellerNachbar.isMarked() ){~~		ergebnis.concat(erg2);
	'''//Rekursiver Aufruf'''
	List<Vertex> erg2 = <b><u>tiefendurchlauf(pGraph, aktuellerNachbar)</u></b>;
	ergebnis.concat(erg2);
	}
	}		}
	return ergebnis;		return ergebnis;