java一个图结构的遍历问题

灰太狼 2021-12-01 15:34 100阅读 0赞

问题：

用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如512234、212345等，要求：4不能在第三位，3、5不能相连。

分析：

1）  把问题归结为图结构的遍历问题。实际上6个数字就是六个结点，把6个结点连接成无向连通图，对于每一个结点求这个图形的遍历路径，所有结点的遍历路径就是最后对这6个数字的排列组合集。

2）  显然这个结果集还未达到题目的要求。从几个方面考虑：

a）3、5不能相连，实际要求这个连通图的结点3、5之间不能连通，可在构造图结构时就满足该条件，然后再遍历图。

b）不能有重复：考虑到有两个2，明显会存在重复结果，可以把结果集放在TreeSet中过滤重复结果。

c）4不能在第三位，所以仍旧在结果集中去除满足此条件的结果。

程序：

import java.util.Iterator;
    import java.util.TreeSet;
    
    public class TestQuestion {
    	private String[] b = new String[]{"1", "2","2", "3", "4", "5"};
    	private int n = b.length;
    	private boolean[] visited = new boolean[n];
    	private int[][] a = new int [n][n];
    	private String result = "";
    	private TreeSet set = new TreeSet();
    	public static void main(String[] args) {
    		new TestQuestion().start();
    	}
    	private void start() {
    		for(int i=0; i<n; i++) {
    			for(int j=0; j<n; j++) {
    				if(i==j) {
    					a[i][j] = 0;
    				}
    				else {
    					a[i][j] = 1;
    				}
    			}
    		}
    		a[3][5] = 0;
    		a[5][3] = 0;
    		for(int i=0; i<n; i++) {
    			this.depthFirstSearch(i);
    		}
    		Iterator it = set.iterator();
    		while(it.hasNext()) {
    			String string = (String)it.next();
    			if(string.indexOf("4")!=2) {
    				System.out.println(string);
    			}
    				
    		}
    			
    	}
    	private void depthFirstSearch(int startIndex) {
    		visited[startIndex] = true;
    		result = result + b[startIndex];
    		if(result.length()==n) {
    			set.add(result);
    		}
    		for(int j=0; j<n; j++) {
    			if(a[startIndex][j] == 1 && visited[j] == false) {
    				depthFirstSearch(j);
    			}
    			else {
    				continue;
    			}
    		}
    		result = result.substring(0,result.length()-1);
    		visited[startIndex] = false;
    			
    	}
    	
    
    }