data-structure-service/src/main/java/com/example/data_structure/service/GraphService.java

package com.example.data_structure.service;


import com.example.data_structure.domain.UDUWGraph;
import com.example.data_structure.domain.UDWGraph;
import com.example.data_structure.vo.GraphTraversalStep;
import com.example.data_structure.vo.GraphTraversalVO;
import com.example.data_structure.vo.PrimMinimumSpanningTree;
import org.springframework.stereotype.Service;

import java.util.*;

@Service
public class GraphService {
    private static final int NODE_NUM=7;
    //获取一个新的无向非带权图
    public UDUWGraph getNewUDUDGraph(){
        ArrayList<ArrayList<Integer>> content=new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<NODE_NUM;i++){
            ArrayList<Integer> raw=new ArrayList<Integer>();
            for(int j=0;j<NODE_NUM;j++){
                raw.add(0);
            }
            content.add(raw);
        }
        //11-21 0.7
        int tokeTimes = Math.round(((float)Math.random())*10)+11;
        int edgeNum=0;
        for(int i=1;i<=tokeTimes;i++){
            int left=Math.round(((float)Math.random())*7);
            int right=Math.round(((float)Math.random())*7);
            while(left==right){
                right=Math.round(((float)Math.random())*7);
            }
            if(content.get(left).get(right)==1){
                i--;
            }else if(content.get(left).get(right)==0){
                content.get(left).set(right,1);
                content.get(right).set(left,1);
                edgeNum++;
            }

        }
        return new UDUWGraph(content);
    }

    //获取一个新的无向带权图
    public UDWGraph getNewUDWGraph(){
        ArrayList<ArrayList<Integer>> content=new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<NODE_NUM;i++){
            ArrayList<Integer> raw=new ArrayList<Integer>();
            for(int j=0;j<NODE_NUM;j++){
                raw.add(0);
            }
            content.add(raw);
        }
        //11-21 0.7
        int tokeTimes = Math.round(((float)Math.random())*10)+11;
        int edgeNum=0;
        for(int i=1;i<=tokeTimes;i++){
            int left=Math.round(((float)Math.random())*7);
            int right=Math.round(((float)Math.random())*7);
            while(left==right){
                right=Math.round(((float)Math.random())*7);
            }
            if(content.get(left).get(right)==1){
                i--;
            }else if(content.get(left).get(right)==0){
                int weight=Math.round(((float)Math.random())*10);
                content.get(left).set(right,weight);
                content.get(right).set(left,weight);
                edgeNum++;
            }

        }
        return new UDWGraph(content);
    }

    //获取无向非带权图的广度优先遍历
    public GraphTraversalVO getBreadthFirstTraversal(UDUWGraph graph,int startVertex){
        ArrayList<ArrayList<Integer>> content=graph.getContent();
        ArrayList<Integer> visitSequence =new ArrayList<Integer>();
        ArrayList<Integer> visited=new ArrayList<Integer>();
        ArrayList<Integer> visitStartNode=new ArrayList<Integer>();
        for(int i=0;i<content.size();i++){
            System.out.println("=================add===============");
            visitStartNode.add(-1);
        }

        //访问某节点的起初节点
        visitStartNode.set(startVertex,startVertex);

        GraphTraversalVO graphTraversalVO=new GraphTraversalVO();
        graphTraversalVO.setGraph(graph);
        ArrayList<GraphTraversalStep> steps=new ArrayList<GraphTraversalStep>();
        for(int i=0;i<graph.getNodeNum();i++){
            visited.add(0);
        }
        Queue<Integer> q=new LinkedList<Integer>();
        q.add(startVertex);
        while(!q.isEmpty()){
            int curVertex=q.poll();
            steps.add(new GraphTraversalStep("visit",visitStartNode.get(curVertex),curVertex,true));
            visited.set(curVertex,1);
            visitSequence.add(curVertex);
            for(int i=0;i<graph.getNodeNum();i++){
                if(content.get(curVertex).get(i)==1){
                    //如果节点没有被访问，且没有被纳入队列当中，则tryRoad为true
                    if(visited.get(i)==0&&!q.contains(i)) {
                        steps.add(new GraphTraversalStep("tryRoad",curVertex,i,true));
                        if(visitStartNode.get(i)==-1){
                            visitStartNode.set(i,curVertex);
                        }
                        q.offer(i);
                    }else{
                        steps.add(new GraphTraversalStep("tryRoad",curVertex,i,false));
                    }
                }
            }
        }
        graphTraversalVO.setContent(steps);
        return graphTraversalVO;
    }

    //获取无向非带权图的深度优先遍历
    public GraphTraversalVO getDepthFirstTraversal(UDUWGraph graph,int startVertex){
        int nodeNum=graph.getNodeNum();
        ArrayList<ArrayList<Integer>> content=new ArrayList<ArrayList<Integer>>();
        GraphTraversalVO graphTraversalVO =new GraphTraversalVO();
        graphTraversalVO.setGraph(graph);
        ArrayList<GraphTraversalStep> steps=new ArrayList<GraphTraversalStep>();
        GraphTraversalStep currentStep=new GraphTraversalStep();

        ArrayList<Integer> visitSequence=new ArrayList<Integer>();
        ArrayList<Integer> visited=new ArrayList<Integer>();
        ArrayList<Integer> visitStartNode=new ArrayList<Integer>();

        for(int i=0;i<nodeNum;i++){
            visited.add(0);
        }
        for(int i=0;i<nodeNum;i++){
            visitStartNode.add(-1);
        }
        visitStartNode.set(startVertex,startVertex);
        Stack<Integer> stack=new Stack<Integer>();
        stack.push(startVertex);
        while(!stack.isEmpty()){
            boolean isTerminal=false;
        }
        return null;
    }
    //获取无向带权图的prim算法的最小生成树
    public PrimMinimumSpanningTree getPrimMinimumSpanningTree(UDUWGraph graph,int startVertex){
        return null;
    }


}