图-邻接矩阵

news/2024/11/19 9:39:24/

图的邻接矩阵表示法

参考b站视频

用一维数组存储顶点信息，用二维数组存储顶点与顶点之间的边关系

创建接口类

先定义图要实现的方法

package com.testgraph;
public interface Graph<V> {//获取顶点数int getVerticesSize();//获取边数int getEdgesSize();//增加一个顶点void addVertex(V v);//增加一条边void addEdge(V from,V to);//增加一条带权值的边void addEdge(V from, V to,int weight);//删除一个顶点void removeVertex(V v);//删除一条边void removeEdge(V from, V to);//深度遍历void dfs();//广度遍历void bfs();//打印图void displayGraph();
}
实现接口的方法
  1. 用一维数组存储顶点信息
  2. 用二维数组存储顶点与顶点之间的边关系
  3. 顶点数量，用于实际存储的顶点的数量
  4. size规模，最大可以存储size-1个顶点
package com.testgraph;import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;public class MatrixGraph<V> implements Graph<V> {// 顶点的数量private int verticesNum;// 边的数量private int edgesNum;// 顶点的存储private List<V> verticesList;// 边的存储private int[][] edgesList;// 规模private int size;// 初始化图public MatrixGraph(int size) {// TODO Auto-generated constructor stubthis.verticesList = new ArrayList<>();this.edgesList = new int[size][size];this.size = size;this.verticesNum = 0;this.edgesNum = 0;}@Overridepublic int getVerticesSize() {// TODO Auto-generated method stubreturn this.verticesNum;}@Overridepublic int getEdgesSize() {// TODO Auto-generated method stubreturn this.edgesNum;}@Overridepublic void addVertex(V v) {/**** 判断顶点数组是否存在该顶点 1. 存在则不添加 2. 不存在判断是否已经超上限 1)不超上限则添加到数组中*/int index = this.verticesList.indexOf(v);if (index > -1) {System.out.println(v.toString() + "顶点已经存在！！");} else {this.verticesNum++;if (this.verticesNum + 1 > this.size) {System.out.println("顶点数超上限");this.verticesNum--;} else {this.verticesList.add(v);}}}@Overridepublic void addEdge(V from, V to) {/**** 找出顶点在顶点数组中下标 1. 不存在则不添加 2. 存在则 将二维数组中置为1*/this.addEdge(from, to, 1);}@Overridepublic void addEdge(V from, V to, int weight) {/**** 找出顶点在顶点数组中下标 1. 不存在则不添加 2. 存在则 将二维数组中置为weight*/int fromIndex = this.verticesList.indexOf(from);int toIndex = this.verticesList.indexOf(to);if (fromIndex < 0) {System.out.println("不存在" + from.toString() + "该顶点");} else if (toIndex < 0) {System.out.println("不存在" + to.toString() + "该顶点");} else {this.edgesList[fromIndex][toIndex] = weight;this.edgesNum++;System.out.println(from.toString() + "===>" + to.toString() + "添加边成功！！！");}}@Overridepublic void removeVertex(V v) {/**** 找出顶点在顶点数组中下标 1. 不存在则退出 2. 存在则 将二维数组左上移（谁等于index,则谁向前移动）*/int index = this.verticesList.indexOf(v);boolean flag = this.verticesList.remove(v);if (flag) {// 删除边数---startfor (int i = 0; i < this.verticesNum; i++) {if (this.edgesList[i][index] > 0) {this.edgesNum--;this.edgesList[i][index] = 0;}}for (int j = 0; j < this.verticesNum; j++) {if (this.edgesList[index][j] > 0) {this.edgesNum--;this.edgesList[index][j] = 0;}}// 删除边数---endfor (int i = index; i < this.verticesNum; i++) {for (int j = 0; j < this.verticesNum; j++) {this.edgesList[i][j] = this.edgesList[i + 1][j];}}for (int i = 0; i < this.verticesNum; i++) {for (int j = index; j < this.verticesNum; j++) {this.edgesList[i][j] = this.edgesList[i][j + 1];}}this.verticesNum--;System.out.println(v.toString() + "删除成功！！");} else {System.out.println(v.toString() + "元素不存在！");}}@Overridepublic void removeEdge(V from, V to) {/**** 找出顶点在顶点数组中下标 1. 不存在则退出 2. 存在则 将二维数组中对应边的关系置为0*/int fromIndex = this.verticesList.indexOf(from);int toIndex = this.verticesList.indexOf(to);if (fromIndex < 0) {System.out.println("不存在" + from.toString() + "该顶点");} else if (toIndex < 0) {System.out.println("不存在" + to.toString() + "该顶点");} else {this.edgesList[fromIndex][toIndex] = 0;this.edgesNum--;System.out.println("删除边成功：" + from.toString() + "=XX=>" + to.toString());}}@Overridepublic void dfs() {// 1.建立一个访问数组boolean[] beVisited = new boolean[this.verticesNum];// 2.访问初始节点System.out.print("深度度优先访问：");System.out.print(this.verticesList.get(0));// 3.将初始节点在访问数组置为truebeVisited[0] = true;this.dfs(0, 1, beVisited);System.out.println();}/*** verticesIndex顶点下标 matrixVerticesIndex顶点的邻接表下标*/public void dfs(int verticesIndex, int matrixVerticesIndex, boolean[] beVisited) {// 遍历该顶点的所有邻接节点for (int y = matrixVerticesIndex; y < this.verticesNum; y++) {// 存在路，未访问if (this.edgesList[verticesIndex][y] != 0 && !beVisited[y]) {beVisited[y] = true;// 访问System.out.print("==>" + this.verticesList.get(y));// 深度继续访问该邻接节点的邻接节表this.dfs(y, 0, beVisited);}}}@Overridepublic void bfs() {// 1.建立一个访问数组、一个队列boolean[] beVisited = new boolean[this.verticesNum];Queue<Integer> queue = new LinkedList<>();// 2.访问初始节点System.out.print("广度优先访问：");System.out.print(this.verticesList.get(0));// 3.将初始节点在访问数组置为true,将节点纳入队列中beVisited[0] = true;queue.offer(0);while (!queue.isEmpty()) {// 提取节点int vertexIndex = queue.poll();for (int y = 0; y < this.verticesNum; y++) {// 存在边，未访问if (this.edgesList[vertexIndex][y] != 0 && !beVisited[y]) {// 入列queue.offer(y);// 访问System.out.print("==>" + this.verticesList.get(y));beVisited[y] = true;}}}System.out.println();}@Overridepublic void displayGraph() {// 打印System.out.println("图的顶点" + this.verticesList);System.out.println("图的顶点数：" + getVerticesSize());System.out.println("图的边数为: " + getEdgesSize());System.out.println("图的临接矩阵: ");System.out.print("    ");for (int i = 0; i < this.verticesNum; i++) {System.out.print(this.verticesList.get(i) + " ");}System.out.println();for (int i = 0; i < this.verticesNum; i++) {System.out.print(this.verticesList.get(i) + ": [ ");for (int j = 0; j < this.verticesNum; j++) {System.out.print(" " + this.edgesList[i][j] + " ");}System.out.println("]");}}}
测试类
package com.testgraph;public class GraphTest {public static void main(String []args) {//MatrixGraph graph = new MatrixGraph(10);LinkGraph graph = new LinkGraph(15);graph.addVertex("北京");graph.addVertex("上海");graph.addVertex("广东");graph.addVertex("四川");graph.addVertex("湖南");graph.addVertex("吉林");graph.addVertex("海南");graph.addVertex("重庆");graph.addVertex("台湾");graph.addVertex("香港");graph.addVertex("陕西");graph.addVertex("贵州");graph.addVertex("河北");graph.addVertex("河南");graph.addEdge("北京","上海");graph.addEdge("北京","广东");graph.addEdge("四川","广东");graph.addEdge("湖南","广东");graph.addEdge("广东","上海");graph.addEdge("上海","四川");graph.addEdge("台湾","上海");graph.addEdge("重庆","广东");graph.addEdge("香港","北京");graph.addEdge("贵州","上海");graph.addEdge("吉林","海南");graph.addEdge("四川","海南");graph.addEdge("广东","吉林");graph.displayGraph();//graph.removeEdge("湖南","广东");//graph.displayGraph();//graph.removeVertex("广东");//graph.displayGraph();graph.dfs();graph.bfs();}
}

http://www.ppmy.cn/news/911935.html

相关文章

丰农控股 CIO 王轶枭：万亿级农资市场，神策数据助力大丰收筑就数据驱动核心竞争力...

丰农控股 CIO 王轶枭：万亿级农资市场，神策数据助力大丰收筑就数据驱动核心竞争力...

丰农控股集团成立于 2014 年初&#xff0c;是国内专业的农业产业服务集团。集团多年来聚焦国内种植领域&#xff0c;以“提升农业价值”为使命&#xff0c;为国内 2.6 亿种植户提供专业服务&#xff0c;帮助种植户解决传统农资流通渠道单一、农技知识薄弱、田间服务不完整、农产…
阅读更多...
招商证券：知识型券商如何推动企业知识资产化管理

招商证券：知识型券商如何推动企业知识资产化管理

一百人的专家队伍&#xff0c;一百个重点知识地图&#xff0c;一百场专题知识讲座&#xff0c;一百个内部经典案例”&#xff0c;招商证券通过“四个一工程”推动了公司核心知识传承&#xff0c;快速提升了最佳实践传播周期和新知识产品响应时间。招商证券凭借在知识管理实践的…
阅读更多...
week27

week27

这周是磨难的一周不知道NT装了多少次系统&#xff0c;删除了多少数据好消息是把BIOS和ubuntu安装地很熟练了&#xff0c;而且经过爱上了心仪的Ubuntu23.04&#xff0c;就是她了坏消息是一个学期做的笔记全都没了&#xff0c;以后不好回忆了&#xff0c;好消息是不用考试了&…
阅读更多...
SpringBoot整合knife4j

SpringBoot整合knife4j

knife4j 文档地址&#xff1a;https://doc.xiaominfo.com/ knife4j是为Java MVC框架集成Swagger生成Api文档的增强解决方案。 Swagger介绍 前后端分离开发模式中&#xff0c;api文档是最好的沟通方式。 Swagger 是一个规范和完整的框架&#xff0c;用于生成、描述、调用和…
阅读更多...
Redis进阶底层原理-Cluster集群底层

Redis进阶底层原理-Cluster集群底层

Redis实现高可用的方案有很多中&#xff0c;先了解下高可用和分区的概念&#xff1a; 高可用是指系统在面对硬件故障、网络故障、软件错误等意外问题时&#xff0c;仍能给客户端提供正常的服务&#xff0c;尽量的减少服务的阻塞、终端现象。在高可用的方案中一般会采用冗余备份…
阅读更多...
i910980hk和 i9-10900K哪个好

i910980hk和 i9-10900K哪个好

由于i9-10900K是桌面处理器&#xff0c;基本不需要考虑节能和散热问题&#xff0c;因此默频下性能比10980HK高。 我的笔记本就是活动时8折抢购的https://list.jd.com/list.html? 英特尔 i9-10900K为 10 核 20 线程&#xff0c;主频 3.7GHz&#xff0c;睿频最高可达 5.3GHz&am…
阅读更多...
A14性能超酷睿i9，ARM终于超越了Intel

A14性能超酷睿i9，ARM终于超越了Intel

苹果最新发布的A14处理器性能比去年的A13提升了16%&#xff0c;而去年的A13处理器已与Intel的顶级PC处理器酷睿i9-10920X相当&#xff0c;如此一来A14处理器的性能应该已超过Intel的酷睿i9处理器。 如今推出的Geekbench5的分数作出了很大调整&#xff0c;故以去年的Geekbench4测…
阅读更多...
Gigabyte GA-Z790-UD i9-13900黑苹果efi引导文件

Gigabyte GA-Z790-UD i9-13900黑苹果efi引导文件

原文来源于黑果魏叔官网&#xff0c;转载需注明出处。 硬件型号驱动情况 主板Dell-Latitude-E7490 处理器13th Gen Intel i9-13900已驱动 内存32GB * 2&#xff08;DDR5-6000&#xff09;已驱动 硬盘Samsung SSD 970 EVO 1TB已驱动 显卡AMD Radeon RX 6900 XT已驱动 声卡…
阅读更多...
最新文章

Copyright @ 2022~2023