3

  package com.fredal.structure;

import java.util.ArrayList;

public class MyGraphy {

    private ArrayList vList;//用来存节点
    private int[][] edges;//邻接矩阵 用来存储边
    private int numOfEdges;//边的条数
    
    public MyGraphy(int n){
        //初始化矩阵
        edges=new int[n][n];
        vList=new ArrayList(n);
        numOfEdges=0;
    }
    
    public int[][] getEdges() {
        return edges;
    }
    
    //得到节点个数
    public int getNumOfVertex(){
        return vList.size();
    }
    
    //得到边的个数
    public int getNumOfEdges(){
        return numOfEdges;
    }
    
    //返回节点i的值
    public Object get(int i){
        return vList.get(i);
    }
    
    //返回v1,v2节点之间边的权值
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }
    
    //插入节点
    public void insertVertext(Object vertex){
        vList.add(vList.size(),vertex);
        edges=new int[vList.size()][vList.size()];
    }
    
    //插入边
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2]=weight;
        numOfEdges++;
    }
    
    //删除节点
    public void deleteVertex(int v){
        vList.remove(v);
        for(int i=0;i<vList.size();i++){
            edges[v][i]=0;
            numOfEdges--;
        }
    }
    
    //删除边
    public void deleteEdge(int v1,int v2){
        edges[v1][v2]=0;
        numOfEdges--;
    }
    
    //得到第一个邻接节点的下标
    public int getFirstneighbor(int i){
        for(int j=0;j<vList.size();j++){
            if(edges[i][j]>0){
                return j;
            }
        }
        return -1;
    }
    
    //根据前一个邻接节点的下标来取得下一个邻接节点
    public int getNextNeighbor(int v1,int v2){
        for(int j=v2+1;j<vList.size();j++){
            if(edges[v1][j]>0){
                return j;
            }
        }
        return -1;
    }
    
    //测试程序
    public static void main(String[] args) {
        String labels[]={"V1","V2","V3","V4"};//结点的标识
        MyGraphy g=new MyGraphy(4);
        for(String label:labels) {
            g.insertVertext(label);//插入结点
        }
        
        g.insertEdge(0, 1, 2);
        g.insertEdge(0, 2, 5);
        g.insertEdge(2, 3, 8);
        g.insertEdge(3, 0, 7);
        
        System.out.println("结点个数是："+g.getNumOfVertex());
        System.out.println("边的个数是："+g.getNumOfEdges());

        g.deleteEdge(0, 1);//删除<V1,V2>边
        System.out.println("删除<V1,V2>边后...");
        System.out.println("结点个数是："+g.getNumOfVertex());
        System.out.println("边的个数是："+g.getNumOfEdges());
    }
    
}

接下来我们用邻接表来实现图的存储,同样是前面那张图

  package com.fredal.structure;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

import com.fredal.structure.MyGraphyL.Node;
import com.fredal.structure.MyGraphyL.Vertex;

public class MyGraphyL {

    class Vertex{
        private Object value;//顶点的名称
        private int vvalue;//定点的额值
        public LinkedList<Node> elist;//链表 用来存放边的信息
        
        public Vertex(Object value,int vvalue){
            this.value=value;
            this.vvalue=vvalue;
            elist=new LinkedList<Node>();
        }
    }
    
    class Node{
        private int evalue;//边的节点的值
        private int weight;//权重
        
        public Node(int evalue,int weight){
            this.evalue=evalue;
            this.weight=weight;
        }
        public int getEvalue() {
            return evalue;
        }

        public int getWeight() {
            return weight;
        }
        
    }

    private List<Vertex> vertexs;//存储节点
    private int numOfEdges;//边的条数
    
    public MyGraphyL(int n){
        //初始化邻接表
        vertexs=new ArrayList<Vertex>(n);
        numOfEdges=0;
    }
    
    public List<Vertex> getVertexs() {
        return vertexs;
    }
    
    //得到节点个数
    public int getNumOfVertex(){
        return vertexs.size();
    }
    
    //得到边的个数
    public int getNumOfEdges(){
        return numOfEdges;
    }
    
    //返回节点i的值
    public Object get(int i){
        Vertex vertex = vertexs.get(i);
        if(vertex!=null){
            return vertex.value;
        }
        return null;
    }
    
    //返回v1,v2节点之间边的权值
    public int getWeight(int v1,int v2){
        Node search = search(v1, v2);
        if(search!=null) return search.weight;
        else return -1;
    }
    
    //搜索边节点
    public Node search(int v1,int v2){
        Iterator<Node> it = vertexs.get(v1).elist.iterator();
        while(it.hasNext()){
            Node node = (Node) it.next();
            if(node.evalue==v2){
                return node;
            }    
        }
        return null;
    }
    
    //插入节点
    public void insertVertext(Object value,int vvalue){
        Vertex vertex=new Vertex(value,vvalue);
        vertexs.add(vertex);        
    }
    
    //插入边节点
    public void insertEdge(int v1,int v2,int weight){
        LinkedList<Node> elist = vertexs.get(v1).elist;
        Node node = new Node(v2, weight);
        elist.add(node);
        numOfEdges++;
    }
    
    //删除节点
    public void deleteVertex(int vvalue){
        vertexs.remove(vvalue);
    }
    
    //删除边节点
    public void deleteEdge(int v1,int v2){
        LinkedList<Node> elist = vertexs.get(v1).elist;
        Node search = search(v1, v2);
        if(search!=null) elist.remove(search);
        numOfEdges--;
    }
    
    //得到节点的第一个边节点的下标
    public int getFirstneighbor(int i){
        LinkedList<Node> elist = vertexs.get(i).elist;
        if(elist.size()==0) return -1;
        Node node =  elist.get(0);
        if(node!=null)
        return node.evalue;
        return -1;
    }
    
    //根据前一个边节点的下标来取得下一个边节点
    public int getNextNeighbor(int v1,int v2){
        LinkedList<Node> elist = vertexs.get(v1).elist;
        Iterator<Node> iterator = elist.iterator();
        while(iterator.hasNext()){
            Node next = iterator.next();
            if (next.evalue==v2) {
                try {
                    return iterator.next().evalue;
                } catch (Exception e) {
                    System.out.println("没有下一个");
                }
            }
        }
        
        return -1;
    }
    
    //测试程序
     public static void main(String args[]) {
             int i=0;
            int n=4,e=4;//分别代表结点个数和边的数目
            String labels[]={"V1","V2","V3","V4"};//结点的标识
            MyGraphyL graph=new MyGraphyL(n);
            for(String label:labels) {
                graph.insertVertext(label, i);//插入结点
                i++;
            }
            //插入四条边
            graph.insertEdge(0, 1, 2);
            graph.insertEdge(0, 2, 5);
            graph.insertEdge(2, 3, 8);
            graph.insertEdge(3, 0, 7);

            System.out.println("结点个数是："+graph.getNumOfVertex());
            System.out.println("边的个数是："+graph.getNumOfEdges());

//            graph.deleteEdge(0, 1);//删除<V1,V2>边
//            System.out.println("删除<V1,V2>边后...");
//            System.out.println("结点个数是："+graph.getNumOfVertex());
//            System.out.println("边的个数是："+graph.getNumOfEdges());
            System.out.println(graph.getFirstneighbor(0));
            System.out.println(graph.getNextNeighbor(0, 1));
            System.out.println("---------------------");
            List<Vertex> vlist = graph.vertexs;
            for(Vertex v:vlist){
                System.out.println(v.value+" "+v.vvalue+":");
                LinkedList<Node> elist = v.elist;
                for (Node node : elist) {
                    System.out.println("  "+node.evalue+"--"+node.weight);
                }
            }
        }
    
}

深度优先遍历与广度优先遍历

• 深度优先遍历

所谓深度优先遍历,就是首先访问第一个邻接结 点，然后再以这个被访问的邻接结点作为初始结点，访问它 的第一个邻接结点。总结起来可以这样说：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
如下图,深度优先遍历的顺序为1->2->4->8->5->3->6->7

4

我们先用邻接矩阵的形式实现上图的深度优先遍历,图结构采用上面自己写的

 package com.fredal.structure;
public class DeepTravel {
   
   //深度优先遍历 参数为要遍历的图,访问过的标记以及从哪开始遍历
   public static void deepTravel(MyGraphy a,boolean [] visited,int k){
       int[][] edges = a.getEdges();
       
       visited[k]=true;
       
       System.out.println(a.get(k));
       for(int i=0;i<edges[k].length;i++){
           if(edges[k][i]==1&&visited[i]==false) deepTravel(a, visited, i);
       }
   }
   
   public static void main(String[] args) {
       String labels[]={"1","2","3","4","5","6","7","8"};//结点的标识
       MyGraphy a=new MyGraphy(8);
       for(String label:labels){
           a.insertVertext(label);
       }
       a.insertEdge(0, 1, 1);
       a.insertEdge(0, 2, 1);
       a.insertEdge(1, 3, 1);
       a.insertEdge(1, 4, 1);
       a.insertEdge(3, 7, 1);
       a.insertEdge(4, 7, 1);
       a.insertEdge(2, 5, 1);
       a.insertEdge(2, 6, 1);
       a.insertEdge(5, 6, 1);
       a.insertEdge(1, 0, 1);
       a.insertEdge(2, 0, 1);
       a.insertEdge(3, 1, 1);
       a.insertEdge(4, 1, 1);
       a.insertEdge(7, 3, 1);
       a.insertEdge(7, 4, 1);
       a.insertEdge(4, 2, 1);
       a.insertEdge(5, 2, 1);
       a.insertEdge(6, 5, 1);
       
       boolean [] visited=new boolean[a.getNumOfVertex()];
       deepTravel(a, visited, 0);
   }
}

用邻接表实现深度优先遍历并没有多大区别:

public class DeepTravel {
  public static void deepTravelL(MyGraphyL a,boolean [] visited,int k){
       List<Vertex> vertexs = a.getVertexs();
       
       visited[k]=true;
       
       System.out.println(a.get(k));
       LinkedList<Node> elist = vertexs.get(k).elist;
       Iterator<Node> iterator = elist.iterator();
       while(iterator.hasNext()){
           Node node = iterator.next();
           if(visited[node.getEvalue()]==false) deepTravelL(a, visited, node.getEvalue());
       }
   }
   
   public static void main(String[] args) {
       String labels[]={"1","2","3","4","5","6","7","8"};//结点的标识
       MyGraphyL a=new MyGraphyL(8);
       int i=0;
       for(String label:labels) {
           a.insertVertext(label, i);//插入结点
           i++;
       }
       a.insertEdge(0, 1, 1);
       a.insertEdge(0, 2, 1);
       a.insertEdge(1, 3, 1);
       a.insertEdge(1, 4, 1);
       a.insertEdge(3, 7, 1);
       a.insertEdge(4, 7, 1);
       a.insertEdge(2, 5, 1);
       a.insertEdge(2, 6, 1);
       a.insertEdge(5, 6, 1);
       a.insertEdge(1, 0, 1);
       a.insertEdge(2, 0, 1);
       a.insertEdge(3, 1, 1);
       a.insertEdge(4, 1, 1);
       a.insertEdge(7, 3, 1);
       a.insertEdge(7, 4, 1);
       a.insertEdge(4, 2, 1);
       a.insertEdge(5, 2, 1);
       a.insertEdge(6, 5, 1);
       
       boolean [] visited=new boolean[a.getNumOfVertex()];
       deepTravelL(a, visited, 0);
   }
}

• 广度优先遍历

