Java实现无向图的欧拉回路判断问题

1 问题描述

Problem Description

欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？

Input

测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是节点数N ( 1 < N < 1000 )和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。当N为0时输入结

束。

Output

每个测试用例的输出占一行，若欧拉回路存在则输出1，否则输出0。

Sample Input

3 3

1 2

1 3

2 3

3 2

1 2

2 3

0

Sample Output

1

0

2 解决方案

package com.liuzhen.practice;

import java.util.ArrayList;

import java.util.Scanner;

public class Main {

    public static int MAX = 1000;

    public static int[][] map = new int[MAX][MAX];      //输入图

    public static ArrayList<Integer> result = new ArrayList<Integer>();  //用于存放最终输出结果

    //判断给定图的每个顶点的度是否均为偶数

    public boolean judge(int[] degree) {

        for(int i = 0;i < degree.length;i++) {

            if(degree[i] % 2 != 0)

                return false;

        }

        return true;

    }

    //使用BFS遍历，判断给定图是否为连通图

    public boolean bfs(int n) {

        boolean[] used = new boolean[n];

        ArrayList<Integer> list = new ArrayList<Integer>();

        list.add(0);

        used[0] = true;

        while(!list.isEmpty()) {

            int temp = list.get(0);

            list.remove(0);

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

                if(!used[i] && map[temp][i] != 0) {

                    used[i] = true;

                    list.add(i);

                }

            }

        }

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

            if(used[i] == false)

                return false;

        }

        return true;

    }

    public static void main(String[] args) {

        Main test = new Main();

        Scanner in = new Scanner(System.in);

        while(true) {

            int n = in.nextInt();       //输入图的顶点数

            if(n == 0)

                break;

            int m = in.nextInt();       //输入图的边数目

            int[] degree = new int[n];   //用于计算输入图的每个顶点的度

            for(int i = 0;i < m;i++) {

                int a = in.nextInt();

                int b = in.nextInt();

                map[a - 1][b - 1] = 1;

                map[b - 1][a - 1] = 1;

                degree[a - 1]++;

                degree[b - 1]++;

            }

            if(test.judge(degree) && test.bfs(n))

                result.add(1);

            else

                result.add(0);

        }

        for(int i = 0;i < result.size();i++)

            System.out.println(result.get(i));

    }

}

运行结果：

巴特西

Java实现无向图的欧拉回路判断问题

最新文章

热门文章