Day587588589.图 -数据结构和算法Java

图

一、介绍

二、基本概念

三、图的表示方式

四、代码案例

• 需求

• 代码实现

package com.achang.graph;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;/*** 图结构*/
public class Graph {//存储顶点集合private List<String> vertexList;//矩阵，存储图结构对应的领接矩阵private int[][] edges;//表示当前有多少条边private int numOfEdges;/*** 构造器** @param n 顶点数量*/public Graph(int n) {edges = new int[n][n];vertexList = new ArrayList<>(n);numOfEdges = 0;}//返回v1和v2的权值public int getWeight(int v1,int v2){return edges[v1][v2];}//显示矩阵public void showVertex(){for (int[] edge : edges) {System.out.println(Arrays.toString(edge));}}//返回节点i对应的值 0->Apublic String getValueByIndex(int i){return vertexList.get(i);}//返回节点的个数public int getVertexSize(){return vertexList.size();}//得到边的数目public int getNumOfEdges(){return numOfEdges;}//插入顶点public void addVertex(String vertex) {vertexList.add(vertex);}/*** 添加边* @param v1     表示点的下标及第几个节点 比如ABCDE，A->0 B->1 C->2 D->3 E->4* @param v2     如上* @param weight 权值 1或者0 默认为0*/public void addEdge(int v1, int v2, int weight) {edges[v1][v2] = weight;edges[v2][v1] = weight;numOfEdges++;}public static void main(String[] args) {int n = 5;//节点的个数String[] vertexValue  = {"A","B","C","D","E"};Graph graph = new Graph(vertexValue.length);//添加节点for (String vertex : vertexValue) {graph.addVertex(vertex);}//添加边graph.addEdge(0,1,1);//ABgraph.addEdge(0,2,1);//ACgraph.addEdge(1,2,1);//BCgraph.addEdge(1,3,1);//BDgraph.addEdge(1,4,1);//BEgraph.showVertex();}
}

---

五、图的深度遍历

1、介绍

2、代码实现

/*** 图结构*/
public class Graph {//存储顶点集合private List<String> vertexList;//矩阵，存储图结构对应的领接矩阵private int[][] edges;//表示当前有多少条边private int numOfEdges;//记录每个节点是否被访问过private boolean[] isVisited;/*图的深度遍历i第一次为0*/public void dfs(boolean[] isVisited, int i) {//首先访问该节点，且输出节点System.out.println(getValueByIndex(i));//将已访问过的节点，置为已访问isVisited[i] = true;//查找节点i的第一个临界节点wint w = getFirstNeighbor(i);while (w != -1) {//说明有临界节点//判断是否有没有被访问过if (!isVisited[w]) {//没被访问过dfs(isVisited, w);}//存在，当被访问过w = getNextNeighbor(i, w);}//找到或不存在的}//对dfs 进行一个重载，遍历所有的节点，并进行dfspublic void dfs(){//遍历所有节点，进行dfs[回溯]for (int i = 0; i < getNumOfEdges(); i++) {if (!isVisited[i]){dfs(isVisited,i);}}}//得到第一个临界节点的下标w，如果存在返回对应的下标，不存在返回-1public int getFirstNeighbor(int index) {for (int i = 0; i < vertexList.size(); i++) {if (edges[index][i] > 0) {return i;}}return -1;}//根据前一个临界节点的下标来获取下一个临界节点public int getNextNeighbor(int v1, int v2) {for (int i = v2 + 1; i < vertexList.size(); i++) {if (edges[v1][i] > 0) {return i;}}return -1;}/*** 构造器** @param n 顶点数量*/public Graph(int n) {edges = new int[n][n];vertexList = new ArrayList<>(n);numOfEdges = 0;isVisited = new boolean[n];}//返回v1和v2的权值public int getWeight(int v1, int v2) {return edges[v1][v2];}//显示矩阵public void showVertex() {for (int[] edge : edges) {System.out.println(Arrays.toString(edge));}}//返回节点i对应的值 0->Apublic String getValueByIndex(int i) {return vertexList.get(i);}//返回节点的个数public int getVertexSize() {return vertexList.size();}//得到边的数目public int getNumOfEdges() {return numOfEdges;}//插入顶点public void addVertex(String vertex) {vertexList.add(vertex);}/*** 添加边** @param v1     表示点的下标及第几个节点 比如ABCDE，A->0 B->1 C->2 D->3 E->4* @param v2     如上* @param weight 权值 1或者0 默认为0*/public void addEdge(int v1, int v2, int weight) {edges[v1][v2] = weight;edges[v2][v1] = weight;numOfEdges++;}public static void main(String[] args) {int n = 5;//节点的个数String[] vertexValue = {"A", "B", "C", "D", "E"};Graph graph = new Graph(vertexValue.length);//添加节点for (String vertex : vertexValue) {graph.addVertex(vertex);}//添加边graph.addEdge(0, 1, 1);//ABgraph.addEdge(0, 2, 1);//ACgraph.addEdge(1, 2, 1);//BCgraph.addEdge(1, 3, 1);//BDgraph.addEdge(1, 4, 1);//BEgraph.showVertex();System.out.println("深度优先遍历-------------------↓");graph.dfs();}
}