广度优先遍历(BFS)从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。
上图按广度优先遍历的顺序应为:1->2->3->4->5->6->7->8
同样采用上面的图先使用邻接矩阵进行模拟

  package com.fredal.structure;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class WidthTravel {

   public static void widthTravel(MyGraphy a,Set visited,List layer){
       int[][] edges = a.getEdges();

       //遍历当前层
       for(int i=0;i<layer.size();i++){
           System.out.println(a.get((Integer) layer.get(i)));
           visited.add(layer.get(i));
       }
       
       //下一层
       List next_layer=new ArrayList();
       for(int i=0;i<layer.size();i++){
           int node=(Integer) layer.get(i);
           for(int j=0;j<edges[node].length;j++){
               if(edges[node][j]==1&&next_layer.indexOf(j)<0) next_layer.add(j);
           }
       }
       next_layer.removeAll(visited);
       
       if(next_layer.isEmpty()==false) widthTravel(a, visited, next_layer);
   }
   
   public static void main(String[] args) {
       String labels[]={"1","2","3","4","5","6","7","8"};//结点的标识
       MyGraphy a=new MyGraphy(8);
       for(String label:labels){
           a.insertVertext(label);
       }
       a.insertEdge(0, 1, 1);
       a.insertEdge(0, 2, 1);
       a.insertEdge(1, 3, 1);
       a.insertEdge(1, 4, 1);
       a.insertEdge(3, 7, 1);
       a.insertEdge(4, 7, 1);
       a.insertEdge(2, 5, 1);
       a.insertEdge(2, 6, 1);
       a.insertEdge(5, 6, 1);
       a.insertEdge(1, 0, 1);
       a.insertEdge(2, 0, 1);
       a.insertEdge(3, 1, 1);
       a.insertEdge(4, 1, 1);
       a.insertEdge(7, 3, 1);
       a.insertEdge(7, 4, 1);
       a.insertEdge(4, 2, 1);
       a.insertEdge(5, 2, 1);
       a.insertEdge(6, 5, 1);
       
       Set visited=new HashSet();
       List layer=new ArrayList();
       layer.add(0);
       widthTravel(a, visited, layer);
   }
}

用邻接表实现广度遍历基本没区别

public class WidthTravel {
  public static void widthTravelL(MyGraphyL a,Set visited,List layer){
       List<Vertex> vertexs = a.getVertexs();

       //遍历当前层
       for(int i=0;i<layer.size();i++){
           System.out.println(a.get((Integer) layer.get(i)));
           visited.add(layer.get(i));
       }
       
       //下一层
       List next_layer=new ArrayList();
       for(int i=0;i<layer.size();i++){
           int node=(Integer) layer.get(i);
           LinkedList<Node> elist = vertexs.get(node).elist;
           Iterator<Node> iterator = elist.iterator();
           while(iterator.hasNext()){
               Node next = iterator.next();
               if(next_layer.indexOf(next.getEvalue())<0) next_layer.add(next.getEvalue());
           }
       }
       next_layer.removeAll(visited);
       
       if(next_layer.isEmpty()==false) widthTravelL(a, visited, next_layer);
   }
   
   public static void main(String[] args) {
       String labels[]={"1","2","3","4","5","6","7","8"};//结点的标识
       MyGraphyL a=new MyGraphyL(8);
       int i=0;
       for(String label:labels) {
           a.insertVertext(label, i);//插入结点
           i++;
       }
       a.insertEdge(0, 1, 1);
       a.insertEdge(0, 2, 1);
       a.insertEdge(1, 3, 1);
       a.insertEdge(1, 4, 1);
       a.insertEdge(3, 7, 1);
       a.insertEdge(4, 7, 1);
       a.insertEdge(2, 5, 1);
       a.insertEdge(2, 6, 1);
       a.insertEdge(5, 6, 1);
       a.insertEdge(1, 0, 1);
       a.insertEdge(2, 0, 1);
       a.insertEdge(3, 1, 1);
       a.insertEdge(4, 1, 1);
       a.insertEdge(7, 3, 1);
       a.insertEdge(7, 4, 1);
       a.insertEdge(4, 2, 1);
       a.insertEdge(5, 2, 1);
       a.insertEdge(6, 5, 1);
       
       Set visited=new HashSet();
       List layer=new ArrayList();
       layer.add(0);
       widthTravelL(a, visited, layer);
   }
}

拓扑排序(kahn&DFS)

关于拓扑排序,是一种对于关联性的排序,可以参考维基百科的解释:
在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（Topological sorting）。
a. 每个顶点出现且只出现一次；
b. 若A在序列中排在B的前面，则在图中不存在从B到A的路径。
也可以定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中B出现在A的后面
我们根据下图进行排序

5

首先来最简单的和自然的kahn算法,得出的结果应该是1->5->2->4->6->7->3,基于邻接表

  package com.fredal.structure;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import com.fredal.structure.MyGraphyL.Node;
import com.sun.xml.internal.messaging.saaj.packaging.mime.util.QEncoderStream;
public class TopSort {
    public static void topSort(MyGraphyL a){
        int[] ins;//入度数组
        int [] tops;//拓扑排序的结果数组
        Queue<Integer> queue;//辅助队列
        int num=a.getNumOfVertex();//顶点个数
        int index=0;

        ins=new int[num];
        tops=new int[num];
        queue=new LinkedList<Integer>();
        
        //统计每个顶点的入度数
        for(int i=0;i<num;i++){
            LinkedList<Node> elist = a.getVertexs().get(i).elist;
            Iterator<Node> iterator = elist.iterator();
            while(iterator.hasNext()){
                ins[iterator.next().getEvalue()]++;
            }
        }
        //将入度为0的顶点入队列
        for(int i=0;i<num;i++){
            if(ins[i]==0) queue.offer(i);//入队列
        }
        while(!queue.isEmpty()){
            int j=queue.poll().intValue();//出队列 j是顶点序号            tops[index++]=Integer.parseInt((String) a.get(j));
            LinkedList<Node> elist = a.getVertexs().get(j).elist;
            Iterator<Node> iterator = elist.iterator();
            while(iterator.hasNext()){
                Node node = iterator.next();
                ins[node.getEvalue()]--;//将入度减一
                if(ins[node.getEvalue()]==0) queue.offer(node.getEvalue());
            }
        }
        if(index!=num){
            System.out.println("有个环");
            return;
        }
        //输出排序结果
        System.out.print("拓扑排序: ");
        for(int i=0;i<num;i++){
            System.out.print(tops[i]+" ");
        }
    }
    public static void main(String[] args) {
        String labels[]={"1","2","3","4","5","6","7"};//结点的标识
        MyGraphyL a=new MyGraphyL(8);
        int i=0;
        for(String label:labels) {
            a.insertVertext(label, i);//插入结点
            i++;
        }
        a.insertEdge(0, 1, 1);
        a.insertEdge(0, 3, 1);
        a.insertEdge(0, 5, 1);
        a.insertEdge(1, 6, 1);
        a.insertEdge(3, 2, 1);
        a.insertEdge(4, 6, 1);
        a.insertEdge(5, 6, 1);
        a.insertEdge(6, 2, 1);
        
        topSort(a);
    }
    
}

除了上面那种算法我们还可以基于深度优先遍历(DFS)进行拓扑排序,同样基于邻接表,首先保证图是有向无环图

  package com.fredal.structure;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
import com.fredal.structure.MyGraphyL.Node;
import com.fredal.structure.MyGraphyL.Vertex;
public class TopSort {
    static boolean [] visited;
    private static Stack<Integer> stack=new Stack<Integer>();
    
    public static void topSortDFS(MyGraphyL a){
         int num=a.getNumOfVertex();
         visited=new boolean[num];
         for(int i=0;i<num;i++){//循环调用DFS
             if(!visited[i]) DFS(a, i);
         }
    }
    
    private static void DFS(MyGraphyL a,int k){
        visited[k]=true;
        List<Vertex> vertexs = a.getVertexs();
        LinkedList<Node> elist = vertexs.get(k).elist;
        Iterator<Node> iterator = elist.iterator();
        while(iterator.hasNext()){
            Node node = iterator.next();
            if(!visited[node.getEvalue()]) {
                DFS(a, node.getEvalue());
            }    
        }
        stack.push(Integer.parseInt((String) a.get(k)));//在dfs方法快结束时压入栈中
    }
    
    
    public static void main(String[] args) {
        String labels[]={"1","2","3","4","5","6","7"};//结点的标识
        MyGraphyL a=new MyGraphyL(8);
        int i=0;
        for(String label:labels) {
            a.insertVertext(label, i);//插入结点
            i++;
        }
        
        a.insertEdge(0, 1, 1);
        a.insertEdge(0, 3, 1);
        a.insertEdge(0, 5, 1);
        a.insertEdge(1, 6, 1);
        a.insertEdge(3, 2, 1);
        a.insertEdge(4, 6, 1);
        a.insertEdge(5, 6, 1);
        a.insertEdge(6, 2, 1);
        
        topSortDFS(a);
        while(!stack.isEmpty()){
            System.out.println(stack.pop());
        }
    }
    
}

这种算法得出得到排序结果为5->1->6->4->2->7->3,与上面的有些区别,但是仍然是对的排序结果.
这有关到解的唯一性问题,有哈密顿路径的图,即每一对顶点都能确定向后关系的图的解是唯一的.
至于如何确定有唯一解呢,最简单的想法是把每一对顶点两两比较看看有无先后关系,但是这样很低效,我们可以用类似插入排序的算法进行判断.详细的以后再讲.

最短路径问题(Dijkstra&Floyd)

最短路径问题,先讲单源最短路径,就是求从指定顶点出发到其他各点的最短距离.经典的算法有(Dijkstra)算法.
我们根据下图来模拟该算法:

6

  public class Dijstra {

    public static void dijstra(MyGraphyL a,int k){
        Map map=new HashMap();//存储节点号--最小路径值
        List<Vertex> vertexs = a.getVertexs();
        while(true){
            int min=Integer.MAX_VALUE;
            int min_no=-1;
            Vertex first = vertexs.get(k);//获得初始节点
            
            Iterator<Node> iterator = first.elist.iterator();
            while(iterator.hasNext()){
                Node node = iterator.next();
                //选出路径最短的节点
                if(map.get(node.getEvalue())==null&&node.getWeight()<min){
                    min_no=node.getEvalue();
                    min=node.getWeight();
                }
            }
            
            Iterator it = map.keySet().iterator();
            while(it.hasNext()){
                //取出集合中存在的最短路径节点
                int index=(Integer) it.next();
                int weight=(Integer) map.get(index);
                
                Iterator<Node> iterator2 = vertexs.get(index).elist.iterator();
                while(iterator2.hasNext()){
                    Node node2 = iterator2.next();
                    //将集合中的节点自身的权值加上下一个节点的权值与外面非集合中的权值比较 取最小值 循环
                    if(map.get(node2.getEvalue())==null&&node2.getWeight()+weight<min){
                        min_no=node2.getEvalue();
                        min=node2.getWeight()+weight;
                    }
                }
            }
            //出口
            if(min<Integer.MAX_VALUE)
                map.put(min_no, min);
            else
                break;
        }
        
        System.out.println(map);
    }
    
    public static void main(String[] args) {
        String labels[]={"0","1","2","3","4"};//结点的标识
        MyGraphyL a=new MyGraphyL(5);
        int i=0;
        for(String label:labels) {
            a.insertVertext(label, i);//插入结点
            i++;
        }
        a.insertEdge(0, 1, 10);
        a.insertEdge(0, 3, 30);
        a.insertEdge(0, 4, 100);
        a.insertEdge(1, 2, 50);
        a.insertEdge(2, 4, 10);
        a.insertEdge(3, 2, 20);
        a.insertEdge(3, 4, 60);

        dijstra(a, 0);
    }
}

模拟结果为:

从0出发到1的最短路径为：0-->1
从0出发到2的最短路径为：0-->3-->2
从0出发到3的最短路径为：0-->3
从0出发到4的最短路径为：0-->3-->2-->4
从0出 发到1的最短距离为：10
从0出 发到2的最短距离为：50
从0出 发到3的最短距离为：30
从0出 发到4的最短距离为：60

对于最短路径问题,还有著名的算法,Floyd算法,比起单源,它对于任意两点间的最短路径问题计算更方便.
通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入一个矩阵S，矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。
基本思想:
假设图G中顶点个数为N，则需要对矩阵S进行N次更新。初始时，矩阵S中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞。 接下来开始，对矩阵S进行N次更新。第1次更新时，如果"a[i][j]的距离" > "a[i][0]+a[0][j]"(a[i][0]+a[0][j]表示"i与j之间经过第1个顶点的距离")，则更新a[i][j]为"a[i][0]+a[0][j]"。 同理，第k次更新时，如果"a[i][j]的距离" > "a[i][k]+a[k][j]"，则更新a[i][j]为"a[i][k]+a[k][j]"。更新N次之后，操作完成！
我们还是用代码模拟更易于理解,同样采用上面那张图,基于邻接矩阵:

  package com.fredal.structure;
