Niveau d'un noeud [Fermé]

Signaler
-
Messages postés
623
Date d'inscription
vendredi 26 juillet 2002
Statut
Membre
Dernière intervention
11 novembre 2012
-
Bonjour,

Je veux déterminer le niveau d'un noeud X dans un graphe donné. Ci-dessous le code du graphe ainsi que la méthode permettant de retrouver la profondeur d'un sommet. Je n'ai aucune erreur mais je n'arrive toujours pas à compiler mon programme.

Merci pour votre aide.


public class InputGraph {
public static int [][] arc; // Matrice d'adjacense
public Object [] sommet; //objet sommet

public static int count;

public InputGraph (int n){
arc = new int [n][n];
sommet = new Object[n];

}
public int GetSize (){ // récupère la taille du sommet
return sommet.length;

}

public void SetSommet(int node, Object label){ //permet d'ajouter un sommet
sommet[node]=label;

}

public Object GetSommet(int node){ // récupère la valeur d'un sommet
return sommet[node];

}


public void AddArc(int SommetDep, int SommetArr, int dist){ // ajoute un arc
arc [SommetDep][SommetArr]= dist;

}

public int GetPoids(int SommetDep, int SommetArr){ //récupère la distance
return arc [SommetDep][SommetArr];

}




public void AfficheMatrice(){ //affiche la matrice du graphe

for (int j = 0; j < arc.length; j++) {
System.out.println("");
System.out.println( " DE " + sommet[j] +" jusqu'à ");
System.out.println("");
for (int i = 0; i < arc[j].length; i++) {
if (arc[j][i]>0)
System.out.println(sommet[i] + " la distance est de " +arc[j][i] );
}
}

}
public int [] ChercheVoisin(int node){ //construit un tableau des sommets adjacents d'un sommet

count=0;

for (int i = 0; i < arc[node].length; i++) {
if (arc[node][i]>0 ) {count ++; }
}
final int[]rep = new int [count];

count=0;
for (int i = 0; i < arc[node].length; i++){
if(arc[node][i]>0){rep[count++]=i;}
}
return rep;
}}


*****************************

public static int Niveau (int noeud) {
InputGraph ex = new InputGraph (12);

int y=0;
int j;
boolean trouve;

while (noeud !=0)
{
j= ex.GetSize();
trouve=false;
while (j<=ex.GetSize()&& !trouve)
{
if (InputGraph.arc [j][noeud]!=0)
{trouve=true;
noeud=j;
y+=1;
}
j--;
}
}

return y ;
}

3 réponses

Messages postés
1608
Date d'inscription
jeudi 19 juillet 2007
Statut
Membre
Dernière intervention
17 avril 2020
111
Bonjour,

Avant de tester le code, j'ai vu une petite erreur :

while (j<=ex.GetSize()&& !trouve) 


Puisque les indices en Java commence de 0, la condition doit être :

j<ex.GetSize()


Est ce qu'il y a une erreur de compilation ou bien une erreur d'exécution, et quelle est cette erreur?

Bon Courage.
Bonjour ,

J'ai essayer de modifier le code de la méthode Niveau par un appel récursif, en gardant le même code pour le graphe. Cependant, j'ai toujours une erreur à l'exécution et cette fois-ci, c'est au niveau de la ligne "y= 1+ Niveau (j)".

Merci à vous.
*******************

public int Niveau (int noeud) { // profondeur d'un noeud

int y = 0 ;
if (noeud ==0)

y= 0;


for (int j=0;j<arc.length;j++)
{
if (arc[j][noeud]!=-1)

{y= 1+ Niveau (j);}
}



return y;
}
Messages postés
623
Date d'inscription
vendredi 26 juillet 2002
Statut
Membre
Dernière intervention
11 novembre 2012
967
Maintenant ça compile mais tu auras un ArrayOutOfBoundException car tu dois initialisr tes arrays "arc" et "sommet"

package hacktrack.picturedisplay;

public class InputGraph {
	public static int[][] arc; // Matrice d'adjacense
	public Object[] sommet; // objet sommet

	public static int count;

	public InputGraph(int n) {
		arc = new int[n][n];
		sommet = new Object[n];

	}

	public int GetSize() { // récupère la taille du sommet
		return sommet.length;

	}

	public void SetSommet(int node, Object label) { // permet d'ajouter un
													// sommet
		sommet[node] = label;

	}

	public Object GetSommet(int node) { // récupère la valeur d'un sommet
		return sommet[node];

	}

	public void AddArc(int SommetDep, int SommetArr, int dist) { // ajoute un
																	// arc
		arc[SommetDep][SommetArr] = dist;

	}

	public int GetPoids(int SommetDep, int SommetArr) { // récupère la distance
		return arc[SommetDep][SommetArr];

	}

	public void AfficheMatrice() { // affiche la matrice du graphe

		for (int j = 0; j < arc.length; j++) {
			System.out.println("");
			System.out.println(" DE " + sommet[j] + " jusqu'à ");
			System.out.println("");
			for (int i = 0; i < arc[j].length; i++) {
				if (arc[j][i] > 0)
					System.out.println(sommet[i] + " la distance est de "
							+ arc[j][i]);
			}
		}

	}

	public int[] ChercheVoisin(int node) { // construit un tableau des sommets
											// adjacents d'un sommet

		count = 0;

		for (int i = 0; i < arc[node].length; i++) {
			if (arc[node][i] > 0) {
				count++;
			}
		}
		final int[] rep = new int[count];

		count = 0;
		for (int i = 0; i < arc[node].length; i++) {
			if (arc[node][i] > 0) {
				rep[count++] = i;
			}
		}
		return rep;
	}

	public static int Niveau(int noeud) {
		InputGraph ex = new InputGraph(12);

		int y = 0;
		int j;
		boolean trouve;

		while (noeud != 0) {
			j = ex.GetSize();
			trouve = false;
			while (j <= ex.GetSize() && !trouve) {
				if (InputGraph.arc[j][noeud] != 0) {
					trouve = true;
					noeud = j;
					y += 1;
				}
				j--;
			}
		}

		return y;
	}

	public static void main(String[] args) {
		System.out.println(Niveau(4));
	}
}


;-)
HackTrack