作者:28640

出处:

为什么要有图？

1、前面我们学习到的线性表与树

2、线性表局限一个直接前驱和一个直接后续的关系

3、树也只能有一个直接前驱、也就是父节点

4、我们需要多对多的关系的时候，就需要使用到图

一、什么是图图的基本介绍

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

图的常用知识概念图的常见表达方式

图的表达方式有两种： 二维数组表示（领接矩阵）；链表表示（邻接表）

顶点0 ->顶点1、2、3、4、5、时，若能连通则是1，否则0 表示

二、通过示例认识图图的快速入门案例

根据如图所示，使用邻接矩阵展示连接效果，1 表示能连接 0-表示不能连接

思路分析

1.使用集合的方式存储节点信息

2.使用二维数组[][]保存矩阵信息

3.初始化节点个数 n 时，集合长度为n，二维码数组长度为n * n

4.添加两个节点之间的连接时，需要记录两个节点的下标

public class Graph {    private ArrayList<String > vertexList;//存储顶点的集合    private int[][] edges;//存储顶点对应图的邻接矩阵    private int numOfEdges;//表示边的数目    //构造器    public Graph(int n ){        edges = new int[n][n];        vertexList = new ArrayList<String>(n);        numOfEdges = 0;    }    //插入节点    public void  insertVertex(String vertex){        vertexList.add(vertex);    }    //添加边    public void insertEdge(int v1,int v2,int weight){        edges[v1][v2] = weight;        edges[v2][v1] = weight;        numOfEdges++;    }    //返回目前的节点个数    public int getNumOfVertex(){        return vertexList.size();    }    //得到目前边的个数    public int getNumOfEdges(){        return numOfEdges;    }    //返回下标对应节点数据    public String getValueByIndex(int i){        return vertexList.get(i);    }    //返回两个节点之间的权值    public int getWeight(int v1,int v2){        return edges[v1][v2];    }    //显示图对应的矩阵    public void showGraph(){        for(int[] link :edges){            System.out.println(Arrays.toString(link));        }    }}

接下来我们按照图所示，将节点：A、B、C、D、E 添加进demo看看

public static void main(String[] args) {     //节点的数组     String[] arr = {"A","B","C","D","E"};     //创建图对象     Graph graph = new Graph(arr.length);     //循环添加顶点项     for(String data :arr){            graph.insertVertex(data);     }     graph.showGraph();}运行结果如下：[0, 0, 0, 0, 0][0, 0, 0, 0, 0][0, 0, 0, 0, 0][0, 0, 0, 0, 0][0, 0, 0, 0, 0]

根据运行结果来说，我们添加成功了，但是发现了嘛？为什么全是0？

那是我们没有添加边，并且如图所示是 无向图 ，现在我们进行添加边

如图连接的节点是： A-B/B-A、A-C/C-A、B-C/C-B、B-E/E-B、B-D/D-B

public static void main(String[] args) {    //节点的数组     String[] arr = {"A","B","C","D","E"};     //创建图对象     Graph graph = new Graph(arr.length);     //循环添加顶点项     for(String data :arr){            graph.insertVertex(data);     }     //graph.showGraph();     //添加边 //`A-B/B-A、A-C/C-A、B-C/C-B、B-E/E-B、B-D/D-B`        graph.insertEdge(0,1,1);//`A-B     graph.insertEdge(0,2,1);//`A-C     graph.insertEdge(1,2,1);//`B-C     graph.insertEdge(1,4,1);//`B-E     graph.insertEdge(1,3,1);//`B-D     graph.showGraph();}运行结果如下：[0, 1, 1, 0, 0][1, 0, 1, 1, 1][1, 1, 0, 0, 0][0, 1, 0, 0, 0][0, 1, 0, 0, 0]

我们可以对比一下上面的图，是否正确关联起来

图遍历介绍

所谓的图遍历，即是对结点的访问。

一个图有那么多个结点，如何遍历这些结点？

需要特定策略，一般有两种访问策略: (1)深度优先遍历(2)广度优先遍历

三、图的深度优先遍历介绍图的深度优先搜索(Depth First Search)

1.首先访问第一个邻接结点，然后 再以这个被访问的邻接结点 作为 初始结点 ，访问 它的第一个邻接结点

（每次都在访问完当前结点后，再以之前访问的当前结点的第一个邻接结点）

2.这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问

深度优先遍历算法步骤

1.访问 初始结点v ，并 标记结点v为已访问

2.查找 结点v 的 第一个邻接结点w

3.若 w存在 ，则继续执行4，如果 w不存在 ，则回到第1步，将 从v的下一个结点 继续

4.若w未被访问，对w进行深度优先遍历递归（即把 w当做另一个v，然后进行步骤123 ）

5.查找结点v的w邻接结点的下一个邻接结点，转到步骤3

以上面创建的图，进行一个示例深度优先遍历的图解分析，假设初始点：A

引用示例图解分析算法步骤

第一步：访问初始结点v，并标记结点v为已访问

第二步：查找结点v的第一个邻接结点w

第三步：若 w存在 ，则继续执行，检查若w是否未被访问，则对w进行深度优先遍历递归（即把 w当做另一个v，然后进行步骤123 ），如果 w不存在 ，则回到第1步，将 从v的下一个结点 继续，

第四步：将w节点当做另一个v，执行步骤1-2-3

第五步：C的邻接节点不存在，返回上一层，即是B节点，从下一个节点继续

第六步：D的邻接节点不存在，返回上一层，即是B节点，从下一个节点继续

深度优先搜索代码实现

1.我们需要记录某个节点是否被访问

2.我们查找节点V的邻接节点W，需要知道w的下标，所以需要求出w的下标

根据我们前面的二维数组以及遍历思路，A的下一邻接节点B，就是 [A][B] >0

// 得到领接节点的下标public int getFirstNeighbor(int index){    for (int j =0; j<vertexList.size() ; j++){        if(edges[index][j] > 0){            return j;        }    }    return -1;}

3.我们查找新节点V的邻接节点W，需要根据前一个邻接节点的下标获取

我们需要C的节点邻接节点W，就需要前一个邻接节点C的下标

//根据前一个邻接节点的下标获取下一个领接节点public int getNextNeighbor(int v1,int v2){    for (int j = v2 +1 ;j<vertexList.size();j++){        if(edges[v1][j] >0){            return j;        }    }    return -1;}

那么按照图解思路，我们的算法方法代码（有缺陷，只能访问一次）就是

public class Graph {    //省略之前关键代码        private boolean[] isVisited;//记录某个节点是否被访问        //构造器    public Graph(int n ){        edges = new int[n][n];        vertexList = new ArrayList<String>(n);        numOfEdges = 0;        isVisited = new boolean[n];    }    //深度优先遍历方法    public void dfs(boolean [] isVisited,int i ){        //输出节点进行访问        System.out.print(getValueByIndex(i) + " - >");        //标记已访问        isVisited[i] = true;        //查找当前节点i的邻接节点w        int w = getFirstNeighbor(i);        while(w != -1){            //邻接节点w未被访问            if(!isVisited[w]){                dfs(isVisited,w);            }            //如果w被访问过了            w = getNextNeighbor(i,w);        }    }    public void dfs(){        for(int j=0; j< getNumOfVertex(); j++){            if(!isVisited[j]){                dfs(isVisited,j);            }        }    }

我们根据之前添加的demo测试遍历输出看看

public static void main(String[] args) {    //节点的数组    String[] arr = {"A","B","C","D","E"};    //创建图对象    Graph graph = new Graph(arr.length);    //循环添加顶点项    for(String data :arr){        graph.insertVertex(data);    }    //graph.showGraph();    //添加边    //`A-B/B-A、A-C/C-A、B-C/C-B、B-E/E-B、B-D/D-B`    graph.insertEdge(0,1,1);//`A-B    graph.insertEdge(0,2,1);//`A-C    graph.insertEdge(1,2,1);//`B-C    graph.insertEdge(1,4,1);//`B-E    graph.insertEdge(1,3,1);//`B-D    graph.showGraph();    graph.dfs();}运行结果如下：[0, 1, 1, 0, 0][1, 0, 1, 1, 1][1, 1, 0, 0, 0][0, 1, 0, 0, 0][0, 1, 0, 0, 0]A - >B - >C - >D - >E - >

1.类似于一个分层搜索的过程

2.广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点

广度优先遍历算法步骤

1.访问 初始结点v 并 标记 结点v为 已访问 。

2.结点 v入队列

3.当队列 非空时继续执行 ，否则 初始结点v的算法 结束。

4.出队列，取得 队列头结点u 。

5.查找 结点u 的 第一个邻接结点w 。

6.若结点u的 邻接结点w不存在 ，则转到 步骤3 ；

否则循环执行以下三个步骤：

6.1 若结点w尚 未被访问 ，则访问结点w并 标记为已访问 。

6.2 把 结点w入队列

6.3 接着查找结点u的 继w邻接结点后 的 下一个邻接结点 ，当做w转到步骤6。

以上面创建的图，进行一个示例广度优先遍历的图解分析，假设初始点：A

引用示例图解分析算法步骤

第一步：访问初始结点v，并标记结点v为已访问，并将节点v入队列

第二步：此时出队列，获取队列头结点u，查结点u的第一个邻接结点w

第三步：如果 w不存在 ，则回到第二步，查询结点u的继w的下一个 邻接节点结点 继续。若 w存在 ，则检查w是否未被访问，未访问则对w进行标记访问，并且 入队列 ，且继续查找 继w邻接节点后的下一个节点 当做w，接着判断

第四步:接着查找结点u的 继w邻接结点后 的 下一个邻接结点 ，当做结点w

第五步：如果 w不存在 ，则回到第二步，查询结点u的继w的下一个 邻接节点结点 继续。若 w存在 ，则检查w是否未被访问，未访问则对w进行标记访问，并且 入队列 ，且继续查找 继w邻接节点后的下一个节点 当做w，接着判断

第六步:接着查找结点u的 继w邻接结点后 的 下一个邻接结点 ，当做结点w

第七步：如果 w不存在 ，则回到第二步，查询结点u的继w的下一个 邻接节点结点 继续，直至结束回到思路的第二步，代表结点u（A）结束

第八步：出队列，取得队列头结点U、进行查找邻接结点w

第九步：如果 w不存在 ，则回到第二步，查询结点u的继w的下一个 邻接节点结点 继续。若 w存在 ，则检查w是否未被访问，未访问则对w进行标记访问，并且 入队列 ，且继续查找 继w邻接节点后的下一个节点 当做w，接着判断

第十步：接着查找结点u的 继w邻接结点后 的 下一个邻接结点 ，当做结点w

第十一步：如果 w不存在 ，则回到第二步，查询结点u的继w的下一个 邻接节点结点 继续。若 w存在 ，则检查w是否未被访问，未访问则对w进行标记访问，并且 入队列 ，且继续查找 继w邻接节点后的下一个节点 当做w，接着判断

第十二步：如果 w不存在 ，则回到第二步，查询结点u的继w的下一个 邻接节点结点 继续，直至结束回到思路的第二步，代表结点u（B）结束

广度优先搜索代码实现

1.我们可以先一个节点的广度优先方法，其次其他节点循环调用即可

//对一个节点进行广度优先遍历方法public void bfs(boolean[] isVisited,int i ){    int u;//表示队列头节点的下标    int w;//表示邻接节点的下标    //需要一个队列记录访问的顺序    LinkedList queue = new LinkedList();    //访问节点，输出节点信息    System.out.print(getValueByIndex(i) + " ->");    isVisited[i] = true;    //将节点加入队列，记录访问顺序    //队列尾部添加，头部取    queue.addLast(i);    while (!queue.isEmpty()){        //取出队列的头结点，删掉        u = (Integer) queue.removeFirst();        //查找头结点u的邻接节点        w = getFirstNeighbor(u);        //w != -1 代表找到邻接节点        while(w!= -1 ){            //判断是否访问过            if(!isVisited[w]){                //若没有访问过，则输出并标记已访问                System.out.print(getValueByIndex(i) + " ->");                isVisited[w] = true;                //将节点入队列，代表访问过                queue.addLast(w);            }            //以u为起点，查找w邻接结点的下一个邻接结点            w = getNextNeighbor(u,w);        }    }}

2.接下来则遍历所有节点进行广度优先搜索

//广度优先遍历方法public void bfs(){    for(int j=0; j< getNumOfVertex(); j++){        //没有被访问过才进行广度优先搜索         if(!isVisited[j]){            bfs(isVisited,j);         }    }}

我们根据之前添加的demo测试遍历输出看看

public static void main(String[] args) {    //节点的数组    String[] arr = {"A","B","C","D","E"};    //创建图对象    Graph graph = new Graph(arr.length);    //循环添加顶点项    for(String data :arr){        graph.insertVertex(data);    }    //graph.showGraph();    //添加边    //`A-B/B-A、A-C/C-A、B-C/C-B、B-E/E-B、B-D/D-B`    graph.insertEdge(0,1,1);//`A-B    graph.insertEdge(0,2,1);//`A-C    graph.insertEdge(1,2,1);//`B-C    graph.insertEdge(1,4,1);//`B-E    graph.insertEdge(1,3,1);//`B-D    graph.showGraph();    //graph.dfs();    graph.bfs();}运算结果如下：[0, 1, 1, 0, 0][1, 0, 1, 1, 1][1, 1, 0, 0, 0][0, 1, 0, 0, 0][0, 1, 0, 0, 0]A ->B ->C ->D ->E ->

作者:28640

出处: