1.图基本介绍
1)前面大家学了线性表和树
2)线性表局限于一个直接前驱和一个直接后继的关系
3)树也只能有一个直接前驱也就是父节点
4)当我们需要表示多对多的关系时，这 里我们就用到了图。
图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。结点 也可以称为顶点。如图:
1.图的常用概念
1)顶点(vertex)
2)边(edge)
3)路径
4)无向图(下图
5)有向图
6)带权图
7)连通图：
如果图中任意一个顶点都存在一条路径到达另外一个顶点，那么这幅图就称之为连通图
8) 连通子图：
2.图的表示方式
图的表示方式有两种::
二维数组表示(邻接矩阵)
链表表示(邻接表)
1.邻接矩阵
邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言,矩阵是的row和col表示的是1...n个点。
2.邻接表
邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在会造成空间的一定损失.
邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成
3.快速入门案例
1.邻接矩阵方式
import java.util.ArrayList; import java.util.Arrays; public class Graph { private ArrayList<String> vertexList;//存储顶点集合 private int[][] edges;//存储图对应的邻结矩阵 private int numOfEdges;//表示边的数目 private boolean[] isVisited; //记录某个结点是否被访问 public static void main(String[] args) { int n=5; //节点的个数 String Vertexs[]={"A","B","C","D","E"}; //创建图对象 Graph graph = new Graph(n); //循环的添加顶点 for (String vertex:Vertexs){ graph.insertVertex(vertex); } //添加边 graph.insertEdge(0,1,1); graph.insertEdge(0,2,1); graph.insertEdge(1,2,1); graph.insertEdge(1,3,1); graph.insertEdge(1,4,1); graph.showGraph(); } //构造器 public Graph(int n){ edges = new int[n][n]; vertexList = new ArrayList<>(n); numOfEdges=0; } //插入节点 public void insertVertex(String vertex){ vertexList.add(vertex); } //返回节点的个数 public int getNumOfVertex(){ return vertexList.size(); } //返回节点i(下标)对应的数据 0->"A" 1->"B" 2->"C" public String getValueByIndex(int i){ return vertexList.get(i); } //显示图对应的矩阵 public void showGraph(){ for (int[] link:edges){ System.out.println(Arrays.toString(link)); } } //返回v1和v2的权值 public int getWeight(int v1,int v2){ return edges[v1][v2]; } //返回边的数目 public int getNumOfEdges() { return numOfEdges; } /** * 添加边 * @param v1 * @param v2 * @param weight */ public void insertEdge(int v1,int v2,int weight){ edges[v1][v2]=weight; edges[v2][v1]=weight; numOfEdges++; } }
类名
Graph
构造方法
Graph(int V) ：创建一个包含 V 个顶点但不包含边的图
成员方法
1.public int V(): 获取图中顶点的数量
2.public int E(): 获取图中边的数量
3.public void addEdge(int v,int w): 向图中添加一条边 v-w
4.public Queue adj(int v) ：获取和顶点 v 相邻的所有顶点
成员变量
1.private fifinal int V: 记录顶点数量
2.private int E: 记录边数量
3.private Queue[] adj: 邻接表
import sun.misc.Queue; public class Graph { //顶点数目 private final int V; //边的数目 private int E; //邻接表 private Queue<Integer>[] adj; public Graph(int V) { this.V = V; //初始化顶点数量 this.E = 0; // 初始化边的数量 this.adj = new Queue[V]; // 初始化邻接表 // 初始化邻接表中的空队列 for (int i = 0; i < adj.length; i++) { adj[i] = new Queue<Integer>(); } } //获取顶点数目 public int V() { return V; } //获取边的数目 public int E() { return E; } //向图中添加一条边v-w public void addEdge(int v, int w) { //把w添加到v的链表中，这样顶点v就多了一个相邻点w adj[v].enqueue(w); //把v添加到w的链表中，这样顶点w就多了一个相邻点v adj[w].enqueue(v); // 边的数目自增1 E++; } // 获取和顶点v相邻的所有顶点 public Queue<Integer> adj(int v) { return adj[v]; } }
2.图遍历
所谓图的遍历，即是对结点的访问。一个图有那么多个结点，如何遍历这些结点，需要特定策略，一般有两种.
访问策略: (1 )深度优先遍历 (2)广度优先遍历
1.深度优先遍历
图的 深度优先搜索 (Depth First Search)
(1)深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点， 可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
(2)我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。
(3)显然，深度优先搜索是一个递归的过程
深度优先遍历算法步骤
1.访问初始结点v，并标记结点v为已访问。
2.查找结点v的第一个邻接结点w。
3.若w存在，则继续执行4，如果w不存在，则回到第1步，将从v的下一个结点继续。
4.若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）。
5.若w已经访问查找结点v的w邻接结点的下一个邻接结点，转到步骤3
A对应0 B对应1 C对应2 D对应3 E对应4
import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Graph { //图的实现:利用邻接矩阵的形式实现 //注意:此处实现的是无向图 //定义图的内部属性 private List<String> vertexList;//用于存储顶点的集合 private int[][] edges;//用来保存图对应的邻接矩阵 private int edgeOfNums;//显示边的个数 //定义boolean数组:记录某个结点是否已经被访问,数组大小和结点个数大小相同 private boolean[] isVisited; public static void main(String[] args) { //定义图的所有顶点 String[] vertexs = {"A","B","C","D","E"}; //创建图 Graph graph = new Graph(vertexs.length); //添加顶点到图中 for (String vertex : vertexs) { graph.addVertex(vertex); } //添加边到图中 //A-B A-C B-C B-D B-E graph.insertEdge(0,1,1); graph.insertEdge(0,2,1); graph.insertEdge(1,2,1); graph.insertEdge(1,3,1); graph.insertEdge(1,4,1); //显示图的邻接矩阵信息 graph.showGraph(); //进行图的深度优先遍历A==>B==>C==>D==>E graph.DFS(); } //定义图的构造器 public Graph(int n) {//n表示定义的图的顶点的个数 //初始化邻接矩阵和顶点集合 edges = new int[n][n]; vertexList = new ArrayList<String>(n); } //===========深度优先遍历的方法=========== //1.根据当前结点的下标获取其第一个邻接结点的下标 //若存在,返回其下标;若不存在,则返回-1 public int getFirstNeighbor(int index) { //遍历顶点集合 for (int i = 0; i < vertexList.size(); i++) { if (edges[index][i] == 1) { return i; } } //若没有邻接的结点,则返回-1 return -1; } //2.根据当前结点的前一个邻接结点的下标获取下一个邻接结点的下标 //同上:若存在,返回其下标;若不存在,则返回-1 public int getNextNeighbor(int v1,int v2) { for (int i = v2 +1;i < vertexList.size();i++) { if (edges[v1][i] == 1) { return i; } } //若没有下一个邻接的结点,则返回-1 return -1; } //3.深度优先算法DFS private void DFS(boolean[] isVisited,int i) { //i表示访问的当前结点的下标 //1.访问该结点,输出 System.out.print(getVertexByIndex(i) + "==>"); //2.将该结点设置为已经访问 isVisited[i] = true; //3.查找结点i的第一个邻接的结点w int w = getFirstNeighbor(i); //4.判断w是否存在 while (w != -1) { //表示w(第一个邻接的结点存在) //5.判断w是否已经被访问 if (!isVisited[w]) { //6.1如果没有被访问,则对w进行深度优先遍历递归 DFS(isVisited,w); } //6.2如果w已经被访问过了 //查找v的w的邻接结点的下一个邻接结点 //同时回到4:判断其是否存在 w = getNextNeighbor(i,w); } } //上面的DFS没有考虑W不存在,返回到结点i的下一个结点继续进行DFS //我们利用一个DFS方法的重载来完成DFS的回溯 public void DFS() { isVisited = new boolean[vertexList.size()];//初始化isVisited的size for (int i = 0; i < getVertexNum(); i++) { if (!isVisited[i]) { DFS(isVisited,i); } } } //===========深度优先遍历的方法(为上)=========== //插入结点(顶点的方法) public void addVertex(String vertex) { vertexList.add(vertex); } //添加边:传入参数 /** * * @param v1 表示点的下标即使第几个顶点 "A"-"B" "A"->0 "B"->1 * @param v2 第二个顶点对应的下标 * @param weight 表示是否连接0/1 */ public void insertEdge(int v1,int v2,int weight) { //由于图为无向图,故将两个顶点的正序和反序都设置为weight edges[v1][v2] = weight; edges[v2][v1] = weight; edgeOfNums++;//每增加一条边,将边的条数加1 } //图的常用API //1.获取两个顶点的权值weight public int getWeight(int v1,int v2) { return edges[v1][v2]; } //2.获取图的边的长度 public int getEdgeOfNums(){ return edgeOfNums; } //3.返回结点i(下标)对应的数据 0->"A" 1->"B" 2->"C" public String getVertexByIndex(int index) { return vertexList.get(index); } //4.图的邻接矩阵的显示方法 public void showGraph() { for (int[] edge : edges) { System.out.println(Arrays.toString(edge)); } } //5.获取顶点的个数 public int getVertexNum() { return vertexList.size(); } }
2.广度优先遍历
类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点
广度优先遍历算法步骤
1.访问初始结点v并标记结点v为已访问。
2.结点v入队列
3.当队列非空时，继续执行，否则算法结束。
4.出队列，取得队头结点u。
5.查找结点u的第一个邻接结点w。
6.若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤：
6.1 若结点w尚未被访问，则访问结点w并标记为已访问。
6.2 结点w入队列
6.3 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6
A对应0 B对应1 C对应2 D对应3 E对应4
import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.List; public class Graph { //图的实现:利用邻接矩阵的形式实现 //注意:此处实现的是无向图 //定义图的内部属性 private List<String> vertexList;//用于存储顶点的集合 private int[][] edges;//用来保存图对应的邻接矩阵 private int edgeOfNums;//显示边的个数 //定义boolean数组:记录某个结点是否已经被访问,数组大小和结点个数大小相同 private boolean[] isVisited; public static void main(String[] args) { //定义图的所有顶点 String[] vertexs = {"A","B","C","D","E"}; //创建图 Graph graph = new Graph(vertexs.length); //添加顶点到图中 for (String vertex : vertexs) { graph.addVertex(vertex); } //添加边到图中 //A-B A-C B-C B-D B-E graph.insertEdge(0,1,1); graph.insertEdge(0,2,1); graph.insertEdge(1,2,1); graph.insertEdge(1,3,1); graph.insertEdge(1,4,1); //显示图的邻接矩阵信息 graph.showGraph(); System.out.println("广度优先遍历为:"); graph.BFS(); } //定义图的构造器 public Graph(int n) {//n表示定义的图的顶点的个数 //初始化邻接矩阵和顶点集合 edges = new int[n][n]; vertexList = new ArrayList<String>(n); } //=============广度优先遍历(BFS)============= //1.根据当前结点的下标获取其第一个邻接结点的下标 //若存在,返回其下标;若不存在,则返回-1 public int getFirstNeighbor(int index) { //遍历顶点集合 for (int i = 0; i < vertexList.size(); i++) { if (edges[index][i] == 1) { return i; } } //若没有邻接的结点,则返回-1 return -1; } //2.根据当前结点的前一个邻接结点的下标获取下一个邻接结点的下标 //同上:若存在,返回其下标;若不存在,则返回-1 public int getNextNeighbor(int v1,int v2) { for (int i = v2 +1;i < vertexList.size();i++) { if (edges[v1][i] == 1) { return i; } } //若没有下一个邻接的结点,则返回-1 return -1; } private void BFS(boolean[] isVisited,int i) { //定义局部变量 int u;//表示队列的头结点对应的下标 int w;//表示邻接结点的下标 //定义存储结点访问的顺序 LinkedList queue = new LinkedList(); //1.访问当前结点,即输出当前结点的信息 System.out.print(getVertexByIndex(i) + "-->"); //2.标记其已被访问 isVisited[i] = true; //3.将该结点加入队列:利用linkedlist的api:addLast(相当于入队列) queue.addLast(i); //进行while循环完成BFS while (!queue.isEmpty()) { //只要队列不为空 //4.取出队列的头结点下标 u = (Integer)queue.removeFirst(); //5.获取u(头结点)的第一个邻接结点的下标 w = getFirstNeighbor(u); while (w != -1) {//说明w(邻接结点存在) //6.继续判断是否访问过 if (!isVisited[w]) { //6.1如果没有访问过,则访问该结点 System.out.print(getVertexByIndex(w) + "-->"); //6.2标记其已经被访问 isVisited[w] = true; //6.3将其入队列 queue.addLast(w); } //如果已经访问过,则查找u的继w的下一个邻接结点,继续进行上述步骤 w = getNextNeighbor(u,w); } } } //上面的BFS只是对一个结点进行了对应层的遍历访问 //for循环完成每一个结点的访问 public void BFS() { isVisited = new boolean[vertexList.size()]; for (int i = 0; i < getVertexNum(); i++) { if (!isVisited[i]) { //若该结点未被访问 BFS(isVisited,i); } } } //=============广度优先遍历(BFS)(为上)============= //插入结点(顶点的方法) public void addVertex(String vertex) { vertexList.add(vertex); } //添加边:传入参数 /** * * @param v1 表示点的下标即使第几个顶点 "A"-"B" "A"->0 "B"->1 * @param v2 第二个顶点对应的下标 * @param weight 表示是否连接0/1 */ public void insertEdge(int v1,int v2,int weight) { //由于图为无向图,故将两个顶点的正序和反序都设置为weight edges[v1][v2] = weight; edges[v2][v1] = weight; edgeOfNums++;//每增加一条边,将边的条数加1 } //图的常用API //1.获取两个顶点的权值weight public int getWeight(int v1,int v2) { return edges[v1][v2]; } //2.获取图的边的长度 public int getEdgeOfNums(){ return edgeOfNums; } //3.返回结点i(下标)对应的数据 0->"A" 1->"B" 2->"C" public String getVertexByIndex(int index) { return vertexList.get(index); } //4.图的邻接矩阵的显示方法 public void showGraph() { for (int[] edge : edges) { System.out.println(Arrays.toString(edge)); } } //5.获取顶点的个数 public int getVertexNum() { return vertexList.size(); } }