---

六、图的广度优先遍历

1、介绍分析

2、代码实现

/*** 图结构*/
public class Graph {//存储顶点集合private List<String> vertexList;//矩阵，存储图结构对应的领接矩阵private int[][] edges;//表示当前有多少条边private int numOfEdges;//记录每个节点是否被访问过private boolean[] isVisited;/*** 对一个节点进行广度优先遍历的方法* @param isVisited 是否访问过的数组* @param i 进行广度优先遍历的节点*/public void bfs(boolean[] isVisited,int i){int u;//表示队列的头节点下标int w;//邻接节点w//队列，记录节点访问的顺序LinkedList<Object> queue = new LinkedList<>();//访问遍历节点System.out.print(getValueByIndex(i)+"=>");//标记为已访问isVisited[i] = true;//将节点加入队列queue.addLast(i);while (!queue.isEmpty()){//取出队列的头结点下标u = (int) queue.removeFirst();w = getFirstNeighbor(u);while (w != -1){//找到了//是否访问过if (!isVisited[w]){//没有访问过System.out.print(getValueByIndex(w)+"=>");//标记已经访问isVisited[w] = true;//入队列queue.addLast(w);}//已经访问过了//以u为前驱节点，找w后面的下一个邻接节点w = getNextNeighbor(u,w);//体现出了广度优先}}}//遍历所有的节点，都进行广度优先遍历搜索public void bfs(){for (int i = 0; i < getNumOfEdges(); i++) {if (!isVisited[i]){bfs(isVisited,i);}}}//得到第一个临界节点的下标w，如果存在返回对应的下标，不存在返回-1public int getFirstNeighbor(int index) {for (int i = 0; i < vertexList.size(); i++) {if (edges[index][i] > 0) {return i;}}return -1;}//根据前一个临界节点的下标来获取下一个临界节点public int getNextNeighbor(int v1, int v2) {for (int i = v2 + 1; i < vertexList.size(); i++) {if (edges[v1][i] > 0) {return i;}}return -1;}/*** 构造器** @param n 顶点数量*/public Graph(int n) {edges = new int[n][n];vertexList = new ArrayList<>(n);numOfEdges = 0;isVisited = new boolean[n];}//返回v1和v2的权值public int getWeight(int v1, int v2) {return edges[v1][v2];}//显示矩阵public void showVertex() {for (int[] edge : edges) {System.out.println(Arrays.toString(edge));}}//返回节点i对应的值 0->Apublic String getValueByIndex(int i) {return vertexList.get(i);}//返回节点的个数public int getVertexSize() {return vertexList.size();}//得到边的数目public int getNumOfEdges() {return numOfEdges;}//插入顶点public void addVertex(String vertex) {vertexList.add(vertex);}/*** 添加边** @param v1     表示点的下标及第几个节点 比如ABCDE，A->0 B->1 C->2 D->3 E->4* @param v2     如上* @param weight 权值 1或者0 默认为0*/public void addEdge(int v1, int v2, int weight) {edges[v1][v2] = weight;edges[v2][v1] = weight;numOfEdges++;}public static void main(String[] args) {int n = 5;//节点的个数String[] vertexValue = {"A", "B", "C", "D", "E"};Graph graph = new Graph(vertexValue.length);//添加节点for (String vertex : vertexValue) {graph.addVertex(vertex);}//添加边graph.addEdge(0, 1, 1);//ABgraph.addEdge(0, 2, 1);//ACgraph.addEdge(1, 2, 1);//BCgraph.addEdge(1, 3, 1);//BDgraph.addEdge(1, 4, 1);//BEgraph.showVertex();System.out.println("广度优先遍历-------------------↓");graph.bfs();}
}

---

七、广度优先&深度优先对比

• 广度优先遍历

输出顺序：12345678

• 深度优先遍历

输出顺序：12485367