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=graph.getContent();
        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);
        visited.set(startVertex,1);
        visitSequence.add(startVertex);
        steps.add(new GraphTraversalStep("visit",startVertex,startVertex,true));
        boolean isTerminal=false;
        int formerNode=0;
        while(!stack.isEmpty()){
            int curVertex=stack.peek();
            int nextNode=0;
            if(visitSequence.get(visitSequence.size()-1)==curVertex) { //如果正在遍历某支路，没有折返
                isTerminal=true;
                for (int i = 0; i < nodeNum; i++) {
                    if (content.get(curVertex).get(i) == 1) {
                        if (visited.get(i) == 0) {
                            steps.add(new GraphTraversalStep("tryRoad",curVertex,i,true));
                            nextNode = i;
                            steps.add(new GraphTraversalStep("visit",curVertex,i,true));
                            visited.set(nextNode, 1);
                            visitSequence.add(nextNode);
                            stack.push(nextNode);
                            isTerminal = false;
                            break;
                        }else{
                            steps.add(new GraphTraversalStep("tryRoad",curVertex,i,false));
                        }
                    }
                }
                if(isTerminal){
                    formerNode=stack.pop();
                    steps.add(new GraphTraversalStep("return",curVertex,stack.peek(),true));
                }
            }else{ //如果在折返状态中
                if(formerNode<nodeNum-1) {
                    boolean needReturn=true;
                    for (int i = formerNode + 1; i < nodeNum; i++) {
                        if(content.get(curVertex).get(i)==1) {
                            if (visited.get(i) == 0) {
                                steps.add(new GraphTraversalStep("tryRoad",curVertex,i,true));
                                steps.add(new GraphTraversalStep("visit",curVertex,i,true));
                                stack.push(i);
                                visited.set(i, 1);
                                visitSequence.add(i);
                                needReturn = false;
                                break;
                            }else{
                                steps.add(new GraphTraversalStep("tryRoad",curVertex,i,false));
                            }
                        }
                    }
                    if(needReturn){
                        formerNode=stack.pop();
                        if(!stack.isEmpty()) {
                            steps.add(new GraphTraversalStep("return", curVertex, stack.peek(), true));
                        }
                    }
                }else{ //如果当前分支就是最大分支了，则不用探路直接折返
                    formerNode=stack.pop();
                    steps.add(new GraphTraversalStep("return",curVertex,stack.peek(),true));
                }
            }
        }
        graphTraversalVO.setContent(steps);
        return graphTraversalVO;
    }
    //获取无向带权图的prim算法的最小生成树
    public PrimMinimumSpanningTree getPrimMinimumSpanningTree(UDWGraph graph,int startVertex){
        ArrayList<ArrayList<Integer>> content=graph.getContent();
        int nodeNum=content.size();
        ArrayList<Integer> cost=new ArrayList<Integer>();
        ArrayList<Boolean> known=new ArrayList<Boolean>();
        ArrayList<Integer> startNode=new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> treeEdges=new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> knownSequence=new ArrayList<Integer>();
        ArrayList<GraphTraversalStep> steps=new ArrayList<GraphTraversalStep>();
        PrimMinimumSpanningTree primMinimumSpanningTree=new PrimMinimumSpanningTree();
        for(int i=0;i<nodeNum;i++){
            cost.add(Integer.MAX_VALUE);
            known.add(false);
            startNode.add(-1);
        }
        cost.set(startVertex,0);
        while(knownSequence.size()<nodeNum){ //还有节点没有被连接
            int min=Integer.MAX_VALUE;
            int indexOfMin=-1;
            for(int i=0;i<nodeNum;i++){
                if(known.get(i)==false){  //在没有被连接的节点中选一个代价最小的节点
                    if(cost.get(i)<min){
                        indexOfMin=i;
                        min=cost.get(i);
                    }
                }
            }
            steps.add(new GraphTraversalStep("selectMin",indexOfMin,-1,true));
            steps.add(new GraphTraversalStep("setKnown",indexOfMin,-1,true));
            known.set(indexOfMin,true); //连接这个节点，并遍历它周围的节点，若代价更小，则将代价和前驱节点替换
            knownSequence.add(indexOfMin);
            for(int i=0;i<nodeNum;i++){
                if(content.get(indexOfMin).get(i)>0){ //如果有边可以到达的话
                    steps.add(new GraphTraversalStep("tryRoad",indexOfMin,i,true));
                    if(content.get(indexOfMin).get(i)<cost.get(i)){ //如果代价更小，需要替换
                        cost.set(i,content.get(indexOfMin).get(i));
                        startNode.set(i,indexOfMin);
                    }
                }
            }

        }
        for(int i=0;i<nodeNum;i++){
            if(i!=startVertex){
                ArrayList<Integer> edge=new ArrayList<Integer>();
                edge.add(startNode.get(i));
                edge.add(i);
                treeEdges.add(edge);
            }
        }
        primMinimumSpanningTree.setSteps(steps);
        primMinimumSpanningTree.setTreeEdges(treeEdges);

        return primMinimumSpanningTree;
    }


}