import java.util.ArrayList;
import java.util.List;
public class Floyd {
    // path[i][j]=k表示 顶点i到顶点j的最短路径经过k
    // dis[i][j]=s表示 顶点i到顶点j的最短路径长度为s
    public static void floyd(MyGraphy a) {
        int num = a.getNumOfVertex();
        int[][] edges = a.getEdges();
        int INF = Integer.MAX_VALUE;
        int[][] dis = new int[num][num];
        List[][] path = new List[num][num];//用list来存储具体的路径
        // 初始化
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                dis[i][j] = ((edges[i][j] == 0) ? INF : edges[i][j]);//用inf表示没有通路
                if (path[i][j] == null) {
                    path[i][j] = new ArrayList();
                    path[i][j].add(j);
                }
            }
        }

            // 计算最短路径
            for (int k = 0; k < num; k++) {
                for (int i = 0; i < num; i++) {
                    for (int j = 0; j < num; j++) {
                        // 如果经过下标为k的顶点路径比原来两点间的路径更短,则更新dis[i][j]和path[i][j]
                        int tmp = (dis[i][k] == INF || dis[k][j] == INF) ? INF
                                : (dis[i][k] + dis[k][j]);
                        if (dis[i][j] > tmp) {
                            dis[i][j] = tmp;//更新路径长度
                            //更新路径 用list存储
                            List list = new ArrayList();
                            list.addAll(path[i][k]);
                            list.addAll(path[k][j]);
                            path[i][j]=list;
                        }
                    }
                }
            }

            //输出路径长度和具体的最短路径
            System.out.println("floyd:");
            for (int i = 0; i < num; i++) {
                for (int j = 0; j < num; j++) {
                    System.out.print((dis[i][j]==INF?0:dis[i][j]) + " ");//INF太难看了 我还是换回0表示没有通路
                }
                System.out.println();
            }
            System.out.println("path:");
            for (int i = 0; i < num; i++) {
                for (int j = 0; j < num; j++) {
                    System.out.print(path[i][j] + " ");
                }
                System.out.println();
            }
    }
    

    public static void main(String[] args) {
        String labels[] = { "0", "1", "2", "3", "4" };// 结点的标识
        MyGraphy a = new MyGraphy(5);
        for (String label : labels) {
            a.insertVertext(label);// 插入结点
        }
        a.insertEdge(0, 1, 10);
        a.insertEdge(0, 3, 30);
        a.insertEdge(0, 4, 100);
        a.insertEdge(1, 2, 50);
        a.insertEdge(2, 4, 10);
        a.insertEdge(3, 2, 20);
        a.insertEdge(3, 4, 60);

        floyd(a);
    }
}

运行结果为:

7

最小生成树(Prim&Kruskal)

最小生成树问题,在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。
普里姆(Prim)算法，是用来求加权连通图的最小生成树的算法。
基本思想为从一个起点开始,选取连接这个点的所有边中权值最小的那条边,然后把边的终点当成新的起点,继续选取权值最小的边,直到把所有顶点都选了一遍..

8

对于上图而言,采用Prim算法生成最小生成树的步骤为:
初始状态：V是所有顶点的集合，即V={A,B,C,D,E,F,G}；U和T都是空！
第1步：将顶点A加入到U中。
此时，U={A}。
第2步：将顶点B加入到U中。
上一步操作之后，U={A}, V-U={B,C,D,E,F,G}；因此，边(A,B)的权值最小。将顶点B添加到U中；此时，U={A,B}。
第3步：将顶点F加入到U中。
上一步操作之后，U={A,B}, V-U={C,D,E,F,G}；因此，边(B,F)的权值最小。将顶点F添加到U中；此时，U={A,B,F}。
第4步：将顶点E加入到U中。
上一步操作之后，U={A,B,F}, V-U={C,D,E,G}；因此，边(F,E)的权值最小。将顶点E添加到U中；此时，U={A,B,F,E}。
第5步：将顶点D加入到U中。
上一步操作之后，U={A,B,F,E}, V-U={C,D,G}；因此，边(E,D)的权值最小。将顶点D添加到U中；此时，U={A,B,F,E,D}。
第6步：将顶点C加入到U中。
上一步操作之后，U={A,B,F,E,D}, V-U={C,G}；因此，边(D,C)的权值最小。将顶点C添加到U中；此时，U={A,B,F,E,D,C}。
第7步：将顶点G加入到U中。
上一步操作之后，U={A,B,F,E,D,C}, V-U={G}；因此，边(G,E)的权值最小。将顶点G添加到U中；此时，U=V。

此时，最小生成树构造完成！它包括的顶点依次是：A B F E D C G,权值为36。
我们采用代码模拟该步骤,基于邻接矩阵:
首先我们要在之前写的MyGraohy类中加一个方法

  //返回顶点在的位置
    public int getPosition(Object v){
        return vList.indexOf(v);
    }

开始模拟Prim算法

  package com.fredal.structure;

public class Prim {

    public static void prim(MyGraphy a,int start){
        int num=a.getNumOfVertex();//顶点个数
        int[][] edges = a.getEdges();
        int index=0;//数组的索引
        String[] prims=new String[num];//结果数组
        int[] weight=new int[num];//顶点边的权值
        int INF=Integer.MAX_VALUE;
        //把0变成INF
        for(int i=0;i<num;i++){
            for(int j=0;j<num;j++){
                edges[i][j]=(edges[i][j]==0?INF:edges[i][j]);
            }
        }
        
        //prim树中第一个数是"图中第start个顶点"
        prims[index++]= (String) a.get(start);
    
        //将每个顶点的权值初始化为"第start个顶点"到"该定点"的权值
        for(int i=0;i<num;i++) 
            weight[i]=edges[start][i];
        //到自身的距离为0
        weight[start]=0;
            
        for(int i=0;i<num;i++){
            if(start==i) continue;
            
            int j=0;
            int k=0;
            int min=Integer.MAX_VALUE;
            while(j<num){
                //找到权值最小的顶点
                if(weight[j]!=0&&weight[j]<min){
                    min =weight[j];
                    k=j;
                }
                j++;
            }
            
            //经过上面的处理 权值最小的顶点是第k个顶点,将第k个顶点加入到最小生成树的结果数组中
            prims[index++]=(String) a.get(k);
            //将第k个节点的权值标记为0 意味着第k个顶点已经排序了
            weight[k]=0;
            //更新下一轮节点的权值
            for(j=0;j<num;j++){
                if(weight[j]!=0&&edges[k][j]<weight[j]){
                    weight[j]=edges[k][j];
                }
            }
        }
            
        //计算最小生成树的权值
        int sum=0;
        for(int i=1;i<index;i++){
            int min=Integer.MAX_VALUE;
            int n=a.getPosition(prims[i]);
            for(int j=0;j<i;j++){
                int m=a.getPosition(prims[j]);
                if(edges[m][n]<min) min=edges[m][n];
            }
            sum+=min;
        }
        
        //打印最小生成树
        System.out.println("prim:");
        System.out.println("sum:"+sum);
        System.out.println("path:");
            for(int i=0;i<index;i++){
                System.out.print(prims[i]+" ");
            }
    }
    
