图的BFS & DFS & Dijkstra算法

图.PNG

python 队列实现的图的BFS，类似于哈夫曼树遍历:

BFS.PNG

栈实现的图的DFS：

DFS.PNG

BFS扩展最短路径：

parent.PNG

Dijkstra（加权最短路径计算）：

dijkstra 推导.PNG
dijkstra.PNG 初始化.PNG
Dijkstra.PNG

写了个java版，比起js和python这种基于对象而不是oo语言，有点啰嗦：

import java.util.*;

/**
 * @author jajing
 */
public class Dijkstra {


    private static class Node implements Comparable<Node>{
        String name;
        Integer distance;
        Node(String name,Integer distance){
            this.name = name;
            this.distance = distance;
        }

        @Override
        public int compareTo(Node o) {
            //正序
            return this.distance - o.distance;
        }
    }

    //图的两点间最短路径
    public static void main(String[] args) {
        Map<String,Map<String,Integer>> map = new HashMap<String,Map<String,Integer>>();
        Map mA = new HashMap();mA.put("B",5);mA.put("C",1);
        Map mB = new HashMap();mB.put("A",5);mB.put("C",2);mB.put("D",1);
        Map mC = new HashMap();mC.put("A",1);mC.put("B",2);mC.put("D",4);mC.put("E",8);
        Map mD = new HashMap();mD.put("B",1);mD.put("C",4);mD.put("E",3);mD.put("F",6);
        Map mE = new HashMap();mE.put("C",8);mE.put("D",3);
        Map mF = new HashMap();mF.put("D",6);
        map.put("A",mA);
        map.put("B",mB);
        map.put("C",mC);
        map.put("D",mD);
        map.put("E",mE);
        map.put("F",mF);
        Map<String,Integer>  result =  dijkstra(map,"A");
        for(Map.Entry<String,Integer> e:result.entrySet()){
            System.out.println(e.getKey() + ":" + e.getValue());
            /**
             * A:0
             * B:3
             * C:1
             * D:4
             * E:7
             * F:10
             */
        }

    }

    public static Map<String,Integer> initDistance(Map<String,Map<String,Integer>> map,String start){
        Map<String,Integer> distance = new HashMap<String, Integer>();
        for(String key:map.keySet()){
            distance.put(key,Integer.MAX_VALUE);
        }
        return distance;
    }

    public static Map<String,Integer>  dijkstra(Map<String,Map<String,Integer>> map,String start){
        //最短距离表，初始都最大化
        Map<String,Integer> minDistance = initDistance(map,start);
        Set<String> seen = new HashSet<String>();
        //最短路径的父结点
        Map<String,String> parent = new HashMap<String, String>();

        PriorityQueue<Node> pQueue = new PriorityQueue<Node>();

        pQueue.offer(new Node(start,0));
        parent.put(start,"Null");
        minDistance.put(start,0);

        while(!pQueue.isEmpty()){
            Node current = pQueue.poll();
            //一定要在取出时才放到seen去！！
            seen.add(start);
            String currentName = current.name;
            Integer currentDist = current.distance;
            
            Map<String,Integer> connects = map.get(currentName);
            for(Map.Entry<String,Integer> entry : connects.entrySet()){
                String nextKey = entry.getKey();
                Integer nextValue = entry.getValue();

                if(seen.contains(nextKey)) continue;

                Integer newDistance = currentDist + nextValue;
                if(newDistance < minDistance.get(nextKey)){
                    parent.put(nextKey,currentName);
                    minDistance.put(nextKey,newDistance);
                    pQueue.offer(new Node(nextKey,newDistance));
                }
            }
        }
        return minDistance;

    }
}

这里要感谢@正月点灯笼的课件