Компоненты связности в ориентированном графе

Рейтинг: 0Ответов: 1Опубликовано: 24.04.2011

Помогите дописать программу для нахождения компонент связности в ориентированном графе.

Вот, собственно, сам код программы:

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

Осталось вызвать рекурсивно методы work и addNodeToResult, а также свести вроде бы ориентированный граф к неориентированному. Нужно чтобы эти два метода вызывали сами себя же. и нужен алгоритм сведения орграфа к простому

Ответы

Ответов пока нет.