Njuptn Nanyou Discrete Mathematics_ Experiment 4

Content ：
Yes, yes. n An undirected graph with nodes , Judge whether it can be drawn by one stroke .
requirement ：
For given n An undirected graph with nodes , Determine the Eulerian graph and semi Eulerian graph , If it is an Euler or semi Euler , Then all Euler （ return ） road .

package exp04;

import java.util.Stack;

class Graph {
    
    int[][] matrix;     //  The adjacency matrix of a graph 
    int n;      //  Number of vertices 
    boolean[] visted;  // Mark whether the point is accessed 
    Stack<Integer> s=new Stack();       //  Stack 
    int[] ans=new int[50];
    int count = 0;  // Record the path of Euler Road , Number of paths 

    public Graph(int[][] matrix, int n) {
    
        this.matrix = matrix;
        this.n = n;
        visted = new boolean[n];
        for (boolean v: visted) {
    
            v=false;
        }
    }

    // Traverse the graph first from the set starting depth , If a point is not visited , Then it is a non connected graph 
    public boolean Judge()
    {
    
        DFS(0);
        for(int i = 0; i < n; i++)
            if(!visted[i])
                return false;
        return true;
    }

    // Depth-first search 
    private void DFS(int x)
    {
    
        visted[x] = true;
        for(int i = 0; i < n; i++)
            if(!visted[i] && matrix[x][i]==1)
                DFS(i);
    }

    public void JudgeEuler(){
    
        int degree,start=0,num=0;
        for(int i = 0; i < n; i++)      //  If there are singular vertices , Then start from the vertex of singularity , Otherwise, from 0 set out 
        {
    
            degree = 0;
            for(int j = 0; j < n; j++)
                degree += matrix[i][j];
            if(degree % 2!=0)
            {
    
                start = i;
                num++;
            }
        }
        //  An undirected graph has an Euler path , If and only if G It's connected , And there are 0 Or 2 Odd degree nodes 
        if(num == 0 || num == 2)
        {
    
            Fleury(start);
            // The head and tail of Euler's path are equal , It means that Euler road is a circuit 
            if(ans[0] == ans[count - 1])
                System.out.println(" The graph is an Euler graph , Euler loop is ：");
            else
                System.out.println(" The graph is a semi Eulerian graph , Eulaluwei ：");
            Answer();
        }
        else
            System.out.println(" This graph is not an Eulerian or semi Eulerian graph ");

    }

    private void Answer() {
    
        for(int i = 0; i < count; i++)
            System.out.print(ans[i]+" ");
        System.out.println();
    }

    private void Fleury(int x) {
    
        int flag;
        s.push(x);
        while(!s.isEmpty())
        {
    
            flag = 0;
            for(int i = 0; i < n; i++)
            {
    
                if(matrix[s.lastElement()][i] > 0)
                {
    
                    flag = 1;
                    break;
                }
            }
            if(flag == 0)  // If there are no extensible points , Then record the point and put it out of the stack 
            {
    
                ans[count ++] = s.pop() + 1;
            }
            else  // If there is , Then it will be out of the stack and continue to search 
            {
    
                DFSGraph(s.pop());
            }
        }
    }

    private void DFSGraph(int x)
    {
    
        s.push(x);
        for(int i = 0; i < n; i++)
        {
    
            if(matrix[i][x] > 0)
            {
    
                matrix[i][x] = 0;  // Delete the side 
                matrix[x][i] = 0;
                DFSGraph(i);
                break;
            }
        }
    }
}

package exp04;

import java.awt.*;
import java.util.Scanner;

public class Test04 {
    
    public static void main(String[] args) {
    
        System.out.println(" Please enter the number of undirected graph nodes ：");
        Scanner input = new Scanner(System.in);
        int n=input.nextInt();     //  Number of undirected graph nodes 
        System.out.println(" Please enter the adjacency matrix of the undirected graph to be determined ：");
        int[][] matrix=new int[n][n];

        System.out.print(" ");
        for (int i = 1; i <=n; i++) {
    
            System.out.print(" "+i);
        }
        System.out.println();

        for (int i = 0; i < n; i++) {
           //  The adjacency matrix of the input graph 
            System.out.print(i+1);
            for (int j = 0; j < n; j++) {
    
                matrix[i][j]=input.nextInt();
            }
        }
        Graph g = new Graph(matrix,n);
        System.out.println(g.Judge()?" This graph is connected ":" This graph is unconnected ");
        if (g.Judge()==false)       //  If it's a non connected graph , No further judgment is required 
            return;
        g.JudgeEuler();
    }
}