Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.FileReader;
- import java.io.IOException;
- import java.util.LinkedList;
- public class DM {
- private static int incedenceMatrix[][];
- private static LinkedList<Integer> currentResultList;
- private static Node [] nodesArray;
- public static void main(String args[]){
- clean();
- incedenceMatrix = readIncedenceMatrix("input.txt");
- printMatrix(incedenceMatrix);
- addNodeToResult(1);
- work(1);
- System.out.println(currentResultList);
- }
- public static int[][] readIncedenceMatrix(String inputFileName) {
- try {
- BufferedReader in = new BufferedReader(new FileReader(inputFileName));
- String Line="";
- int nodesCount = Integer.parseInt(in.readLine());
- nodesArray = new Node [nodesCount];
- int Matr[][] = new int [nodesCount][nodesCount];
- int i=0;
- while((Line = in.readLine() )!=null){
- nodesArray[i] = new Node(i+1);
- String temp[]=Line.trim().split("\s+");
- for(int n=0; n<temp.length; n++)
- Matr[i][n]=Integer.parseInt(temp[n]);
- i++;
- }
- return Matr;
- }
- catch (IOException e) {
- throw new RuntimeException("Ошибка при работа с файлом: "+inputFileName,e);
- }
- }
- public static void addNodeToResult(int what){
- // добавляем вершину в список рассматриваемых:
- nodesArray[what].isVisited=true;
- currentResultList.add(what);
- }
- public static void printMatrix(int[][] Matrix) {
- String comma = "";
- for (int i = 0; i < Matrix.length; i++) {
- for (int j = 0; j < Matrix[0].length; j++) {
- if (i == Matrix.length - 1 && j == Matrix[0].length - 1)
- comma = ".";
- else
- comma = ",";
- System.out.print("{" + Matrix[i][j] + "}" + comma);
- }
- System.out.println();
- }
- }
- static int work(int currentVertex){
- LinkedList<Integer> childs = getChilds(currentVertex);
- if (childs.size() >= 1) {
- for (int child : childs) {
- if (!nodesArray[child].isVisited){
- currentResultList.add(new Integer(child));
- nodesArray[child].isVisited=true;
- work(child);
- }
- }
- }
- else {
- return currentVertex;
- }
- return 0;
- }
- public static void clean() {
- nodesArray = null;
- incedenceMatrix = null;
- currentResultList = new LinkedList<Integer>();
- }
- private static LinkedList<Integer> getChilds(int from) {
- LinkedList<Integer> childs = new LinkedList<Integer>();
- for (int j = 0; j < incedenceMatrix[from].length; j++) {
- if(incedenceMatrix[from][j] == 1){
- childs.add(j);
- }
- }
- return childs;
- }
- }
- public class Node{
- //поля
- public boolean isVisited=false;
- public String Label="";
- Node(int label){ // конструктор класса - вершины графа
- this.Label="Node "+label+"";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement