图

图的基础

A graph is a data structure where a node can have zero or more adjacent elements.

The connection between two nodes is called edge. Nodes can also be called vertices.

图是一种数据结构，其中节点可以具有零个或多个相邻元素。两个节点之间的连接称为边缘。节点也可以称为顶点。

名称	内容
顶点的度	一个顶点的度（degree）是指与该顶点相连的边的条数。比如上图中，紫色顶点的度是 3，蓝色顶点的度是 1。
无向图（undirected graph）	如果所有的边都是双向（译者注：或者理解为没有方向）的，那我们就有了一个无向图（undirected graph）。
有向图（directed graph）	如果边是有向的，我们得到的就是有向图（directed graph）。你可以将有向图和无向图想象为单行道或双行道组成的交通网。
环（cycle）	图可以有环（cycle），即如果遍历图的顶点，某个顶点可以被访问超过一次。
无环图（acyclic graph）	没有环的图被称为无环图（acyclic graph）。
连通图（connected graph）	从任一节点出发，沿着各条边可以访问图中任意节点
非连通图（disconnected graph）	从一个顶点出发，并非所有顶点都是可到达的。
完全图（complete graph）	当一个图中两两不同的顶点之间都恰有一条边相连，这样的图就是完全图（complete graph）。

---

图的应用

当图的每条边都被分配了权重时，我们就有了一个加权图（weighted graph）。如果边的权重被忽略，那么可以认为每条边的权重都相同。

加权图应用的场景很多，根据待解决问题主体的不同，有不同的展现。

航空线路图 (如上图所示)

• 顶点 = 机场
• 边 = 两个机场间的飞行线路
• 权重 = 两个机场间的距离

GPS 导航

• 顶点 = 交叉路口
• 边 = 道路
• 权重 = 从一个路口到另一个路口所花的时间

网络

• 顶点 = 服务器
• 边 = 数据链路
• 权重 = 连接速度

图在现实世界中的应用有：

• 电子电路
• 航空控制
• 行车导航
• 电信设施： 基站建设规划
• 社交网络： Facebook 利用图来推荐（你可能认识的）朋友
• 推荐系统： Amazon/Netflix 利用图来推荐产品与电影
• 利用图来规划物流线路

图的存储结构

图可以使用两种存储结构，分别是邻接矩阵和邻接表。

邻接矩阵无向图

public class MatrixNDG {

    int size;//图顶点个数
    char[] vertexs;//图顶点名称
    int[][] matrix;//图关系矩阵

    public MatrixNDG(char[] vertexs,char[][] edges){
        size=vertexs.length;
        matrix=new int[size][size];//设定图关系矩阵大小
        this.vertexs=vertexs;

        for(char[] c:edges){//设置矩阵值
            int p1 = getPosition(c[0]);//根据顶点名称确定对应矩阵下标
            int p2 = getPosition(c[1]);

            matrix[p1][p2] = 1;//无向图，在两个对称位置存储
            matrix[p2][p1] = 1;
        }

    }

    //图的遍历输出
    public void print(){
        for(int[] i:matrix){
            for(int j:i){
                System.out.print(j+" ");
            }
            System.out.println();
        }
    }

    //根据顶点名称获取对应的矩阵下标
    private int getPosition(char ch) {
        for(int i=0; i<vertexs.length; i++)
            if(vertexs[i]==ch)
                return i;
        return -1;
    }

    public static void main(String[] args) {
        char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G','H','I','J','K'};
        char[][] edges = new char[][]{
            {'A', 'C'}, 
            {'A', 'D'}, 
            {'A', 'F'}, 
            {'B', 'C'}, 
            {'C', 'D'}, 
            {'E', 'G'}, 
            {'D', 'G'},
            {'I','J'},
            {'J','G'},};
        MatrixNDG pG;
        // 自定义"图"(输入矩阵队列)
        // 采用已有的"图"
        long start=System.nanoTime();

        for(int i=0;i<10000;i++){
            pG = new MatrixNDG(vexs, edges);
            //pG.print();   // 打印图 
        }

        long end=System.nanoTime();

        System.out.println(end-start);
    }
}

邻接矩阵有向图

public class MatrixDG {
    int size;
    char[] vertexs;
    int[][] matrix;

    public MatrixDG(char[] vertexs,char[][] edges){
        size=vertexs.length;
        matrix=new int[size][size];
        this.vertexs=vertexs;

        //和邻接矩阵无向图差别仅仅在这里
        for(char[] c:edges){
            int p1 = getPosition(c[0]);
            int p2 = getPosition(c[1]);

            matrix[p1][p2] = 1;
        }

    }

    public void print(){
        for(int[] i:matrix){
            for(int j:i){
                System.out.print(j+" ");
            }
            System.out.println();
        }
    }

