本文由 简悦 SimpRead 转码， 原文地址 mp.weixin.qq.com

1、图的概念

图 (Graph)：是由顶点的有穷非空集合和顶点之间边的集合组成。
顶点 (Vertex)：图中的数据元素。
边 (Edge)：顶点之间的逻辑关系, 边可以是有向的或无向的，也可以带有权重（可以表示距离，花费等）
无向边：若顶点之间的边没有方向，则称这条边为无向边
有向边：若从顶点 vi 到 νj 的边有方向，则称这条边为有向边（一条无向边可以用两条有向边来表示）

无向图

图中任意两个顶点之间的边都是无向边，无向边表示从节点 1 可以到节点 2，也可以从节点 2 到节点 1

有向图

图中任意两个顶点之间的边都是有向边  图中的方向都是朝向一个方向的，并不是有向图都是朝向一个方向，只是为了方便，有向图可以理解为路径是有方向的，只能按着箭头的方向

2、图的存储

图的存储常用的邻接矩阵和邻接表
邻接矩阵存储查询简单方便，缺点当遇到的图是稀疏图时会浪费大量空间
邻接表相对邻接矩阵复杂点，优点节省空间，但当图时稠密图时它的优点就不明显了

邻接矩阵

数组（i，j）表示从 i 到 j 是否连通，0 表示不联通，不为 0 表示联通

无向图存储

将一条有向边转化为两条有向边，比如 顶点 1 和顶点 2 这条无向边转化为顶点 1 到顶点 2 和顶点 2 到顶点 1 两条有向边

有向图存储

有向图二维数组. png

邻接表

有向图邻接表. png

//顶点  class POS{        public POS(int head) {            this.head = head;        }        public  int head;//这个值指向的是边    }//边 class Edge{        public int v;        public  int next;    }//图的初始化top =0;//用来记录边的位置posList =new ArrayList<>();//顶点edgeList =new ArrayList<>();//边的列表for(int i = 0;i<=posSize;i++){     posList.add(new POS(-1));//初始化     hadVisted[i] =false;//初始化 }//添加边邻接表，添加一条从u到v的边 public void Add_Edge(int u, int v) {      //  1 -> 4->3->2        Edge edge =new Edge();        edge.v =v;        edge.next =posList.get(u).head;        posList.get(u).head =top;        edgeList.add(edge);        top++;    }

3、图的搜索

深搜

深搜就是一个递归 1、从顶点 1 开始遍历，遍历到顶点 2，然后从顶点 2 开始遍历 2、由顶点 2 遍历到顶点 5，顶点 5 遍历到顶点 8

3、到顶点 8，没有路径回溯到顶点 5，然后回溯到顶点 2，遍历顶点 6， 由顶点 6 遍历到顶点 74、顶点 8 已遍历，回溯 6，然后回溯到 2，然后回溯到 15、遍历顶点 3，4

//深搜 public void dfsVist(int u){        for(int i = posList.get(u).head;i!=-1;i=edgeList.get(i).next){            Edge edge = edgeList.get(i);            if(!hadVisted[edge.v]){    System.out.println("访问节点:"+edge.v);                hadVisted[edge.v] =true;                vist(edge.v);            }        }    }

广搜

广搜需要一个队列来辅助 从 1 开始将与 1 相连的 2，3，4 加入队列，同时 1 出列从队列开头取出顶点 2，将与 2 相连的 5，6 加入队列，2 出列取出 3，与 3 相连的都访问了，取出 4，3，4 出列，7 进入队列取 5，将与 5 相连的 8 加入队列，5 出列接下来取出 6，7，8，因为都访问过了，等列表为空，遍历结束

public void bfsVist(int u){        Queue queue = new LinkedList();        queue.add(u);//加入队列        System.out.println("访问节点="+u);        while (!queue.isEmpty()){//直至列表为空            Integer p = (Integer) queue.poll();//取出列表里元素            for(int i = posList.get(p).head;i!=-1;i=edgeList.get(i).next){                Edge edge = edgeList.get(i);                if(!hadVisted[edge.v]){                    hadVisted[edge.v] =true;                    System.out.println("访问节点="+edge.v);                    queue.add((Integer)edge.v);                }            }        }    }

• END -

关于奇舞团

奇舞团是 360 集团最大的大前端团队，代表集团参与 W3C 和 ECMA 会员（TC39）工作。奇舞团非常重视人才培养，有工程师、讲师、翻译官、业务接口人、团队 Leader 等多种发展方向供员工选择，并辅以提供相应的技术力、专业力、通用力、领导力等培训课程。奇舞团以开放和求贤的心态欢迎各种优秀人才关注和加入奇舞团。