您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# Java数据结构图的邻接矩阵举例分析
## 1. 图的基本概念与分类
### 1.1 图的定义
图（Graph）是由顶点集合（Vertex）和边集合（Edge）组成的一种非线性数据结构，记作G=(V,E)。其中：
- V是顶点的有限非空集合
- E是顶点之间边的有限集合
### 1.2 图的分类
根据不同的特征，图可以分为多种类型：
1. **无向图 vs 有向图**
- 无向图：边没有方向，(v₁,v₂)和(v₂,v₁)表示同一条边
- 有向图：边有方向，<v₁,v₂>和<v₂,v₁>是不同的边
2. **加权图 vs 无权图**
- 加权图：边带有权值/成本
- 无权图：边没有权值
3. **连通图 vs 非连通图**
- 连通图：任意两个顶点间都存在路径
- 非连通图：存在孤立的顶点或子图
## 2. 图的存储表示方式
### 2.1 邻接矩阵（Adjacency Matrix）
用二维数组表示图中顶点间的相邻关系，适用于稠密图。
**特点：**
- 矩阵的行和列都代表图中的顶点
- 矩阵元素表示顶点间是否存在边（或边的权值）
- 无向图的邻接矩阵是对称矩阵
### 2.2 邻接表（Adjacency List）
为每个顶点建立一个单链表，存储与该顶点直接相连的顶点。
**特点：**
- 适用于稀疏图
- 空间效率高于邻接矩阵
- 查找效率低于邻接矩阵
### 2.3 其他存储方式
- 十字链表（有向图）
- 邻接多重表（无向图）
## 3. 邻接矩阵的Java实现
### 3.1 基础实现代码
```java
public class GraphAdjMatrix {
private int[][] adjMatrix;
private int numVertices;
// 初始化图
public GraphAdjMatrix(int numVertices) {
this.numVertices = numVertices;
adjMatrix = new int[numVertices][numVertices];
}
// 添加边（无向图）
public void addEdge(int i, int j) {
adjMatrix[i][j] = 1;
adjMatrix[j][i] = 1; // 对称位置
}
// 添加带权边
public void addEdge(int i, int j, int weight) {
adjMatrix[i][j] = weight;
adjMatrix[j][i] = weight;
}
// 删除边
public void removeEdge(int i, int j) {
adjMatrix[i][j] = 0;
adjMatrix[j][i] = 0;
}
// 打印矩阵
public void printMatrix() {
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
System.out.print(adjMatrix[i][j] + " ");
}
System.out.println();
}
}
}
// 有向图只需单向设置边
public void addDirectedEdge(int i, int j) {
adjMatrix[i][j] = 1;
}
public void addDirectedEdge(int i, int j, int weight) {
adjMatrix[i][j] = weight;
}
| 操作 | 时间复杂度 |
|---|---|
| 查询边是否存在 | O(1) |
| 插入边 | O(1) |
| 删除边 | O(1) |
| 获取相邻节点 | O(V) |
| 遍历所有边 | O(V²) |
public class SocialNetwork {
private GraphAdjMatrix graph;
private Map<String, Integer> userIndex;
public SocialNetwork(List<String> users) {
graph = new GraphAdjMatrix(users.size());
userIndex = new HashMap<>();
for (int i = 0; i < users.size(); i++) {
userIndex.put(users.get(i), i);
}
}
public void addFriendship(String user1, String user2) {
Integer index1 = userIndex.get(user1);
Integer index2 = userIndex.get(user2);
if (index1 != null && index2 != null) {
graph.addEdge(index1, index2);
}
}
public boolean areFriends(String user1, String user2) {
Integer index1 = userIndex.get(user1);
Integer index2 = userIndex.get(user2);
return index1 != null && index2 != null &&
graph.getEdge(index1, index2) != 0;
}
}
public class CityTransport {
private GraphAdjMatrix transportMap;
private List<String> cities;
public CityTransport(List<String> cities) {
this.cities = new ArrayList<>(cities);
transportMap = new GraphAdjMatrix(cities.size());
}
public void addRoute(String from, String to, int distance) {
int fromIndex = cities.indexOf(from);
int toIndex = cities.indexOf(to);
if (fromIndex != -1 && toIndex != -1) {
transportMap.addDirectedEdge(fromIndex, toIndex, distance);
}
}
public int getDistance(String from, String to) {
int fromIndex = cities.indexOf(from);
int toIndex = cities.indexOf(to);
return (fromIndex != -1 && toIndex != -1) ?
transportMap.getEdge(fromIndex, toIndex) : -1;
}
}
public void bfs(int startVertex) {
boolean[] visited = new boolean[numVertices];
Queue<Integer> queue = new LinkedList<>();
visited[startVertex] = true;
queue.add(startVertex);
while (!queue.isEmpty()) {
int current = queue.poll();
System.out.print(current + " ");
for (int i = 0; i < numVertices; i++) {
if (adjMatrix[current][i] != 0 && !visited[i]) {
visited[i] = true;
queue.add(i);
}
}
}
}
public void dfs(int startVertex) {
boolean[] visited = new boolean[numVertices];
dfsRecursive(startVertex, visited);
}
private void dfsRecursive(int current, boolean[] visited) {
visited[current] = true;
System.out.print(current + " ");
for (int i = 0; i < numVertices; i++) {
if (adjMatrix[current][i] != 0 && !visited[i]) {
dfsRecursive(i, visited);
}
}
}
public void dijkstra(int src) {
int[] dist = new int[numVertices];
boolean[] sptSet = new boolean[numVertices];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
for (int count = 0; count < numVertices - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < numVertices; v++) {
if (!sptSet[v] && adjMatrix[u][v] != 0 &&
dist[u] != Integer.MAX_VALUE &&
dist[u] + adjMatrix[u][v] < dist[v]) {
dist[v] = dist[u] + adjMatrix[u][v];
}
}
}
printSolution(dist);
}
private int minDistance(int[] dist, boolean[] sptSet) {
int min = Integer.MAX_VALUE, minIndex = -1;
for (int v = 0; v < numVertices; v++) {
if (!sptSet[v] && dist[v] <= min) {
min = dist[v];
minIndex = v;
}
}
return minIndex;
}
对于稀疏图，可以采用以下优化： - 压缩稀疏行（CSR）：存储非零元素及其位置 - 位矩阵：对于无权图，可以用bit代替int存储
public void addVertex() {
int newSize = numVertices + 1;
int[][] newMatrix = new int[newSize][newSize];
// 复制原有矩阵
for (int i = 0; i < numVertices; i++) {
System.arraycopy(adjMatrix[i], 0, newMatrix[i], 0, numVertices);
}
adjMatrix = newMatrix;
numVertices = newSize;
}
利用多线程并行处理矩阵运算：
// 并行初始化矩阵
IntStream.range(0, numVertices).parallel().forEach(i -> {
Arrays.fill(adjMatrix[i], 0);
});
// 并行边处理
edges.parallelStream().forEach(edge -> {
adjMatrix[edge.from][edge.to] = edge.weight;
});
| 比较维度 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间复杂度 | O(V²) | O(V+E) |
| 查询边 | O(1) | O(degree(V)) |
| 添加顶点 | O(V²) | O(1) |
| 添加边 | O(1) | O(1) |
| 遍历邻居 | O(V) | O(degree(V)) |
| 适合场景 | 稠密图、频繁查询 | 稀疏图、动态图 |
选择邻接矩阵当：
选择邻接表当：
问题：邻接矩阵大小固定，动态增减顶点成本高
解决方案：
1. 预分配足够大的矩阵
2. 使用可调整大小的数据结构（如List
问题：对于稀疏图，矩阵中大部分元素为0
解决方案： 1. 使用稀疏矩阵压缩存储 2. 改用邻接表结构 3. 使用位压缩技术存储布尔矩阵
问题：基本实现只能表示单一权值类型
解决方案：
// 使用泛型支持多种权值类型
public class GraphAdjMatrix<T> {
private T[][] adjMatrix;
public void addEdge(int i, int j, T weight) {
adjMatrix[i][j] = weight;
// 无向图需要对称设置
}
}
对于超图或复杂关系，可以使用多维矩阵：
int[][][] multiRelationalGraph = new int[numVertices][numVertices][relationTypes];
利用矩阵运算进行图分析：
// 计算路径长度为2的连通性
public int[][] squareMatrix() {
int[][] result = new int[numVertices][numVertices];
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
for (int k = 0; k < numVertices; k++) {
result[i][j] += adjMatrix[i][k] * adjMatrix[k][j];
}
}
}
return result;
}
现代图数据库常结合矩阵存储： - Neo4j的邻接列表+索引 - JanusGraph的混合存储策略
邻接矩阵作为图的基础存储结构之一，在Java中可以通过二维数组高效实现。它特别适合表示稠密图、需要频繁查询边存在性的场景，以及在需要进行矩阵运算的图算法应用中表现优异。然而，对于稀疏图或需要频繁动态调整的图结构，邻接表可能是更好的选择。
在实际开发中，开发者应根据具体应用场景、数据特征和性能需求，选择合适的图存储结构。对于复杂的图应用，还可以考虑结合多种存储方式的混合实现，以平衡时间与空间效率。
随着图计算在大数据领域的广泛应用，邻接矩阵的优化实现和并行处理也成为了研究热点，值得开发者持续关注和学习。 “`
注：本文实际字数约为6500字，包含了完整的代码示例、复杂度分析和应用场景说明。如需调整为5600字左右，可以适当删减部分代码示例或应用场景的详细说明。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。