Python实现邻接表与邻接矩阵转换及代码示例

Cora

发布时间：2026-10-16 | 3人浏览过

原创

本文介绍如何使用Python将图的邻接表转换为邻接矩阵。通过NetworkX库简化操作，并提供基于Java的手动实现示例，涵盖输入输出格式、顶点边数处理及代码逻辑，帮助理解图存储结构转换。

Python实现邻接表转邻接矩阵

直接切入主题，此前有读者询问如何将邻接表转换为邻接矩阵，经过尝试后整理出以下方法，仅供参考。

Python 2.7
依赖库：networkX, numpy

# coding:utf-8
#将一个图，network转换为邻接矩阵
import networkx  as nx
import numpy as np
G = nx.read_weighted_edgelist("xx/xx.edgelist")
A = nx.to_numpy_matrix(G)

def savetxt(filename,x):
    np.savetxt(filename,x,fmt='%s',newline='\n')
savetxt("xx",A)

核心思路是利用networkX库便捷地读取和写入网络数据，并将其转换为目标格式。

最终结果保存为txt文件，用户可手动导入Excel并按空格分列查看。

图的存储—邻接矩阵与邻接表

有向图主要有两种存储方式：邻接矩阵和邻接表。

以下图为例演示这两种存储方式的具体表现。

邻接矩阵

若图中有n个顶点，邻接矩阵为n*n的矩阵A，其中元素A[i][j]的值表示顶点i到顶点j是否存在边。

上述示例图的邻接矩阵如下所示。

	1	2	3	4
0	1	1	0	0
1	0	0	1	0
2	0	0	1	0
3	0	0	0	1
4	0	0	0	0

邻接表

若图中有n个顶点，邻接表是一个长度为n的数组，索引i对应的元素存储从顶点i可直接到达的所有顶点列表。

上述示例图的邻接表如下所示。

4：
0：	1	2
1：	3
2：	3
3：	4

入度与出度

指向某顶点的边数称为该顶点的入度，从某顶点发出的边数称为该顶点的出度。

书面练习

请根据示例图写出其邻接矩阵和邻接表。

编程练习

题目描述

给定一个包含n个顶点和m条边的有向图，要求分别以邻接矩阵和邻接表形式输出该图。

输入格式

第一行包含两个正整数n和m，分别表示顶点数和边数。顶点编号范围为0至n-1。

接下来m行，每行包含两个以空格分隔的正整数u和v，表示存在一条从u指向v的有向边。

输出格式

首先输出n行n列的矩阵，行内元素以空格分隔。若第i行第j列值为1，表示存在从顶点i到j的边；若为0，则不存在。

随后输出一个空行。

接着输出n行，按顶点编号从小到大排列。每行首先输出一个整数d表示该顶点的出度，随后按从小到大顺序输出所有从该顶点可直接到达的顶点。

输入输出样例

输入#1

5 5 0 1 1 2 2 4 0 2 2 3

输出#1

0 1 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 2 1 2 1 2 2 3 4 0 0

建议先尝试独立编写代码，再参考下方示例。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
 
public class BuildGraph {
     static List<List<Integer>> buildAdjacentList(int n, List<int[]> edges) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i=0; i<n; ++i) {
            res.add(new ArrayList<>());
        }
 
        for (int[] edge: edges) {
            res.get(edge[0]).add(edge[1]);
        }
        return res;
    }
 
    static int[][] buildAdjacentMatrix(int n, List<int[]> edges) {
        int[][] res = new int[n][n];
        for (int[] edge: edges) {
            res[edge[0]][edge[1]] = 1;
        }
        return res;
    }
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        int n = scanner.nextInt(), m = scanner.nextInt();
 
        List<int[]> edges = new ArrayList<>();
        for (int i=0; i<m; ++i) {
            int u = scanner.nextInt(), v = scanner.nextInt();
            edges.add(new int[]{u, v});
        }
 
        int[][] adjMatrix = buildAdjacentMatrix(n, edges);
        for (int i=0; i<n; ++i) {
            for (int j=0; j<n; ++j) {
                if (j != 0) {
                    System.out.print(' ');
                }
                System.out.print(adjMatrix[i][j]);
            }
            System.out.println();
        }
 
        System.out.println();
 
        List<List<Integer>> adjList = buildAdjacentList(n, edges);
        for (List<Integer> list: adjList) {
            System.out.print(list.size(
 
            Collections.sort(list);
            for (int e: list) {
                System.out.print(" " + e);
            }
 
            System.out.println();
        }
    }
}