2019-05-23欧拉道路

package 图;
import java.util.Stack;
public class Code_欧拉道路 {
    // 这些图的问题最核心的就是如何将它们抽象成一张图
    // 欧拉道路指的是一笔画问题欧拉回路(七桥问题是无解的)
    // 这个欧拉道路通俗来说就是解决一个图形能不能一笔画成的问题 首先
    // 将这张图抽象成一张表然后检查是否 最多有两个奇点 一个也可以
    // 少于一个或者大于两个就不存在欧拉道路 而且这个一笔画的路线必须是从
    // 奇点开始可能从奇点结束(如果它存在两个奇点的话)  检测奇点的话我们只需要
    // 在这张图中那些点到另外点的路线数为奇数就可以了
    static int[][] graph = {
            {0, 1, 0, 1, 0},
            {1, 0, 1, 1, 0},
            {0, 1, 0, 1, 0},
            {1, 1, 1, 0, 1},
            {0, 0, 0, 1, 0}
    };
    static int n = graph.length;
    static int[][] vis  = new int[n][n];
    static Stack<String> stack = new Stack<String>();
    // 因为是无向图 如 A--C的路和C--A的路是不一样的这是两条路了
    // 但是在抽象到邻接矩阵上其实就是一条路
    public static void dfs_ouler(int k) {
        for(int i = 0; i < n; i++) {
            if(graph[k][i] > 0 && graph[k][i] > vis[k][i]) { 
                vis[k][i]++;
                vis[i][k]++;
                // A C间有一条路那么这条路可以表示为A走到C也可以从C走到A
                // 因为是无向图两个节点中路是没有方向的那么在邻接矩阵中 k i i k 两点表示的是一条路
                // 所以需要标记两个位置的点 另外当两个节点中存在两条路时从首先的这个节点走到另一个节点
                // 他们之间的一条路被标记 k i, i k 被标记但是到第二次实际上还是这两个点被标记从逻辑上
                // 来说这两个点就不存在路了就是你需要形象化的思考一下其实我们将这些"无向"图抽象成邻接矩阵之后
                // 不管你两个点中有多少条路其实我们每次走的都是同一条路只是相对于标记来说的这也就不可能存在两个点
                // 中存在多条路会重复走一条路的现象
                dfs_ouler(i);
                stack.push((char)('A' + k) + "->" + (char)('A' + i));
                // 打印路径
            }
        }
    }
    public static void main(String[] args) {
        dfs_ouler(4); // 你输出不是奇点的数是没有意义的
        while(!stack.empty()) {
            System.out.println(stack.pop());
        }
    }
···