calculer le nombre des composantes connexes dans un graphe Fermé

Question

bon
jour , j'ai une question sur le calcul du nombre des composantes connexes dans un graphe non orienté  aprés  la suppression  de qq noeuds  a partir de son matrice adjacence par exemple on a ce garphe  avant et apres la suppression les noeuds v4,v7,v2 , donc dans la deuxieme graphe apres la suppression nous produit  3 composantes connexes {(v2),(v4),(v5,v6)},  je  besoin un idée comment ecrire ca dans java , je ne sais pas comment commence .merci

MicaLyl · Answer

Bonjour,
Est ce que tu sauvegarde ton graphe sous forme de matrice en JAVA?
Par exemple si on considère que les indices des lignes et des colonnes sont des nœuds et ce qui a dans la matrice sont les arrêtes, S'il y a une arrête entre les nœuds (Exemple entre v2 et v4) le contenue des colonnes [2,4] et [4,2] sera égal à 1. Et quand il n'y a pas d'arrête (Exemple entre v1 et v3), le contenu des colonnes [1,3] et [3,1] sera égale à -1.
Dans le cas où tu souhaiterais supprimé une arrête, il suffira alors de mettre la valeur des colonne [i,j] et [j,i] à -1
Ce n'est peut être pas optimal parce que j'ignore ce que tu comptes faire de ton graphe après o_O

Calculer le nombre des composantes connexes dans un graphe

1 réponse

Discussions similaires

Newsletters