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
  Titel Forum Antworten Datum
N gerichteter Graph aus einer Datei einlesen Java Basics - Anfänger-Themen 21
Q Tiefensuche Graph -> Schulprojekt Java Basics - Anfänger-Themen 1
F Graph Tiefensuche Methode Java Basics - Anfänger-Themen 7
S Längster Pfad zwischen zwei Vertices in einem Graph Java Basics - Anfänger-Themen 3
danieldemetry Java - Graph Komponenten - Ausgabe Java Basics - Anfänger-Themen 0
M Untersuchen ob ein Graph nach entfernen einer Kante immer noch zusammenhängend ist Java Basics - Anfänger-Themen 70
O ADT Graph nach größe Abfragen Java Basics - Anfänger-Themen 42
Z Graph einlesen Java Basics - Anfänger-Themen 2
S Ungerichteter Graph in Java Java Basics - Anfänger-Themen 1
M int double int double Graph Java Basics - Anfänger-Themen 3
A Tiefensuche in Graph Java Basics - Anfänger-Themen 4
N gerichteten Graph abspeichern Java Basics - Anfänger-Themen 2
Luk10 Frage zu Graph Tiefensuche Java Basics - Anfänger-Themen 4
S Methoden Wegsuche in einem Graph Java Basics - Anfänger-Themen 6
F Zusammenhängend Komponente suchen(Graph) Java Basics - Anfänger-Themen 4
F Kanten in Graph Java Basics - Anfänger-Themen 3
M Wth? übernimmt nichtübergebenen Wert (Graph) Java Basics - Anfänger-Themen 4
T Wie kann ich einem Graph in nem JPanel eine fixe Größe geben? Java Basics - Anfänger-Themen 6
B Graph aus 2dim-Array Java Basics - Anfänger-Themen 3

Ähnliche Java Themen

Neue Themen


Oben