View Full Version : [Frage] Bsp3A_Testangabe22Mai02
Weiss jemand wie man den Tiefenalgorithmus verwenden kann, um einen Graphen vom Knoten 1 aus zudurchlaufen und die Adjazenzmatrix von ihm auszugeben?
In diesem Beispiel soll man nämlich solche einen Algorithmus als Pseudocode ausgeben.
Das wäre dann etwas analog zu dem Beispiel aus der Übung heute, wo der DFS-Algor. den Knotengrad ausgegeben hat.
Meine Idee wäre, in die Schleife für alle w€N(v) {}
etwas einzubauen, was jeweils dann das w und das v festhält(z.B ein Array vorhandeneKanten[]).
Ich hab das mal so angeschrieben:
Initialise {
setzte markiert[v]=0 für alle Knoten v aus V
setzte Adj[v][v]=0 für alle Knoten v aus V
DFS(1);
für alle Kanten e(v,w) in K {
A[v][w] = 1;
}
gib Adj aus;
}
DFS(v) {
markiert[v] = 1;
für alle w € N(v) {
falls markiert[w] == 0
dann {
K=K u e(v,w);
DFS(w);
}
}
K ist die Menge aller Kanten e mit v und w als Knoten.
Die Laufzeit dürfte sich nicht wirklich verändert haben, also O(|V|+|E|)
Ich glaub, Dein Algorithmus gibt nur die Adjazenzenmatrix von einem Spannbaum des Graphen aus, weil er ja die Kanten nur dann in die Menge K aufnimmt, falls der Knoten noch nicht markiert ist. Ich probiers mal:
AdjMatr(G):
Input: Graph G=(V,E)
Output: Adjazenzenmatrix A
Initialisierung: markiert[0]=0 für alle v;
Initialisierung: A[v][v]=0 für alle v;
DSF(1);
Ausgabe(A);
DSF(v):
markiert[v]=1;
FürAlle w € N(v) {
A[v][w]=1;
Falls markiert[w]==0{
DSF(w);
}
}
mfg johnDoe
muss ich einen Tiefensuche- bzw. Breitensuchealgorithmus rekursiv implementieren?
oder darf ich es auch so machen?
adjazenzmatrix(V,E){
für i = (1,...,|V|){
für j = (1,...,|V|){
falls (i,j) € E {
A[i,j] = 1;}
sonst{A[i,j]=0;}
}
}
}
adjazenzmatrix(V,E) ---> Das ist nicht adjazenzmatrix sondern inzidenzmatrix :verycool:
adjazenzmatrix(V,E) ---> Das ist nicht adjazenzmatrix sondern inzidenzmatrix :verycool: Du hast recht das könnte man auch falsch interpretieren. (Hab den Code ein klein bisschen verändert.)
Hab mir das so gedacht:
die Variable i durchläuft die Knotenmenge.
die Varialbe j durchläuft ebenfalls die Knotenmenge.
Bei jedem Durchlauf der inneren Schleife wird geschaut ob zwischen dem Knoten i und dem j eine Kante in E existiert wenn ja wird der betreffende Teil der Matrix auf 1 gesetzt wenn nicht auf 0.
dadurch erhalte ich die adjazenzmatrix, oder? (Zwei Knoten sind ja adjazent wenn zwischen ihnen eine Kante existiert)
dadurch erhalte ich die adjazenzmatrix, oder? (Zwei Knoten sind ja adjazent wenn zwischen ihnen eine Kante existiert)
Ja, das schon. Aber das hat nix mit einer Tiefen- oder Breitensuche zu tun.
Sorry, stimmt!
da hat sich ein Denkfehler eingeschlichen.
adjazenzmatrix(V,E) ---> Das ist nicht adjazenzmatrix sondern inzidenzmatrix :verycool: Wie meinst du das? Was ist die Inzidenzmatrix?
Meiner Meinung müsst das eh korrekt sein , die verbesserte Lösung von johnDo....
P.S : Eigentlich hab ich die Angabe bisserl verdreht ghabt.
Gefragt war eine Adjazenzliste...
Aber wenn ich die in dem Array so hab, ist das nicht dasselbe ??
Ich glaub, Dein Algorithmus gibt nur die Adjazenzenmatrix von einem Spannbaum des Graphen aus, weil er ja die Kanten nur dann in die Menge K aufnimmt, falls der Knoten noch nicht markiert ist. Ich probiers mal:
AdjMatr(G):
Input: Graph G=(V,E)
Output: Adjazenzenmatrix A
Initialisierung: markiert[0]=0 für alle v;
Initialisierung: A[v][v]=0 für alle v;
DSF(1);
Ausgabe(A);
DSF(v):
markiert[v]=1;
FürAlle w € N(v) {
A[v][w]=1;
Falls markiert[w]==0{
DSF(w);
}
}
mfg johnDoe
ich denke den aufruf DFS(1), muss du auch in eine schleife setzen, weil wenn du einen unzusammenhängenden graphen hast, hört der algorithmus nach der ersten komponete auf
im DFS-Algorithmus gehört nicht nur A[v][w]=1, sondern auch A[w][v]=1, weil du ja an beiden stellen eine 1 eintragen musst
hast du das mit Inzidenzmatrix gemeint? Dass ich nur in eine Richtung eingetragen habe?
Und das mit der Schleife:
Da hst du Recht falls der Graph unzusammenhängend ist.
Steht ja nicht in der Angabe wie er ist, also muss ich für den Fall sorgen ..
clemensp
18-05-2004, 16:26
im DFS-Algorithmus gehört nicht nur A[v][w]=1, sondern auch A[w][v]=1, weil du ja an beiden stellen eine 1 eintragen musst
nope muss man nicht beides machen
WEIL
zuerst wirds für den ausgangsknoten v aufgerufn für alle seine nachbarknoten w
also hat man alle a[v][w]
ABER für jeden der nachbarknoten wird der algorithmus auch aufgerufen
und da tauschen die beiden die plätze
jetzt is einer der vorigen w knoten usner v
für alle dessen nachbarknoten wird jetzt die schleife aufgerufen
da der eintrag in die adjazenzliste immer gemacht wird auch wenn knoten w schon markiert ist wird das also automatisch erledigt
weil einer der w knoten ist der knoten von dem wir die funktion aufgerufn haben...
hm i hoff das is halbwegs klar *gg*
uj, das macht das ganz dann wirklich kompliziert, da ja der Graph gerichtet sein soll!
Das heisst es darf ja gar nicht umgekehrt auch eingetragen gehören!
maitscha
18-05-2004, 16:33
ahmmmm... war da nicht die Adjazenzliste gefragt??? Wenn ja, dann würde ja der Pseudecode sehr minimiert aussehen:
Adjazenzliste() {
für alle v von V
{
ausgeben(v);
für alle w = N(v)
{
ausgeben(w);
}
neue_Zeile();
}
}
clemensp
18-05-2004, 16:38
?
gerichteter graph
hm welches bsp is das jetz konkret ^^
also bsp 3a
vom 22.mai 02 is ein ungerichteter graph soweit i des seh
clemensp
18-05-2004, 16:41
zu dem test gäbs übrigns hier
http://hades.gothic.at/iforum/showthread.php?t=13895
scho einiges
(is ein alter thread ausn vorjahr :) )
ahmmmm... war da nicht die Adjazenzliste gefragt??? Wenn ja, dann würde ja der Pseudecode sehr minimiert aussehen:
Adjazenzliste() {
für alle v von V
{
ausgeben(v);
für alle w = N(v)
{
ausgeben(w);
}
neue_Zeile();
}
}
das wuerd jez aber nur die nachbarknoten ausgeben, sollte aber auch 0 ausgeben wenn der knoten kein nachbarknoten is, wenn ich das richtig verstanden hab :)
clemensp
18-05-2004, 16:49
in ner adjazenzLISTE sind nur die nachbarknoten gespeichert
siehe skript seite 114
in ner adjazenzLISTE sind nur die nachbarknoten gespeichert
siehe skript seite 114
aja sorry, ich bin von ner matrix ausgegangen :hewa:
?
gerichteter graph
hm welches bsp is das jetz konkret ^^
also bsp 3a
vom 22.mai 02 is ein ungerichteter graph soweit i des seh
tschuldigung, ahb mich verschaut, es ist eh ein ungerichteter...
sonst wärs wirklich komplexer ;)
Adjazenzliste() {
für alle v von V
{
ausgeben(v);
für alle w = N(v)
{
ausgeben(w);
}
neue_Zeile();
}
}
Ja, so ungefähr müsste es dann sein.
Gemäss Skriptum:
Als alternative Umsetzung bieten sich Felder (Arrays) an:
Hierbei gibt es einen Eintrag index(v) für jeden Knoten, der angibt, an welcher Stelle in der Kantenliste (edgelist) die Nachbarliste von v beginnt.
für das Beispiel aus dem Skriptum:
1->2->3->
2->1->3->
3->1->2->3->
wäre das laut Skriptum dann
index[v]=1,3,5
edgelist[e]=2,3|1,3|1,2,3|
ganz verstehn tu ich das aber nicht
clemensp
18-05-2004, 17:43
naja wenn mas in einer liste SPEICHERN sollte
dann braucht man ja eigentlich nur
für alle w von N(v){
v.add(w);
}
das würde dann zur liste vom knoten v den knoten w dazugebn...
wenns a normale liste wär ^^
s kommt halt drauf an was ma alles verwenden darf an algorithmen aber ich glaub nicht das man dann noch die liste implementiern muss
wenns ausgegebn werden müsste...
dafür hab ich heute schoin was geschriebn
initialisiere markiert[v]=0 für alle v;
Adjazenz (1); ich ruf die funktion auf die ich gleich progge
ALOGRITHMUS adjazenz(v){
markiert[v]=1;
ausgeben(v + ":");
für alle w von N(v){
ausgeben(w + ", ");
}
NEUEZEILE;
für alle w von N(v){
wenn (markiert==0) {
Adjazenz(w);
}
}
das is aber eigntlich e das was maitscha schon gepostet hat nur das die tiefensuche auch dabei is :)
initialisiere markiert[v]=0 für alle v;
Adjazenz (1); ich ruf die funktion auf die ich gleich progge
ALOGRITHMUS adjazenz(v){
markiert[v]=1;
ausgeben(v + ":");
für alle w von N(v){
ausgeben(w + ", ");
}
NEUEZEILE;
für alle w von N(v){
wenn (markiert==0) {
Adjazenz(w);
}
}
kan sein das ich jez bloedsinn red, aber wenn ich das mit der zusammenhangskomponente richtig verstanden hab (bin mir da net so sicher:distur: ) , dann kanns doch auch sein, dass ein graph aus 2 Teilen besteht , die nicht durch eine kante verbunden sind, wenn ich das jetzt richtig seh wuerd dein algo den 2. teil nicht finden, demnach wuerds einem auch nicht erspart bleiben ueber alle v aus V zu iterien.
bitte korregierts mich wenn das unfug is :)
solange nicht steht das es ein zusammenhängender Graph ist, hast du sicher recht.
Dann würde ich das so anschreiben:
Initialize(T,v) {
markiert[v] = 0 für alle v in V
für alle v in V {
DFS(v)
}
}
und dann im DFS:
DFS(v) {
markiert[v] = 1;
für alle v e N(v) {
v.add(w);
falls markiert[w] ==0 DFS(v)
}
jetzt müsste es funzen...
und dann im DFS:
DFS(v) {
markiert[v] = 1;
für alle v e N(v) {
v.add(w);
falls markiert[w] ==0 DFS(v)
}
wie waers mit
DFS(v) {
markiert[v]=1;
string temp = v+":"
fuer alle w e N(v) {
temp = temp+w+","
falls markiert[w] ==0 DFS(v)
}
print temp && newline
}
nur irgendwie blick ich grad nicht durch ob das so funktionieren kann :o
clemensp
18-05-2004, 19:22
jop
schon ABER
in der angabe steht eben dass es ein zusammenhängender graph is deswegn is das unnötig :)
solange nicht steht das es ein zusammenhängender Graph ist, hast du sicher recht.
Dann würde ich das so anschreiben:
Initialize(T,v) {
markiert[v] = 0 für alle v in V
für alle v in V {
DFS(v)
}
}
und dann im DFS:
DFS(v) {
markiert[v] = 1;
für alle v e N(v) {
v.add(w);
falls markiert[w] ==0 DFS(v)
}
jetzt müsste es funzen...
nö
so krigst du das problem dass du teilweise nachbarknoten öfter in die liste dazunimmst...
weil du rufst knoten 1 auf der hat den nachbar knoten 2 der noch nicht markiert ist..
also wird in der dfs funktion wieder dfs für 2aufgerufn... dann werdn alle knoten für den knoten 2 in seine liste hinzugefügt
so nehmen wir an das sind die einzigen knoten dieser komponente ...
dann wären wir fertig und er springt zurück in die haupt schleife
dort ruft er fürs nächste v wieder dfs auf
das 1. v war eins sagen wir das 2. v is jetzt der knoten 2
jetzt wird dfs für den knoten 2 aufgerufen..
o je ham ma shconmal gemacht
aber dein algorithmus fügt trotzdem nochmal alle nachbarknoten zur adjazenzliste des knoten hinzu
d.h. wir beseitign das indem wir in der hauptschleife auchnochmal prüfen ob der knoten schon markiert ist...
dann pasts :)
Initialize(T,v) {
markiert[v] = 0 für alle v in V
für alle v in V {
falls (markiert[v] ==0)
{
DFS(v)
}
}
}
DFS(v) {
markiert[v] = 1;
für alle v e N(v) {
v.add(w);
falls markiert[w] ==0 DFS(v)
}
jetzt wird dfs für den knoten 2 aufgerufen..
o je ham ma shconmal gemacht
aber dein algorithmus fügt trotzdem nochmal alle nachbarknoten zur adjazenzliste des knoten hinzu
der algorithmus von merlin kann doch gar nicht DFS 2x fuer einen knoten aufrufen, weil der knoten ja dann schon markiert waere !?
edit: imho kuerzt deine ueberpruefung den algo nur ab, aendert aber nix am ergebnis
vBulletin® v3.7.1, Copyright ©2000-2009, Jelsoft Enterprises Ltd.