首页 / 算法 / Java数据结构与算法之图
Java数据结构与算法之图
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Java数据结构与算法之图,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1951字,纯文字阅读大概需要3分钟。
内容图文
![Java数据结构与算法之图](/upload/InfoBanner/zyjiaocheng/628/b51b1a8d286a41ebacaca7d5fa53f44d.jpg)
六、图
1. 图基本介绍
当我们需要表示多对多的关系时,这里我们就用到了图。
1.1 图的举例说明
图是一种数据结构,其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。结点也可以称为顶点。
1.2 图的常用概念
1)顶点(vertex)
2)边(edge)
3)路径
4)无向图
5)有向图
6)带权图
1.3 图的表示方式
1.3.1 邻接矩阵
邻接矩阵是表示图形中顶点之间相邻关系的矩阵,对于n个顶点的图而言,矩阵是的row和col表示的是1....n个点。
1.3.2 邻接表
1)邻接矩阵需要为每个顶点都分配n个边的空间,其实有很多边都是不存在,会造成空间的一定损失。
2)邻接表的实现只关心存在的边,不关心不存在的边。因此没有空间浪费,邻接表由数组+链表组成。
1.4 图的快速入门案例
思路
(1)存储顶点使用ArrayList
(2)保存矩阵int[][]edges
代码实现
public class Graph {
private ArrayList<Integer> vertexList; // 创建指定节点长度的数组
private int[][] edges; // 存储边的数据
private int edgesNum; // 边的数目
private int weight; // 权重
public static void main(String[] args) {
int n = 8;
int[] vertexs = {1,2,3,4,5,6,7,8};
Graph graph = new Graph(n);
for (int vertex:vertexs) {
graph.insertVertex(vertex);
}
graph.insertEdge(0,1,1);
graph.insertEdge(0,2,1);
graph.insertEdge(1,3,1);
graph.insertEdge(1,4,1);
graph.insertEdge(3,7,1);
graph.insertEdge(4,7,1);
graph.insertEdge(2,5,1);
graph.insertEdge(2,6,1);
graph.insertEdge(5,6,1);
graph.showGraph();
}
public Graph(int n) {
vertexList = new ArrayList<Integer>(n);
edges = new int[n][n];
}
// 返回节点的个数
public int numOfVertex() {
return vertexList.size();
}
// 显示图中的矩阵
public void showGraph() {
for (int[] edge:edges) {
System.out.println(Arrays.toString(edge));
}
}
// 得到边的数目
public int numOfEdges() {
return edgesNum;
}
// 返回节点下标i对应的数组
public int showVertexList(int i) {
return vertexList.get(i);
}
// 返回v1、v2的权值
public int getWeightOfEdge(int v1, int v2) {
return edges[v1][v2];
}
// 插入节点
public void insertVertex(Integer vertex) {
vertexList.add(vertex);
}
// 添加边
public void insertEdge(int v1, int v2, int weight) {
edges[v1][v2] = weight;
edges[v2][v1] = weight;
edgesNum++;
}
}
结果打印:
内容总结
以上是互联网集市为您收集整理的Java数据结构与算法之图全部内容,希望文章能够帮你解决Java数据结构与算法之图所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。