Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Graph durchlaufen
Hey,
ich lern grad für AuD Klausur und hab mal BFS mit Adjazenliste versucht.
Also angenommen ein Graph ist in einer ArrayList[] gespeichert.
public List bfs(int value) {
List result= new List();
Queue<Integer> q= new ArrayList<Integer>();
q.enqeue(value);
while(!q.isEmpty()){
int node= q.dequeue();
if(!result.contains(node)){
result.add(node);
}while(!adjazenzlist[node].isEmpty){
if(!result.contains(node){
q.enqeue(adjazenzlist[node].poll());
}
}
return result;
}würde das ungefähr so funktionieren, oder seht ihr einen groben fehler?
Ok ich habs jetzt mit dem Programm in Java hinbekommen.
Also die Breitensuche für den Graphen funktioniert.
Die Aufgabe ist aus der MT AUD Klausur von 25 märz 2013
Wieso funktioniert die Breitensuche auch wenn man nicht überprüft ob ein Knoten schon besucht war
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Graph {
public ArrayList<Integer>[] adjlist = new ArrayList[9];
public Graph() {
for (int i = 0; i < adjlist.length; i++) {
adjlist[i] = new ArrayList<Integer>();
}
}
public void add(int node, int neighbour) {
adjlist[node].add(neighbour);
}
public List<Integer> bfs(int value) {
List<Integer> result = new ArrayList();
LinkedList<Integer> q = new LinkedList<Integer>();
List<Integer> speicher= new ArrayList();
q.add(value);
while (!q.isEmpty()) {
int node = q.poll();
if (!result.contains(node)) {
result.add(node);
System.out.println(result.toString());
}
for(Integer i: adjlist[node]){
q.add(i);
}
if(result.size()>=adjlist.length){
break;
}
}
return result;
}
public static void main(String[] args) {
Graph g = new Graph();
g.add(0, 1);
g.add(0, 4);
g.add(0, 6);
g.add(1, 0);
g.add(1, 2);
g.add(2, 1);
g.add(2, 3);
g.add(2, 7);
g.add(3, 2);
g.add(3, 4);
g.add(3, 8);
g.add(4, 0);
g.add(4, 3);
g.add(4, 5);
g.add(5, 4);
g.add(6, 0);
g.add(7, 2);
g.add(8, 3);
// for (ArrayList<Integer> i : g.adjlist) {
// System.out.println(i.toString());
// }
System.out.println(g.bfs(6).toString());
}
}Also List ist ein Interface, also nicht instanziierbar.
jo ich habs schon im zweiten Code korrigiert das erste war nur so ne Art pseudo
Du entfernst Kanten aus der Adjazenzliste. Nach abarbeiten eines Knotens gibt es keine Kanten mehr, die von diesem Knoten zu irgendeinem anderen Knoten führen. Daher terminiert dein Programm irgendwann. Allerdings solltest du die Adjazenzliste besser nicht verändern. Es hilft dir nämlich wenig, wenn du eine Breitensuche auf deinem Graphen gemacht hast, aber dein Graph danach nicht mehr existiert ;).
ich habs grad aufm Papier durchgeführt was das Programm macht, er legt die einzelnen Knoten öfter als einmal auf die Queue aber wegen
der bedingung das result keine Duplikate entahlten kann, funktioniert es trotzdem.
Wie könnte ich es hinbekommen dass die Queue auch nur jeden Knoten einmal aufnimmt?
.
bfs jetzt verbessert.
Habe noch eine Liste angeleget um besuchte Knoten zu speichern jetzt läufts so wies soll
public List<Integer> bfs(int value) {
List<Integer> result = new ArrayList();
LinkedList<Integer> q = new LinkedList<Integer>();
List<Integer> visitedNodes = new ArrayList();
q.add(value);
while (!q.isEmpty()) {
int node = q.poll();
if (!result.contains(node)) {
result.add(node);
}
for(Integer i: adjlist[node]){
if(!visitedNodes.contains(i)){
q.add(i);
}
System.out.println(q.toString());
visitedNodes.add(i);
}
}
return result;
}[m]contains()[/m] auf einer [m]ArrayList[/m] ist in O(n), d.h. in linearer Zeit. Das macht deine Breitensuche unnötig langsam. Stattdessen benutzt du für die [m]visitedNodes[/m]-Datenstruktur besser irgendwas mit Lookup in O(1) oder zumindest O(log n), also ein [m]TreeSet[/m] (logarithmisch), [m]HashSet[/m] (konstant) oder wenn deine Objekte keine Integer sondern Klassen sind eine [m]boolean[/m] Membervariable in diesem Objekt (auch colorbit genannt).