過去ログ

kasama

#19592 Eulerパス検索クラスEulerPathの内容

import java.util.*;

public class EulerPath {
　private boolean[][] matrix;
　private List archPath;

　public EulerPath(boolean[][] matrix) {
　　this.matrix = matrix;
　}
　public List scan(int startNode) {
　　return scan(startNode, startNode);
　}
　public List scan(int startNode, int endNode) {
　　return scan(startNode, endNode, matrix[0].length);
　}
　public List scan(int startNode, int endNode, int length) {
　　archPath = new ArrayList();
　　scan(startNode, endNode, length, new ArrayList());
　　return archPath;
　}
　private void scan(int startNode, int endNode, int length, List archList) {
　　if (archList.size() > length) return;
　　if (startNode == endNode && archList.size() == length) {
　　　archPath.add(archList);
　　　return;
　　}
　　for (int j = 0; j < matrix[startNode].length; ++j) {
　　　if (matrix[startNode][j]) {
　　　　for (int i = 0; i < matrix.length; ++i) {
　　　　　if (i != startNode && matrix[i][j]) {
　　　　　　Integer arch = new Integer(j);
　　　　　　if (!archList.contains(arch)) {
　　　　　　　List newArchList = new ArrayList(archList);
　　　　　　　newArchList.add(arch);
　　　　　　　scan(i, endNode, length, newArchList);
　　　　　　}
　　　　　　break;
　　　　　}
　　　　}
　　　}
　　}
　}
}

訂正：インシデンス行列の行と列が逆でした。直接解法に関係しませんが気持ちが悪いので訂正(10/14)

和歌山　　 10月14日（火） 20:18:44　　 MAIL:kasama@s34.co.jp 　　19593

過去問題一覧へ戻る