带权有向图的邻接矩阵转为邻接表 java
时间: 2023-09-03 17:11:01 浏览: 38
好的,我可以帮你回答这个问题。
首先,我们可以定义一个类来表示图中的每个节点,例如:
```java
class Node {
int to; // 表示该节点指向的节点
int weight; // 表示该节点和指向的节点之间的权重
public Node(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
```
然后,我们可以使用一个 ArrayList 数组来存储每个节点所连向的节点列表,例如:
```java
List<Node>[] adjList = new ArrayList[n]; // n 表示节点的个数
for (int i = 0; i < n; i++) {
adjList[i] = new ArrayList<Node>();
}
// 假设邻接矩阵为 matrix[][]
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] != 0) { // 如果节点 i 和 j 之间有边
adjList[i].add(new Node(j, matrix[i][j])); // 将 j 加入到 i 的邻接表中
}
}
}
```
这样,我们就可以将带权有向图的邻接矩阵转换为邻接表了。希望能帮到你!
相关问题
有向图的邻接矩阵和邻接表存储结构
有向图的邻接矩阵和邻接表存储结构是用于表示有向图中顶点之间相邻关系的两种方法。
1. 邻接矩阵存储结构:
有向图的邻接矩阵是一个n×n的方阵,其中n为图中顶点的个数。对于有向图中的每一条边(i,j),如果存在,则在邻接矩阵中第i行第j列的位置上标记为1,否则标记为0。如果有权值,则在对应位置上存储权值。邻接矩阵存储结构的空间复杂度为O(n^2)。
2. 邻接表存储结构:
邻接表是由一个一维数组和若干个链表组成,数组中的每个元素表示一个顶点,每个顶点vi的所有邻接点构成一个单链表,链表中的每个元素表示vi的一个邻接点。邻接表存储结构的空间复杂度为O(n+e),其中e为边的个数。
下面是Python代码示例:
```python
# 邻接矩阵存储结构
class DirectedGraph:
def __init__(self, vertex_num):
self.vertex_num = vertex_num
self.adj_matrix = [[0] * vertex_num for i in range(vertex_num)]
def add_edge(self, start, end, weight=1):
self.adj_matrix[start][end] = weight
# 邻接表存储结构
class DirectedGraph:
def __init__(self, vertex_num):
self.vertex_num = vertex_num
self.adj_list = [[] for i in range(vertex_num)]
def add_edge(self, start, end, weight=1):
self.adj_list[start].append((end, weight))
```
java 给定一个带权有向图的邻接矩阵存储结构g,创建对应的邻接表存储结构G
好的,这里是 Java 代码实现:
```java
import java.util.*;
public class Graph {
private int n; // 图中节点的个数
private ArrayList<ArrayList<Pair<Integer, Integer>>> adjList; // 邻接表
public Graph(int[][] g) {
n = g.length;
adjList = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
ArrayList<Pair<Integer, Integer>> neighbors = new ArrayList<>();
for (int j = 0; j < n; j++) {
if (g[i][j] != 0) {
neighbors.add(new Pair<>(j, g[i][j]));
}
}
adjList.add(neighbors);
}
}
public void printGraph() {
for (int i = 0; i < n; i++) {
System.out.print("节点 " + i + " 的邻居是: ");
for (Pair<Integer, Integer> neighbor : adjList.get(i)) {
System.out.print("(" + neighbor.getKey() + ", " + neighbor.getValue() + ") ");
}
System.out.println();
}
}
}
```
其中,`Pair` 是 Java 中的一个泛型类,用于封装一对数据。`Pair<Integer, Integer>` 表示一个包含两个整型的元组,第一个整型表示邻居节点的编号,第二个整型表示边的权值。`ArrayList` 是 Java 中的动态数组,它可以存储任意类型的数据,这里用它来存储邻居节点列表。`adjList` 是一个 `ArrayList` 的数组,每个元素是一个邻居节点列表。
在构造函数中,我们首先获取邻接矩阵的大小,并初始化邻接表数组。然后遍历邻接矩阵,对于每个非零元素,我们将其加入到对应节点的邻居列表中。
最后,我们提供了一个 `printGraph` 方法,用于输出邻接表。