最大的高仿手表网站,安监局特种作业证全国联网,重庆汽车网站建设,host wordpress图 1. 相关概念2. 图的表示方式3. 图的遍历3.1 深度优先遍历#xff08;DFS#xff09;3.2 广度优先遍历#xff08;BFS#xff09; 1. 相关概念
图G(V,E) #xff1a;一种数据结构#xff0c;可表示“多对多”关系#xff0c;由顶点集V和边集E组成#xff1b;顶点(ve… 图 1. 相关概念2. 图的表示方式3. 图的遍历3.1 深度优先遍历DFS3.2 广度优先遍历BFS 1. 相关概念
图G(V,E) 一种数据结构可表示“多对多”关系由顶点集V和边集E组成顶点(vertex) 边 (edge)一幅点对v,wv,w∈V边也称为弧邻接点vw邻接当且仅当边(v,w)∈E路径 由一个顶点序列v1v2…,vn组成路径长为n-1有向图 边是单向的点对有序无向图 边是双向的图点对无序带权图不同边具有不同的权值的图连通无向图的一个顶点到其他任何顶点都存在一条路径则称其为连通的强连通有向图的一个顶点到其他任何顶点都存在一条路径弱连通有向图本身不是强连通的但是其边不考虑方向的无向图是连通的完全图每一对顶点间都存在边
2. 图的表示方式
邻接矩阵使用二维数组实现数组中每个元素表示图中两顶点之间是否有边或者表示边的权值适用于稠密图对于稀疏图而言此表示方法过于浪费空间 package com.northsmile.graph;import java.util.ArrayList;
import java.util.Arrays;/*** Author:NorthSmile* Create:2023/4/18 9:17* 使用邻接矩阵表示图无向图*/
public class Graph {// 存储边及其权值int[][] edges;// 存储顶点ArrayListString vertexes;// 记录边的数目int edgeNums;public Graph(int n){edgesnew int[n][n];vertexesnew ArrayList(n);edgeNums0;}/*** 插入顶点* param vertex*/public void insertVertex(String vertex){vertexes.add(vertex);}/*** 插入边* param v1 边的一个顶点对应下标* param v2 边的另一个顶点对应下标* param w 边对应权值默认为1*/public void insertEdge(int v1,int v2,int w){edges[v1][v2]w;edges[v2][v1]w;edgeNums;}/*** 获取顶点数量* return*/public int getVertexesNum(){return vertexes.size();}/*** 获取边的数目* return*/public int getEdgesNum(){return edgeNums;}/*** 获取指定下标对应的顶点的值* param v* return*/public String getValByIndex(int v){return vertexes.get(v);}/*** 获取指定边的权值* param v1* param v2* return*/public int getWeightOfEdge(int v1,int v2){return edges[v1][v2];}/*** 显示表示图的邻接矩阵*/public void showGraph(){for (int[] edge:edges){System.out.println(Arrays.toString(edge));}}
}
package com.northsmile.graph;/*** Author:NorthSmile* Create:2023/4/18 9:18*/
public class GraphDemo {public static void main(String[] args) {int n5;String[] vertexes{A,B,C,D,E};Graph graph new Graph(n);// 插入顶点for (String vertex:vertexes){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();}
}邻接表使用数组链表的方式实现适用于稀疏图表示是图的标准表示方法对于每个顶点将其所有邻接点使用一个表存放
package com.northsmile.graph;import java.util.ArrayList;
import java.util.HashMap;/*** Author:NorthSmile* Create:2023/4/18 11:12* 使用邻接表表示图有向图*/
public class GraphByAdjacenceList {// 邻接表HashMapString,Vertex list;int vertexNums;int edgeNums;public GraphByAdjacenceList(int n){listnew HashMap();vertexNumsn;edgeNums0;}/*** 插入顶点* param vertex*/public void insertVertex(String vertex){list.put(vertex,new Vertex(vertexNums));}/*** 插入边* param v 顶点* param w 邻接点*/public void insertEdge(String v,String w){Vertex vertex list.get(v);vertex.table.add(w);edgeNums;}/*** 获取顶点数量* return*/public int getVertexesNum(){return list.size();}/*** 获取边的数目* return*/public int getEdgesNum(){return edgeNums;}/*** 显示表示图的邻接表*/public void showGraph(){for (String vertex:list.keySet()){System.out.println(vertex:list.get(vertex).table);}}/*** 顶点类*/class Vertex{ArrayListString table;public Vertex(int n){tablenew ArrayList(n/2);}}
}
package com.northsmile.graph;/*** Author:NorthSmile* Create:2023/4/18 9:18*/
public class GraphDemo {public static void main(String[] args) {// 2.邻接表int n5;String[] vertexes{A,B,C,D,E};GraphByAdjacenceList graph new GraphByAdjacenceList(n);// 插入顶点for (String vertex:vertexes){graph.insertVertex(vertex);}// 插入边graph.insertEdge(A,B);graph.insertEdge(A,C);graph.insertEdge(B,C);graph.insertEdge(B,D);graph.insertEdge(B,E);graph.showGraph();}
}3. 图的遍历 3.1 深度优先遍历DFS
类似树的先序遍历先访问当前顶点再依次以其邻接点为新的起点进行深度优先遍历与树的遍历不同图在深度优先遍历时当前顶点的邻接点可能已经访问过所以无需再进行访问为了实现顶点的唯一遍历在代码实现时需要提供一个标记数组表示对应顶点是否已经访问过代码实现以递归方式进行 /*** 深度优先遍历类似树的先序遍历* param v 以当前点开始遍历* param visited 标记节点是否访问过*/public void dfs(int v,boolean[] visited){System.out.print(vertexes.get(v)-);// 遍历当前顶点的邻接点for (int i0;ivertexes.size();i){// 说明v、i之间存在边if (edges[v][i]!0!visited[i]){visited[i]true;dfs(i,visited);}}}public void dfs(){// 标记顶点是否已经访问过boolean[] visitednew boolean[vertexes.size()];// 以每个顶点开始进行DFS实现图的完整遍历for (int i0;ivertexes.size();i){if (!visited[i]){visited[i]true;dfs(i,visited);}}}3.2 广度优先遍历BFS
类似树的层序遍历先访问当前顶点再依次访问其邻接点然后分别以其邻接点为新的起点继续进行广度优先遍历与树的遍历不同图在深度优先遍历时当前顶点的邻接点可能已经访问过所以无需再进行访问为了实现顶点的唯一遍历在代码实现时需要提供一个标记数组表示对应顶点是否已经访问过代码实现借助队列实现 /*** 广度优先遍历类似树的层次遍历* param v 以当前点开始遍历* param visited 标记节点是否访问过*/public void bfs(int v,boolean[] visited){ArrayDequeInteger queuenew ArrayDeque();queue.offer(v);visited[v]true;while (!queue.isEmpty()){Integer cur queue.poll();System.out.print(vertexes.get(cur)-);// 遍历当前顶点的邻接点for (int i0;ivertexes.size();i){// 说明v、i之间存在边if (edges[cur][i]!0!visited[i]){visited[i]true;queue.offer(i);}}}}public void bfs(){// 标记顶点是否已经访问过boolean[] visitednew boolean[vertexes.size()];// 以每个顶点开始进行BFS实现图的完整遍历for (int i0;ivertexes.size();i){if (!visited[i]){bfs(i,visited);}}}资料来源尚硅谷
