图的邻接矩阵和邻接表转换

邻接矩阵和邻接表是两种表示图的方式，它们可以相互转换。下面是它们之间的转换方法：

1. 邻接矩阵转邻接表

对于一个有 $n$ 个节点的图，邻接矩阵是一个 $n \times n$ 的矩阵 $M$，其中 $M_{i,j}$ 表示节点 $i$ 和节点 $j$ 之间是否有边。邻接表是一个长度为 $n$ 的链表数组，每个链表存储与该节点相邻的节点。

具体转换方法如下：

- 对于每个节点 $i$，创建一个链表 $L_i$。
- 对于邻接矩阵中的每个元素 $M_{i,j}$，如果 $M_{i,j}=1$，则将节点 $j$ 加入链表 $L_i$ 中。
- 最终得到的链表数组就是邻接表。

2. 邻接表转邻接矩阵

对于一个有 $n$ 个节点的图，邻接表是一个长度为 $n$ 的链表数组，每个链表存储与该节点相邻的节点。邻接矩阵是一个 $n \times n$ 的矩阵 $M$，其中 $M_{i,j}$ 表示节点 $i$ 和节点 $j$ 之间是否有边。

具体转换方法如下：

- 创建一个 $n \times n$ 的矩阵 $M$，初始值全部为 $0$。
- 对于每个节点 $i$，遍历链表 $L_i$ 中的每个节点 $j$，将 $M_{i,j}$ 设为 $1$。
- 最终得到的矩阵 $M$ 就是邻接矩阵。

相关问题

邻接矩阵和邻接表的转换

邻接矩阵和邻接表是两种常见的图的存储方式。邻接矩阵是一个二维数组，其中行和列分别表示图中的节点，数组中的值表示节点之间的边的权重。而邻接表则是由每个节点的邻居列表组成的数组，每个邻居列表包含该节点的所有邻居节点及其对应的边的权重。

邻接矩阵和邻接表的转换可以通过以下步骤完成：
1. 邻接矩阵转邻接表：对于每个节点，遍历其所在行的所有列，如果该列的值不为0，则将该列所对应的节点及其权重添加到该节点的邻居列表中。
2. 邻接表转邻接矩阵：创建一个空的邻接矩阵，对于每个节点，遍历其邻居列表，将该节点与其邻居节点之间的边的权重添加到邻接矩阵中对应的位置。

下面是一个示例代码，将邻接矩阵转换成邻接表并输出，以及将邻接表转换成邻接矩阵并输出：

邻接矩阵转邻接表：

int[][] adjMatrix = {{0, 2, 0, 1}, {0, 0, 0, 4}, {3, 0, 0, 0}, {0, 0, 2, 0}};
List<List<int[]>> adjList = new ArrayList<>();
for (int i = 0; i < adjMatrix.length; i++) {
    List<int[]> neighbors = new ArrayList<>();
    for (int j = 0; j < adjMatrix[i].length; j++) {
        if (adjMatrix[i][j] != 0) {
            neighbors.add(new int[]{j, adjMatrix[i][j]});
        }
    }
    adjList.add(neighbors);
}
System.out.println(adjList);

输出结果为：[[[1, 2], [3, 1]], [[3, 4]], [[0, 3]], [[2, 2]]]

邻接表转邻接矩阵：

List<List<int[]>> adjList = new ArrayList<>();
adjList.add(Arrays.asList(new int[]{1, 2}, new int[]{3, 1}));
adjList.add(Arrays.asList(new int[]{3, 4}));
adjList.add(Arrays.asList(new int[]{0, 3}));
adjList.add(Arrays.asList(new int[]{2, 2}));
int[][] adjMatrix = new int[adjList.size()][adjList.size()];
for (int i = 0; i < adjList.size(); i++) {
    for (int[] neighbor : adjList.get(i)) {
        adjMatrix[i][neighbor[0]] = neighbor[1];
    }
}
System.out.println(Arrays.deepToString(adjMatrix));

输出结果为：[[0, 2, 0, 1], [0, 0, 0, 4], [3, 0, 0, 0], [0, 0, 2, 0]]

matlab 将邻接矩阵转换成邻接表

邻接矩阵是图论中常用的一种表示图结构的方法，而邻接表则是另一种常见的形式。在Matlab中，我们可以使用一些简单的代码将邻接矩阵转换成邻接表。

首先，我们需要创建一个邻接矩阵。我们可以使用Matlab的矩阵表示方法，其中矩阵的行和列代表的是图中的节点，而矩阵中的元素则表示节点之间是否存在边。边存在时，该元素的值为1，边不存在时，该元素的值为0。

接下来，我们要创建一个空的邻接表。在Matlab中，我们可以使用cell数组来实现邻接表。每个节点对应一个cell，cell中存放的是与该节点相邻的节点。

然后，我们可以使用一个for循环来遍历邻接矩阵中的每个元素。对于邻接矩阵中的非零元素，我们可以将其对应的节点添加到邻接表中的对应节点cell中。

最后，我们可以输出邻接表来查看转换结果。

以下是用Matlab代码实现邻接矩阵转换成邻接表的过程：

% 创建邻接矩阵
adjacencyMatrix = [0 1 1; 1 0 0; 1 0 0];

% 获取节点数量
numNodes = size(adjacencyMatrix, 1);

% 创建空的邻接表
adjacencyList = cell(numNodes, 1);

% 遍历邻接矩阵
for i = 1:numNodes
    for j = 1:numNodes
        if adjacencyMatrix(i, j) == 1
            % 将相邻节点添加到邻接表中
            adjacencyList{i} = [adjacencyList{i} j];
        end
    end
end

% 输出邻接表
disp('邻接表：');
for i = 1:numNodes
    disp(['节点 ' num2str(i) ': ' num2str(adjacencyList{i})]);
end

运行上述代码后，将会在命令窗口中输出邻接表，展示邻接矩阵转换的结果。