java实现图的DFS和BFS
2022/4/24 22:12:38
本文主要是介绍java实现图的DFS和BFS,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
java实现图的DFS和BFS
public class GraphDemo { /** * 存储顶点集合 */ private ArrayList<String> vertexList; /** * 存储图对应的领结矩阵 */ private int[][] edges; /** * 表示边的数目 */ private int numOfEdges; /** * 记录是否被访问 */ private boolean[] isVisited; public static void main(String[] args) { // 测试 String[] vertexValues = {"A", "B", "C", "D", "E"}; GraphDemo graph = new GraphDemo(vertexValues.length); // 循环添加节点 for (String vertexValue : vertexValues) { // 加节点 graph.insertVertex(vertexValue); } // 加边 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.dfs(); System.out.println(); graph.bfs(); } public GraphDemo(int n) { // 初始化矩阵和vertexList this.edges = new int[n][n]; this.vertexList = new ArrayList<String>(); this.numOfEdges = 0; this.isVisited = new boolean[n]; } /** * 重载 */ public void bfs() { isVisited = new boolean[getNumOfVertex()]; for (int i = 0; i < getNumOfVertex(); ++i) { if (!isVisited[i]) { bfs(isVisited, i); } } } /** * 广度优先遍历 */ public void bfs(boolean[] isVisited, int i) { // 队列头节点 int u; // 邻接节点 int w; // 队列 LinkedList queue = new LinkedList(); System.out.print(getValueByIndex(i) + " ==> "); isVisited[i] = true; queue.add(i); while (!queue.isEmpty()) { u = (int) queue.removeFirst(); w = getFirstNeighbor(u); // w存在 while (w != -1) { if (!isVisited[w]) { System.out.print(getValueByIndex(w) + " ==> "); isVisited[w] = true; // 入队 queue.addLast(w); } else { // 以u找w下一个节点 w = getNextNeighnor(u, w); } } } } /** * 重载 * 考虑到有不与任何节点所连接的点 */ public void dfs() { isVisited = new boolean[getNumOfVertex()]; // 遍历所有节点 for (int i = 0; i < getNumOfVertex(); i++) { if (!isVisited[i]) { dfs(isVisited, i); } } } /** * 深度优先遍历 */ private void dfs(boolean[] isVisited, int i) { System.out.print(getValueByIndex(i) + " ==> "); isVisited[i] = true; // i的第一个邻接节点 int firstNeighbor = getFirstNeighbor(i); // 存在 while (firstNeighbor != -1) { // 没有被访问过 if (!isVisited[firstNeighbor]) { dfs(isVisited, firstNeighbor); } else { // 被访问过 // 以i找firstNeighbor下一个节点 firstNeighbor = getNextNeighnor(i, firstNeighbor); } } } /** * @return 第一个相邻节点的下标, 没找到返回-1 */ public int getFirstNeighbor(int index) { for (int i = 0; i < vertexList.size(); i++) { // 如果连通 if (edges[index][i] > 0) { return i; } } return -1; } /** * 根据前一个邻接节点的下标来获取后一个领接节点下标 * * @param v1 前一个邻接节点下标 * @param v2 当前节点 * @return 下一个邻接节点的下标 */ public int getNextNeighnor(int v1, int v2) { for (int i = v2 + 1; i < vertexList.size(); ++i) { if (edges[v1][i] > 0) { return i; } } return -1; } /** * @return 顶点个数 */ public int getNumOfVertex() { return vertexList.size(); } /** * @return 边的个数 */ public int getNumOfEdges() { return numOfEdges; } /** * @param i 节点下标 * @return 下标对应的数据 */ public String getValueByIndex(int i) { return vertexList.get(i); } /** * @param v1 v1节点 * @param v2 v2节点 * @return 权值 */ public int getWeight(int v1, int v2) { return edges[v1][v2]; } /** * 添加节点 */ public void insertVertex(String vertex) { vertexList.add(vertex); } /** * 显示矩阵 */ public void showGraph() { for (int[] link : edges) { System.out.println(Arrays.toString(link)); } } /** * 添加边 * * @param v1 表示点的下标 * @param v2 表示另一个点的下标 * @param weight 权值 */ public void insertEdge(int v1, int v2, int weight) { edges[v1][v2] = weight; edges[v2][v1] = weight; ++numOfEdges; } }
这篇关于java实现图的DFS和BFS的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?