    public static void main(String[] args) {
        String labels[]={"A","B","C","D","E","F","G"};//结点的标识
        MyGraphy g=new MyGraphy(7);
        for(String label:labels) {
            g.insertVertext(label);//插入结点
        }
        
        g.insertEdge(0, 1, 12);
        g.insertEdge(0, 5, 16);
        g.insertEdge(0, 6, 14);
        g.insertEdge(1, 0, 12);
        g.insertEdge(1, 2, 10);
        g.insertEdge(1, 5, 7);
        g.insertEdge(2, 1, 10);
        g.insertEdge(2, 3, 3);
        g.insertEdge(2, 4, 5);
        g.insertEdge(2, 5, 6);
        g.insertEdge(3, 2, 3);
        g.insertEdge(3, 4, 4);
        g.insertEdge(4, 2, 5);
        g.insertEdge(4, 3, 4);
        g.insertEdge(4, 5, 2);
        g.insertEdge(4, 6, 8);
        g.insertEdge(5, 0, 16);
        g.insertEdge(5, 1, 7);
        g.insertEdge(5, 2, 6);
        g.insertEdge(5, 4, 2);
        g.insertEdge(5, 6, 9);
        g.insertEdge(6, 0, 14);
        g.insertEdge(6, 4, 8);
        g.insertEdge(6, 5, 9);
        
        prim(g, 0);
    }
}

除了Prim算法外,还有一种思路迥异的kruskal算法,基本思想是按照权值从小到大排列所有的边,依次选取并且保证不构成回路.
同样根据上面的图作为基础,步骤为:
第1步：将边(E,F)加入R中。
边(E,F)的权值最小，因此将它加入到最小生成树结果R中。
第2步：将边(C,D)加入R中。
上一步操作之后，边(C,D)的权值最小，因此将它加入到最小生成树结果R中。
第3步：将边(D,E)加入R中。
上一步操作之后，边(D,E)的权值最小，因此将它加入到最小生成树结果R中。
第4步：将边(B,F)加入R中。
上一步操作之后，边(C,E)的权值最小，但(C,E)会和已有的边构成回路；因此，跳过边(C,E)。同理，跳过边(C,F)。将边(B,F)加入到最小生成树结果R中。
第5步：将边(E,G)加入R中。
上一步操作之后，边(E,G)的权值最小，因此将它加入到最小生成树结果R中。
第6步：将边(A,B)加入R中。
上一步操作之后，边(F,G)的权值最小，但(F,G)会和已有的边构成回路；因此，跳过边(F,G)。同理，跳过边(B,C)。将边(A,B)加入到最小生成树结果R中。

