Essayez de tourner dans ces informations en matrice d'adjacence mais confondue sur la manière dont stocke les informations dans une arrayliste d'arraylist. Aide sur la manière de faire une matrice d'adjacence serait appréciée.
3 Réponses :
Si les données que vous extrayez de STDIN sont valides, vous devez être capable de construire une matrice de adjacence comme celle-ci:
public static void main(String[] args) {
String[] input = "1 2 5 \n3 4 2 \n".split("\n");
int adjMatrix[][];
int max = 0;
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
for(int i=0; i<input.length; i++) {
String[] str = input[i].split("[\\s,]+");
ArrayList<Integer> inner = new ArrayList<Integer>();
for(int j = 0; j < str.length; j++) {
inner.add(Integer.parseInt(str[j]));
}
max = Math.max(Math.max(max, inner.get(0)), inner.get(1));
list.add(inner);
}
int[][] adjacencyMatrix = new int[max+1][max+1];
for(int i=0; i<list.size(); i++) {
int source = list.get(i).get(0);
int dest = list.get(i).get(1);
adjacencyMatrix[source][dest] += 1;
}
for(int i=0; i<adjacencyMatrix.length; i++) {
for(int j=0; j<adjacencyMatrix[i].length; j++) {
System.out.print(adjacencyMatrix[i][j]);
}
System.out.println("");
}
}
public static void main(String[] args) {
Scanner stdin = new Scanner(System.in);
int nodeCount = 0;
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
while(stdin.hasNext()) {
String[] str = stdin.nextLine().split("[\\s,]+");
ArrayList<Integer> inner = new ArrayList<Integer>();
for(int i = 0; i < str.length; i++) {
int value = Integer.parseInt(str[i]);
inner.add(value);
if(value > nodeCount && i != str.length - 1){
nodeCount = value;
}
}
list.add(inner);
}
int adjMatrix[][] = new int[nodeCount + 1][nodeCount + 1];
for(ArrayList<Integer> inner : list){
adjMatrix[inner.get(0)][inner.get(1)] += 1;
}
for(int i = 0; i < nodeCount; i++){
for(int j = 0; j < nodeCount; j++){
System.out.print(adjMatrix[i][j] + " ");
}
System.out.println();
}
}
Peut-être que vous devriez utiliser quelque chose comme celui-ci comme point de départ.
public class AdjacencyMatrix {
public static void main(String... args) {
List<Edge> edges = readFromStdIn();
Graph graph = new Graph(edges);
int[][] adjacencyMatrix = graph.getAdjacencyMatrix();
printMatrix(adjacencyMatrix);
}
private static List<Edge> readFromStdIn() {
List<Edge> edges = new ArrayList<Edge>();
try (Scanner scanner = new Scanner(System.in)) {
boolean readOn = true;
while (scanner.hasNext() && readOn) {
String[] strings = scanner.nextLine().split("[\\s,]+");
if (strings.length == 3) {
edges.add(new Edge(Integer.parseInt(strings[0]), Integer.parseInt(strings[1]),
Integer.parseInt(strings[2])));
} else {
readOn = false;
}
}
}
return edges;
}
private static void printMatrix(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
}
class Edge {
final int source;
final int destination;
final int weight;
Edge(int source, int destination, int weight) {
this.source = source;
this.destination = destination;
this.weight = weight;
}
}
class Graph {
final List<Edge> edges;
Graph(List<Edge> edges) {
this.edges = edges;
}
public int[][] getAdjacencyMatrix() {
int n = getNodeCount();
int[][] matrix = new int[n][n];
for (Edge e : edges) {
matrix[e.source][e.destination] = 1;
// directed graph?
matrix[e.destination][e.source] = 1;
}
return matrix;
}
int getNodeCount() {
int maxNodeNumber = 0;
for (Edge edge : edges) {
if (edge.source > maxNodeNumber) {
maxNodeNumber = edge.source;
}
if (edge.destination > maxNodeNumber) {
maxNodeNumber = edge.destination;
}
}
return maxNodeNumber + 1;
}
}
Le titre indique que vous souhaitez une matrice d'adjacence, mais dans le texte, vous parlez de liste de adjacence. C'est deux choses différentes. Que voulez-vous faire avec la matrice / la liste? Voulez-vous l'imprimer à stdout? Ou voulez-vous simplement l'avoir dans une sorte de structure de données? Pour une matrice, cela pourrait être aussi simple que
int [n] [n] oùn est le nombre de nœuds, en supposant que vos nœuds sont numérotés de 0 à N-1. Quelle est la sortie souhaitée?@Jochenreinhardt Woops! C'était une faute de frappe, je voulais dire matrice et pas la liste. Je souhaite diriger l'algorithme Floyd-Warshall et éventuellement produire deux matrices, une représentant des distances et l'autre pour les parents.