    private int getPosition(char ch) {
        for(int i=0; i<vertexs.length; i++)
            if(vertexs[i]==ch)
                return i;
        return -1;
    }



    public static void main(String[] args) {
        char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G','H','I','J','K'};
        char[][] edges = new char[][]{
            {'A', 'C'}, 
            {'A', 'D'}, 
            {'A', 'F'}, 
            {'B', 'C'}, 
            {'C', 'D'}, 
            {'E', 'G'}, 
            {'D', 'G'},
            {'I','J'},
            {'J','G'},};
        MatrixDG pG;
        // 自定义"图"(输入矩阵队列)
        //pG = new MatrixUDG();
        // 采用已有的"图"
        pG = new MatrixDG(vexs, edges);

        pG.print();
    }

}

邻接表无向图

public class ListNDG {

    Vertex[] vertexLists;//邻接表数组
    int size;

    class Vertex{//邻接表节点类，单链表数据结构
        char ch;
        Vertex next;

        Vertex(char ch){//初始化方法
            this.ch=ch;
        }
        void add(char ch){//加到链表尾
            Vertex node=this;
            while(node.next!=null){
                node=node.next;
            }
            node.next=new Vertex(ch);
        }
    }

    public ListNDG(char[] vertexs,char[][] edges){

        size=vertexs.length;
        this.vertexLists=new Vertex[size];//确定邻接表大小
        //设置邻接表头节点
        for(int i=0;i<size;i++){
            this.vertexLists[i]=new Vertex(vertexs[i]);
        }
        //存储边信息
        for(char[] c:edges){
           int p1=getPosition(c[0]);
           vertexLists[p1].add(c[1]);
           int p2=getPosition(c[1]);
           vertexLists[p2].add(c[0]);
        }

    }

    //跟据顶点名称获取链表下标
    private int getPosition(char ch) {
        for(int i=0; i<size; i++)
            if(vertexLists[i].ch==ch)
                return i;
        return -1;
    }

    //遍历输出邻接表
    public void print(){
       for(int i=0;i<size;i++){
           Vertex temp=vertexLists[i];
           while(temp!=null){
               System.out.print(temp.ch+" ");
               temp=temp.next;
           }
           System.out.println();
       }
    }

    public static void main(String[] args){
        char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G','H','I','J','K'};
        char[][] edges = new char[][]{
            {'A', 'C'}, 
            {'A', 'D'}, 
            {'A', 'F'}, 
            {'B', 'C'}, 
            {'C', 'D'}, 
            {'E', 'G'}, 
            {'D', 'G'},
            {'I','J'},
            {'J','G'},};

        ListNDG pG;

        long start=System.nanoTime();

        for(int i=0;i<10000;i++){
            pG = new ListNDG(vexs, edges);
            //pG.print();   // 打印图 
        }

        long end=System.nanoTime();

        System.out.println(end-start);

    }

}

邻接表有向图

public class ListDG {
    Vertex[] vertexLists;
    int size;

    class Vertex{
        char ch;
        Vertex next;

        Vertex(char ch){
            this.ch=ch;
        }
        void add(char ch){
            Vertex node=this;
            while(node.next!=null){
                node=node.next;
            }
            node.next=new Vertex(ch);
        }


    }

    public ListDG(char[] vertexs,char[][] edges){

        size=vertexs.length;
        this.vertexLists=new Vertex[size];
        for(int i=0;i<size;i++){
            this.vertexLists[i]=new Vertex(vertexs[i]);
        }

        for(char[] c:edges){
           int p=getPosition(c[0]);
           vertexLists[p].add(c[1]);
        }

    }

    private int getPosition(char ch) {
        for(int i=0; i<size; i++)
            if(vertexLists[i].ch==ch)
                return i;
        return -1;
    }

    public void print(){
       for(int i=0;i<size;i++){
           Vertex temp=vertexLists[i];
           while(temp!=null){
               System.out.print(temp.ch+" ");
               temp=temp.next;
           }
           System.out.println();
       }
    }

    public static void main(String[] args){
        char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G','H','I','J','K'};
        char[][] edges = new char[][]{
            {'A', 'C'}, 
            {'A', 'D'}, 
            {'A', 'F'}, 
            {'B', 'C'}, 
            {'C', 'D'}, 
            {'E', 'G'}, 
            {'D', 'G'},
            {'I','J'},
            {'J','G'},};

        ListDG pG;

        long start=System.nanoTime();

        for(int i=0;i<10000;i++){
            pG = new ListDG(vexs, edges);
            //pG.print();   // 打印图 
        }

        long end=System.nanoTime();

        System.out.println(end-start);

    }
}