此时，最小生成树构造完成！它包括的边依次是：(E,F) (C,D) (D,E) (B,F) (E,G) (A,B)。
我们还是选择基于邻接表实现该算法
首先为了方便,我们还往MyGraph类中增加一个内部类和三个方法,方便边的排序

  class Edge{
        Object from;
        Object to;
        int weight;
        public Edge(Object from, Object to, int weight) {
            super();
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
        
    }
    
    //得到图中的边
    public Edge[] getEgdes(){
        int index=0;
        int num=getNumOfVertex();
        Edge[] edgel=new Edge[numOfEdges/2];
        
        for(int i=0;i<num;i++){
            for(int j=i+1;j<num;j++){
                if(edges[i][j]!=0){
                    edgel[index++]=new Edge(vList.get(i), vList.get(j), edges[i][j]);
                }
            }
        }
        return edgel;
    }
    //按照权值从小到大排列
    public void sortEdges(Edge[] edgel,int elen){
        for(int i=0;i<elen;i++){
            for(int j=i+1;j<elen;j++){
                if(edgel[i].weight>edgel[j].weight){
                    //交换
                    Edge temp=edgel[i];
                    edgel[i]=edgel[j];
                    edgel[j]=temp;
                }
            }
        }
    }
    
    //获取节点i的通路的终点
    public int getEnd(int[] ends,int i){
        while(ends[i]!=0) i=ends[i];
        return i;
    }

该算法实现很简单,主要在于如何判断环路是否存在

  package com.fredal.structure;

import com.fredal.structure.MyGraphy.Edge;

public class Kruskal {

    public static void kruskal(MyGraphy a){
        int index=0;
        int num=a.getNumOfEdges()/2;
        int[] ends=new int[num];
        Edge[] res=new Edge[num];//结果数组
        Edge[] edges=a.getEgdes();//图对应的所有边
        
        a.sortEdges(edges, num);
        
        for(int i=0;i<num;i++){
            int p1=a.getPosition(edges[i].from);//第i条边的起点
            int p2=a.getPosition(edges[i].to);//第i条边的终点
            
            int m=a.getEnd(ends, p1);
            int n=a.getEnd(ends, p2);
            
            if(m!=n){//意味着通路的终点不一样,即没有形成环路
                ends[m]=n;//设置m的通路的终点为n
                res[index++]=edges[i];//保存结果
            }
        }
        
        //打印最小生成树
        int sum=0;
        for(int i=0;i<index;i++){
            sum+=res[i].weight;
        }
        System.out.println("kruskal:");
        System.out.println("weight:"+sum);
        System.out.println("path:");
        for(int i=0;i<index;i++){
            System.out.println(res[i].from+"-"+res[i].to);
        }
    }
    
    public static void main(String[] args) {
        String labels[]={"A","B","C","D","E","F","G"};//结点的标识
        MyGraphy g=new MyGraphy(7);
        for(String label:labels) {
            g.insertVertext(label);//插入结点
        }
        
        g.insertEdge(0, 1, 12);
        g.insertEdge(0, 5, 16);
        g.insertEdge(0, 6, 14);
        g.insertEdge(1, 0, 12);
        g.insertEdge(1, 2, 10);
        g.insertEdge(1, 5, 7);
        g.insertEdge(2, 1, 10);
        g.insertEdge(2, 3, 3);
        g.insertEdge(2, 4, 5);
        g.insertEdge(2, 5, 6);
        g.insertEdge(3, 2, 3);
        g.insertEdge(3, 4, 4);
        g.insertEdge(4, 2, 5);
        g.insertEdge(4, 3, 4);
        g.insertEdge(4, 5, 2);
        g.insertEdge(4, 6, 8);
        g.insertEdge(5, 0, 16);
        g.insertEdge(5, 1, 7);
        g.insertEdge(5, 2, 6);
        g.insertEdge(5, 4, 2);
        g.insertEdge(5, 6, 9);
        g.insertEdge(6, 0, 14);
        g.insertEdge(6, 4, 8);
        g.insertEdge(6, 5, 9);
        
        kruskal(g);
    }
}

更多文章与相关下载请看扩展阅读

版权声明：本文来源简书，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://www.jianshu.com/p/d4d0de9eadf1
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

• 发表于 2020-01-08 08:16:52
• 阅读 ( 1386 )
• 分类：

0 推荐 收藏

你可能感兴趣的文章

• Go数据结构与算法-冒泡排序 1124 浏览
• 数据结构与算法-排序算法-基数排序-笔记整理《十二》 1109 浏览
• 数据结构与算法之基数排序 1392 浏览
• 数据结构——基数排序（算法） 1013 浏览
• 数据结构基础(15) --基数排序 882 浏览
• 【数据结构与算法】基数排序 1037 浏览
• 数据结构与算法系列之一：八大排序之基数排序 1816 浏览
• 数据结构 计数排序（Counting Sort） 详解 附C++代码实现： 1038 浏览
• 数据结构-排序算法-计数排序 1141 浏览

精选的优质文章

• 也许 Go 开发可以更简单！ 10574 浏览
• 如何使用 Golang 日志监控你的应用程序？ 12046 浏览
• 阿里云基于 Go 的微服务架构分享 23964 浏览
• java是否会被取代？Go会否给Java带来冲击？ 28489 浏览
• 千万级规模高性能、高并发的网络架构经验分享 30046 浏览
• 阿里部分面试题汇总,对想进阿里的同学非常实用 62339 浏览
• 实用好文：知乎实时数仓架构实践及演进 31359 浏览
• 支撑马蜂窝「双11」营销大战背后的技术架构 228305 浏览
• 想进大厂？50个多线程面试题，你会多少？（一） 23101 浏览

0 条评论

请先 登录 后评论

官方社群

GO教程

  1. Go语言简介  

• 1.1 Go语言简介
• 1.2 Go语言的特性
• 1.3 Go语言为并发而生
• 1.4 哪些项目使用Go语言开发？
• 1.5 哪些大公司正在使用Go语言
• 1.6 Go语言的性能如何？
• 1.7 Go语言标准库强大
• 1.8 Go语言上手简单
• 1.9 Go语言代码风格清晰、简单
• 1.10 Go语言工程结构详述
• 1.11 第一个Go语言程序
• 1.12 Go语言历史版本

  2. Go语言基本语法  

• 2.1 Go语言变量的声明
• 2.2 Go语言变量的初始化
• 2.3 Go语言多个变量同时赋值
• 2.4 Go语言匿名变量
• 2.5 Go语言变量的作用域
• 2.6 Go语言整型（整数类型）
• 2.7 Go语言浮点类型（小数类型）
• 2.8 Go语言复数
• 2.9 Go语言bool类型（布尔类型）
• 2.10 Go语言字符串
• 2.11 Go语言字符类型（byte和rune）
• 2.12 Go语言数据类型转换
• 2.13 Go语言指针
• 2.14 Go语言变量的生命周期
• 2.15 Go语言常量
• 2.16 Go语言类型别名
• 2.17 Go语言关键字与标识符
• 2.18 Go语言运算符的优先级

  3. Go语言数据结构  

• 3.1 Go语言数组
• 3.2 Go语言多维数组
• 3.3 Go语言切片
• 3.4 使用append()为切片添加元素
• 3.5 Go语言切片复制
• 3.6 Go语言从切片中删除元素
• 3.7 Go语言range关键字
• 3.8 Go语言多维切片
• 3.9 Go语言map（映射）
• 3.10 Go语言遍历map
• 3.11 map元素的删除和清空
• 3.12 Go语言sync.Map
• 3.13 Go语言list（列表）
• 3.14 Go语言nil：空值/零值

  4. Go语言流程控制  

• 4.1 Go语言分支结构
• 4.2 Go语言循环结构
• 4.4 Go语言键值循环
• 4.5 Go语言switch语句
• 4.6 Go语言goto语句
• 4.7 Go语言break（跳出循环）
• 4.8 Go语言continue

  5. Go语言函数  

• 5.1 Go语言函数声明
• 5.2 Go语言函数变量
• 5.3 Go语言匿名函数
• 5.4 Go语言函数类型实现接口
• 5.5 Go语言闭包（Closure）
• 5.6 Go语言可变参数
• 5.7 Go语言defer（延迟执行语句）
• 5.8 Go语言递归函数
• 5.9 Go语言处理运行时错误
• 5.10 Go语言宕机（panic）
• 5.11 Go语言宕机恢复（recover）
• 5.12 Go语言计算函数执行时间
• 5.13 Go语言Test功能测试函数

  6. Go语言结构体  

• 6.1 Go语言结构体定义
• 6.2 Go语言实例化结构体
• 6.3 初始化结构体的成员变量
• 6.4 Go语言构造函数
• 6.5 类型内嵌和结构体内嵌
• 6.6 初始化内嵌结构体
• 6.7 内嵌结构体成员名字冲突
• 6.8 Go语言垃圾回收和SetFinalizer
• 6.9 Go语言链表操作
• 6.10 Go语言数据I/O对象及操作

  7. Go语言接口  

• 7.1 Go语言接口声明（定义）
• 7.2 Go语言实现接口的条件
• 7.3 Go语言类型与接口的关系
• 7.4 Go语言类型断言
• 7.5 Go语言排序
• 7.6 Go语言接口的嵌套组合
• 7.9 Go语言接口和类型之间的转换
• 7.10 Go语言空接口类型
• 7.11 Go语言类型分支
• 7.12 Go语言error接口

  8. Go语言包  

• 8.1 包的基本概念
• 8.2 Go语言封装简介及实现细节
• 8.3 Go语言GOPATH
• 8.4 Go语言常用内置包
• 8.5 Go语言自定义包
• 8.6 Go语言package
• 8.7 Go语言导出包中的标识符
• 8.8 Go语言import导入包
• 8.9 Go语言sync包与锁
• 8.10 Go语言big包
• 8.11 Go语言正则表达式：regexp包
• 8.12 Go语言time包：时间和日期
• 8.13 Go语言os包用法简述
• 8.14 Go语言flag包：命令行参数解析
• 8.15 Go语言go mod包依赖管理工具
• 8.16 Go语言runtime包:运行时

  9. Go语言并发  

• 9.1 Go语言并发简述
• 9.2 Go语言轻量级线程
• 9.3 Go语言并发通信
• 9.4 Go语言竞争状态
• 9.5 Go语言调整并发的运行性能
• 9.6 并发和并行的区别
• 9.7 goroutine和coroutine的区别
• 9.8 Go语言通道（chan）
• 9.9 示例：并发打印
• 9.10 Go语言单向通道
• 9.11 Go语言无缓冲的通道
• 9.12 Go语言带缓冲的通道
• 9.13 Go语言channel超时机制
• 9.14 Go语言多核并行化
• 9.15 互斥锁和读写互斥锁
• 9.16 Go语言等待组
• 9.17 死锁、活锁和饥饿概述
• 9.18 Go语言CSP：通信顺序进程简述
• 9.19 示例：聊天服务器

  10. Go语言反射  

• 10.1 Go语言反射（reflection）
• 10.2 Go语言反射规则浅析
• 10.3 通过反射获取类型信息
• 10.4 通过反射获取指针指向的元素类型
• 10.5 通过反射获取结构体的成员类型
• 10.6 Go语言结构体标签
• 10.7 通过反射获取值信息
• 10.8 通过反射访问结构体成员的值
• 10.9 判断反射值的空和有效性
• 10.10 通过反射修改变量的值
• 10.11 通过类型信息创建实例
• 10.12 通过反射调用函数
• 10.13 Go语言inject库：依赖注入

  11. Go语言文件处理  

• 11.1 Go语言自定义数据文件
• 11.2 Go语言JSON文件的读写操作
• 11.3 Go语言XML文件的读写操作
• 11.4 Go语言使用Gob传输数据
• 11.5 Go语言纯文本文件的读写操作
• 11.6 Go语言二进制文件的读写操作
• 11.7 Go语言自定义二进制文件的读写操作
• 11.8 Go语言zip归档文件的读写操作
• 11.9 Go语言tar归档文件的读写操作
• 11.10 Go语言使用buffer读取文件
• 11.11 Go语言文件的写入、追加、读取、复制操作
• 11.12 Go语言文件锁操作

  12. Go语言编译和工具链  

• 12.1 go build命令
• 12.2 go clean命令
• 12.3 go run命令
• 12.4 go fmt命令
• 12.5 go install命令
• 12.6 go get命令
• 12.7 go generate命令
• 12.8 go test命令
• 12.9 go pprof命令

  13. Go语言进阶  

• 13.1 Go语言的深拷贝和浅拷贝
• 13.2 Go语言引用传递和值传递
• 13.3 Go语言的Socket编程

  14. 常见面试题  

• 14.1 Golang Map底层实现
• 14.2 go语言触发异常的场景有哪些
• 14.3 Printf()、Sprintf()、Fprintf()函数的区别用法是什么
• 14.4 详细说说new和make的区别
• 14.5 详细说说切片和数组的区别
• 14.6 Golang的内存模型，为什么小对象多了会造成gc压力
• 14.7 Data Race问题怎么解决？能不能不加锁解决这个问题
• 14.8 在 range 迭代 slice 时，你怎么修改值的
• 14.9 select可以用于什么
• 14.10 go语言编程的好处是什么
• 14.11 你是否主动关闭过http连接，为啥要这样做
• 14.12 recover的执行时机
• 14.13 说出一个避免Goroutine泄露的措施
• 14.14 如何跳出for select 循环
• 14.15 如何初始化带嵌套结构的结构体
• 14.16 Printf()、Sprintf()、Fprintf()函数的区别用法是什么
• 14.17 go语言中的引用类型包含哪些
• 14.18 说说go语言的select机制

推荐文章

• 数据结构和算法(Golang实现)(15)常见数据结构-列表
• 数据结构和算法(Golang实现)(17)常见数据结构-树
• 数据结构和算法(Golang实现)(24)排序算法-优先队列及堆排序
• 视频教程-go专业数据结构与算法-Go语言
• 视频教程-通俗易懂的Go语言教程第5季数据结构和算法（含配套资料）-Go语言
• 【数据结构与算法】顺序队列与链式队列及其实现
• 视频教程-go专业数据结构与算法高级-Go语言
• 程序员修仙之路-数据结构之 CXO让我做一个计算器！！
• 极客时间专栏：数据结构与算法之美
• 程序员修仙之路-数据结构之 CXO让我做一个计算器！

猜你喜欢

随便看看

• Kafka,ZK集群开发或部署环境搭建及实验
• PHP json_encode里面经常用到的 JSON_UNESCAPED_UNICODE和JSON_UNESCAPED_SLASHES
• php 存json字符串到mysql 反斜杠丢失的问题
• 标签 // HTML 表单 // from 表单转换成json 格式
• php json_encode 自动将 斜杠 前面加上 反斜杠问题 java处理
• PHP json_encode返回的json前端获取时出现unicode转码和反斜杠导致无法解析的解决办法
• Vue.js_移动端屏幕横屏的展示
• java快速教程系列(转载于博客园--作者:vamei)
• 转:PHP并发IO编程之路
• [转]PHP并发IO编程之路（深度长文）