非完全图的TSP问题java解法(拙劣)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class ThirdTest {

    private WeightedGraph G;
    private Node head;
    private Node node;
    private int count = 0;
    private int s;

    private class Node{
        private int pre[];
        private Node next;

        public Node(int[] pre, Node node) {
            this.pre = pre;
            this.next = node;
        }

        public Node(int[] pre) {
            this.pre = pre;
            this.next = null;
        }

        public Node() {
            this.next = null;
            this.pre = null;
        }
    }

    public ThirdTest(WeightedGraph G, int s) {
        this.G = G;
        int visited = 0;
        int pre[] = new int[G.V()];
        this.head = null;
        Arrays.fill(pre, -1);
        this.s = s;

        dfs(visited, s, s, G.V(), pre, true);
    }

    private void dfs(int visited, int v, int parent, int left, int[] pre, boolean isInit){
        dfs(visited, v, parent, G.V(), pre);
    }

    public void dfs(int visited, int v, int parent, int left, int[] pre) {
        visited += (1 << v);
        pre[v] = parent;
        left--;

        if (left == 0 && G.hasEdge(v, s)) {
            count++;
            int[] preArray;
            preArray = new int[pre.length];
            for (int i = 0; i < pre.length; i++) {
                preArray[i] = pre[i];
            }
            preArray[s] = v;
            if (head == null) {
                node = new Node();
                head = new Node(preArray, node);
            } else {
                node.pre = preArray;
                node.next = new Node();
                node = node.next;
            }

            return;
        }

        for (int w : G.adj(v)) {
            if ((visited & (1 << w)) == 0) {
                dfs(visited, w, v, left, pre);
                pre[w] = -1;
            }
        }
        visited -= (1 << v);
    }

    public void result() {
        int[][] res = new int[count][];
        for (int i = 0; i < count; i++) {
            res[i] = head.pre;
            head = head.next;
        }
        ArrayList indexs = new ArrayList();
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < count; i++) {
            int total = total(res[i]);
            if (total < min) {
                min = total;
            }
        }

        for (int i = 0; i < count; i++) {
            int total = total(res[i]);
            if (total == min) {
                indexs.add(i);
            }
        }

        for (int index : indexs) {
            int[] result = res[index];

            ArrayList list = new ArrayList();
            list.add(s + 1);
            int cur = result[s];
            while (cur != s) {
                list.add(cur + 1);
                cur = result[cur];
            }
            list.add(cur + 1);

            Collections.reverse(list);
            StringBuilder sb = new StringBuilder();
            sb.append("总路径最短为" + min + "千米" + ",路径为: ");
            for (int a : list) {
                sb.append(a + "->");
            }

            System.out.print("不重复地从" + (s + 1) + "号城市游历这八个城市后回到起点,");
            System.out.println(sb.substring(0, sb.lastIndexOf("->")).toString());
        }
    }

    public int total(int[] pre) {
        int total = 0;
        int cur = 0;
        total += G.getWeight(cur, pre[cur]);
        cur = pre[cur];
        while (cur != 0) {
            total += G.getWeight(cur, pre[cur]);
            cur = pre[cur];
        }
        return total;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String fileName = sc.next();
        WeightedGraph g = new WeightedGraph(fileName);
        ThirdTest test = new ThirdTest(g, 0);
        test.result();
    }
}

import java.io.File;
import java.io.IOException;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class WeightedGraph {

    private int V;//城市
    private int E;//航线
    private TreeMap[] adj;//<源城市到城市,距离>

    public WeightedGraph(String filename){
        File file = new File(filename);

        try(Scanner scanner = new Scanner(file)){
            V = scanner.nextInt();

            adj = new TreeMap[V];

            for (int i = 0; i < V; i++)
                adj[i] = new TreeMap();

            E = scanner.nextInt();

            for (int i = 0; i < E; i++) {
                int a = scanner.nextInt() - 1;
                int b = scanner.nextInt() - 1;

                int weight = scanner.nextInt();

                adj[a].put(b, weight);
                adj[b].put(a, weight);
            }

        } catch (IOException e){
            e.printStackTrace();
        }
    }

    public int V() {
        return V;
    }

    public Iterable adj(int v){
        return adj[v].keySet();
    }

    public boolean hasEdge(int v, int w) {
        return adj[v].containsKey(w);
    }

    public int getWeight(int v, int w) {
        if (hasEdge(v, w))
            return adj[v].get(w);
        return -1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();

        sb.append(String.format("V = %d, E = %dn", V, E));
        for (int v = 0; v < V; v++) {
            sb.append(String.format("%d : ", v + 1));
            for (Map.Entry entry :adj[v].entrySet()) {
                sb.append(String.format("(%d : %d)", entry.getKey() + 1, entry.getValue()));
            }
            sb.append('n');
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        WeightedGraph g = new WeightedGraph("D:\GraphTest\2.txt");
        System.out.println(g.toString());
    }

}

无向有权图