Компоненты связности в ориентированном графе
Помогите дописать программу для нахождения компонент связности в ориентированном графе.
Вот, собственно, сам код программы:
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, а также свести вроде бы ориентированный граф к неориентированному. Нужно чтобы эти два метода вызывали сами себя же. и нужен алгоритм сведения орграфа к простому
Источник: Stack Overflow на русском