DFS深度优先遍历

按要求打印数组的排列情况

要求：“4”不能在第三位，“3”，“5”不能相连

   //DFS深度优先遍历 打印数组的排列情况 4不能在第三位，3，5不能相连
package com.qyc.stringArithmetic;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

import org.hamcrest.core.CombinableMatcher.CombinableBothMatcher;
import org.junit.Test;

public class String_Arithmetic {
    private int [] numbers= new int []{1,2,2,3,4,5};
    private int n = numbers.length;

    private boolean visited[] = new boolean[n];
    private int[][] graph = new int [n][n];
    private String combination = "";

    public void buildGraph() {

        for(int i=0;i<n;i++){
            for(int j = 0;j<n;j++){

                if(i == j){
                    graph[i][j] = 0;
                }else{
                    graph[i][j] = 1;
                }
            }
        }
        graph[3][5] = 0;
        graph[5][3] = 0;
    }

    public Set<String> getAllCombination() {
        buildGraph();
        Set<String> set = new HashSet<String>();
        for(int i=0;i<n;i++){
            this.deptFirstSearch(i, set);
        }
        return set;

    }

    public void deptFirstSearch(int start,Set<String> set) {
        visited[start] = true;
        combination = combination+numbers[start];
        if(combination.length()==n){
            if(combination.indexOf("4")!=2){
                set.add(combination);
            }
        }
        for(int j=0;j<n;j++){
            if(graph[start][j]==1&&visited[j]==false){
                deptFirstSearch(j, set);
            }
        }
        combination=combination.substring(0,combination.length()-1);
        visited[start] = false;
    }
    public static void main(String[] args) {
        String_Arithmetic string_Arithmetic = new String_Arithmetic();
        Set<String> set = string_Arithmetic.getAllCombination();
        Iterator<String> iterator = set.iterator();
        while (iterator.hasNext()) {
            String aString = (String)iterator.next();
            System.out.println(aString);
        }

    }
}