【Java】图论笔记

已含dfs和bfs，相关算法正在研究

代码

import java.util.*;

public class Prim{
    public static void main(String[] args) {
        Graph graph=new Graph();
        graph.addVertex("A");
        graph.addVertex("B");
        graph.addVertex("C");
        graph.addVertex("D");
        graph.addVertex("E");

        graph.addEdge("A","B",1);
        graph.addEdge("A","E",2);
        graph.addEdge("B","C",2);
        graph.addEdge("B","F",2);
        graph.addEdge("C","D",2);
        graph.addEdge("D","F",2);
        graph.addEdge("E","F",2);

        System.out.println(graph.dfs());
        graph.addVertex("1");
        System.out.println(graph.dfs());
    }

}
class Graph{
    public Boolean isConnected(){
        List<String> visited=new ArrayList<>();
        for(String v1:vertexs.keySet()){
            visited.add(v1);
            dfs(v1,visited);
            break;
        }

        return visited.size()==vertexs.size();
    }
    public void prim(){
        List<String> list=new ArrayList();
        putFirst(list);
        int size=vertexs.size();
        for(int i=1;i<size;i++){
            int min=Integer.MAX_VALUE;
            String next=null;
            for(String key:list){
                Map<String,Integer>neighbors=vertexs.get(key);
                for(Map.Entry<String,Integer> nbsentry:neighbors.entrySet()){
                    if(!list.contains(nbsentry.getKey())){
                        if(nbsentry.getValue()<min){
                            min= nbsentry.getValue();
                            next=nbsentry.getKey();
                        }
                    }
                }
            }
            if(next!=null){
                list.add(next);
            }

        }
        System.out.println(list);
    }
    public void putFirst(List<String> list){
        for(Map.Entry<String,Map<String,Integer>>entry:vertexs.entrySet()){
            String key=entry.getKey();
            Map<String,Integer> value=entry.getValue();
            list.add(key);
            break;
        }
    }
    private Map<String,Map<String,Integer>>vertexs;
    public Graph(){
        vertexs=new HashMap<>();
    }
    public void addVertex(String v1){
        if(!vertexs.containsKey(v1)){
            vertexs.put(v1,new HashMap<>());
        }
    }
    public void addEdge(String v1,String v2,int weight){
        if(!vertexs.containsKey(v1)){
            vertexs.put(v1,new HashMap<>());
        }
        vertexs.get(v1).put(v2,weight);
        if(!vertexs.containsKey(v2)){
            vertexs.put(v2,new HashMap<>());
        }
        vertexs.get(v2).put(v1,weight);
    }
    public Map<String,Integer> getNeighbors(String v1){
        return vertexs.get(v1);
    }
    public static void my_traverseNeighbors(Map<String, Integer> neighbors) {
        for (Map.Entry<String, Integer> entry : neighbors.entrySet()) {
            String vertex = entry.getKey();
            Integer weight = entry.getValue();
            System.out.println("顶点: " + vertex + ", 权重: " + weight);
        }
    }
    public void bfs(){
        List<String> visited=new ArrayList<>();
        for(String v1:vertexs.keySet()){
            bfs(v1,visited);
        }
        System.out.println("null");
    }

    private void bfs(String v1,List visited) {
        if(!visited.contains(v1)){
            System.out.print(v1+"->");
            visited.add(v1);
        }
        Map<String,Integer> map=vertexs.get(v1);
        for(Map.Entry<String,Integer>entry:map.entrySet()){
            String v2 = entry.getKey();
            if(!visited.contains(v2)){
                System.out.print(v2+"->");
                visited.add(v2);
            }
        }
    }

    public List dfs(){
        List<String> visited=new ArrayList<>();
        for(String v1:vertexs.keySet()){
            if(!visited.contains(v1)){
                visited.add(v1);
                dfs(v1,visited);
            }

        }
        return visited;
    }

    private List dfs(String v1, List<String> visited) {

        Map<String,Integer> map =vertexs.get(v1);
        for(Map.Entry<String,Integer>entry:map.entrySet()){
            String key=entry.getKey();
            if(!visited.contains(key)){
                visited.add(key);
                dfs(key,visited);
            }
        }
        return visited;
    }
}