Niveau d'un noeud

Fermé
noussa90 - 27 juin 2013 à 16:00
 Utilisateur anonyme - 13 juil. 2013 à 22:09
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

tarek_dotzero Messages postés 817 Date d'inscription jeudi 19 juillet 2007 Statut Membre Dernière intervention 12 avril 2022 121
Modifié par tarek_dotzero le 27/06/2013 à 22:05
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.
0
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;
}
0
Utilisateur anonyme
13 juil. 2013 à 22:09
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
0