Java数据结构与算法:邻接矩阵和邻接表
Java数据结构与算法:邻接矩阵和邻接表
大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿!
什么是邻接矩阵和邻接表?
在图的表示中,邻接矩阵和邻接表是两种常见的方式,用于表示图中节点之间的关系。
1. 邻接矩阵
邻接矩阵是一个二维数组,其中的元素a[i][j]表示节点i到节点j是否有边。对于有权图,元素值可能表示权重。
2. 邻接表
邻接表是由节点的链表组成,每个节点的链表存储该节点相邻的节点。对于有权图,链表节点中可能包含权重信息。
邻接矩阵的Java实现
public class AdjacencyMatrixGraph {
private int V; // 节点数
private int[][] adjMatrix; // 邻接矩阵
public AdjacencyMatrixGraph(int v) {
V = v;
adjMatrix = new int[v][v];
}
// 添加边
public void addEdge(int v, int w, int weight) {
adjMatrix[v][w] = weight;
// 如果是无向图,还需将下面这行取消注释
// adjMatrix[w][v] = weight;
}
}
邻接表的Java实现
import java.util.LinkedList;
// 以邻接表表示的有向图
public class AdjacencyListGraph {
private int V; // 节点数
private LinkedList<Integer>[] adjList; // 邻接表
public AdjacencyListGraph(int v) {
V = v;
adjList = new LinkedList[v];
for (int i = 0; i < v; ++i)
adjList[i] = new LinkedList<>();
}
// 添加边
public void addEdge(int v, int w) {
adjList[v].add(w);
// 如果是无向图,还需将下面这行取消注释
// adjList[w].add(v);
}
}
邻接矩阵和邻接表的选择
- 邻接矩阵: 适用于稠密图,即边的数量接近节点数量的平方。
- 邻接表: 适用于稀疏图,即边的数量远小于节点数量的平方。
总结
邻接矩阵和邻接表是图的两种基本表示方法,选择哪种取决于图的特性。在实际应用中,需要根据图的密度和算法的需求来灵活选择。希望通过这篇文章,大家对邻接矩阵和邻接表有了清晰的认识。在后续的文章中,我们将深入讨论图的遍历、最短路径等算法。
原文地址:https://blog.csdn.net/weixin_44626980/article/details/135737171
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!