gerichteter Graph

Status
Nicht offen für weitere Antworten.
H

Han

Gast
Hallo....ich hab da eine allgemeine Frage zu Graphen:

Wann ist in einem gerichteten Graphen ein Knoten zu einem anderen Knoten adjazent?

Angenommen mein Graph besteht aus 2 Knoten:A,B

Der Pfeil in der gerichteten Kante,die A und B miteinander verbindet, zeigt von A nach B.

Ist dann B ein benachbarter Knoten?

Und wie schauts aus wenn der Pfeil von B nach A zeigt?

mfg,
Hannes
 
B

bygones

Gast
in einer adjazenzmatrix ist eine 1 wenn eine Kante vorhanden ist, eine 0 wenn nicht.

D.h. wenn du eine gerichtete Kante von a -> b hast, so steht bei dem eintrag a/b eine 1, bei b/a eine 0.
geht die Kante von b->a so steht bei a/b 0 und bei b/a 1....
 
H

Han

Gast
Hallo....danke für die Antworten....habs jetzt einmal so implementiert wies ihr gesagt habt.

Ich hab dann aber noch eine Frage....

Und zwar hab ich eine Tiefensuche auch noch implementiert....welche bei der Methode isConnected(Graph g) zum Zug
kommt.

Angenommen ich habe einen Graph A->B->C<-D

Ist dann der Graph verbunden oder nicht? Denn bei der Tiefensuche würde es mir ja dann D nicht besuchen und ich habe isConnected so implementiert:

Code:
//Returns true if the graph is connected, false otherwise.
  public boolean isConnected() {
	  	
	  if(sizeVertices == 0){
		  return false;
	  }
	 
	  int[] val = dfs(0); //Tiefensuche welches Array zurückliefert mit besuchten Knoten.
	  
	  for(int i=0; i<val.length;i++){
		  if(val[i]==0){
			  return false;
		  }
	  }
	  return true;
  }

Also bei mir leifert dann isConnected() false.....was aber anschaulich irgendwie komisch erscheint...da ja der Graph verbunden ist...kann mir wer helfen?

mfg,
Hannes
 
B

bygones

Gast
nein er ist nicht verbunden, es fehlt ja eine Kante von C->D somit findest du beim startpunkt a bei tiefen-/breitensuche den Knoten D nicht !
 
H

Han

Gast
Hallo....jetzt hab ich noch eine Frage:

Wann ist in einem gerichteten Graphen eine Kante inzident?

Im Skript steht folgende Defnition:
Kante,die 2 adjazente Knoten verbindet,heißt inzident zu diesem Knoten.

Angenommen ich habe folgende Verbindung:
A->B

Ist dann die Kante inzident?...ich kapiers noch nciht ganz....

mfg,
Hannes
 
H

Han

Gast
Na ja ich glaub so einfach is nicht...denn was is wenn ich wissen will ob die Kante bei Knoten B indizent ist.
Dann ist aber A kein adjazenter Knoten zu B. Also müsste demnach die Kante wenn man das Ganze von B aus betrachtet nicht indizent sein oder?
Umgekehrt aber schon oder?

mfg,
Hannes
 
B

bygones

Gast
indizenz kommt nur in einem ungerichteten Graphen vor !

wiki hat gesagt.:
Inzidenz bezeichnet eine Beziehung zwischen Knoten und Kanten in einem ungerichteten Graph. Ein Knoten heißt in einem ungerichteten Graph inzident mit einer Kante, wenn er von dieser Kante berührt wird, dass heißt, wenn diese ihn enthält.
 
Status
Nicht offen für weitere Antworten.

Ähnliche Java Themen

Anzeige

Neue Themen


Oben