Как мне создать матрицу смежности из этого? - PullRequest
Новая
       70

Как мне создать матрицу смежности из этого?

0 голосов
/ 23 мая 2019

попытайтесь превратить эту информацию в матрицу смежности, но запутались в том, как 

import java.util.*;

public class graph {

  public static void main(String[] args) {
    Scanner stdin = new Scanner(System.in);
    int adjMatrix[][];
    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++) {
        inner.add(Integer.parseInt(str[i]));
      }
      list.add(inner);
    }
  }
}

хранит информацию в массиве arraylist.Помощь в том, как сделать это матрица смежности будет принята.

Ответы [ 3 ]

0 голосов
/ 23 мая 2019 
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();
    }
}
0 голосов
/ 23 мая 2019

Возможно, вам следует использовать что-то вроде этого в качестве отправной точки. 

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;
    }
}

Он вводит некоторые классы для добавления некоторой структуры в код, избегает списков, когда длина массива известна.Кроме того: он не будет создавать записи со значениями больше 1, если ребра содержатся несколько раз.

0 голосов
/ 23 мая 2019

Если данные, которые вы извлекаете из stdin, действительны, вы должны иметь возможность построить матрицу смежности следующим образом: 

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("");
    }
}

Я не принял во внимание вес, так как он не подходит дляматрица смежности

...