开发者

python实现邻接表转邻接矩阵

开发者 https://www.devze.com 2022-12-17 09:28 出处:网络 作者: Ming_Che
目录python邻接表转邻接矩阵图的存储—邻接矩阵与邻接表邻接矩阵邻接表入度与出度书面练习编程练习总结python邻接表转邻接矩阵
目录
  • python邻接表转邻接矩阵
  • 图的存储—邻接矩阵与邻接表
    • 邻接矩阵
    • 邻接表
    • 入度与出度
    • 书面练习
    • 编程练习
  • 总结

    python邻接表转邻接矩阵

    闲话少说,前段时间看到有同学问怎么把邻接表转成邻接矩阵,想了想做了一下,仅供参考。= =

    • _python 2.7 _
    • 包:networkX,numpy
    # coding:utf-8
    #将一个图,network转换为邻接矩阵
    import netwjsorkx 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然后按照空格分列就可以了。

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

    有向图最常见的存储方式有两种:邻接矩阵和邻接表。

    我们以这样一个图为例子演示这两种存储方式。

    python实现邻接表转邻接矩阵

    邻接矩阵

     假如有向图中有n个顶点,邻接矩阵是一个n*n的矩阵A,其元素A[i][j]的值为

     

    python实现邻接表转邻接矩阵

    上面例子的图的邻近矩阵如下:

    01234
    001100
    100010
    200010
    300001
    400000

    邻接表

    假如有向图中有n个顶点,邻接表是一个长度为n的数组,其索引为i的元素保存的是从顶点i可直接到达的顶点的列表

    上面例子的图的邻接表如下:

    0:12
    1:3
    2:3
    3:4
    4:

    入度与出度

    到达图中某个顶点的边的条数称为这个图的入度,从某个顶点出发的边的条数称为这个图的出度

    书面练习

    请给出以下几例图的邻接矩阵和邻接表。

    python实现邻接表转邻接矩阵

     

    python实现邻接表转邻接矩阵

    编程练习

    题目描述

    给定一个 n个顶点 m 条边的有向图。请以邻接矩阵和邻接表的形式输出这一张图。

    输入格式

    第一行输入两个正整数 n 和 m,表示图的顶点数和边数。顶点的编号为0 ~ n-1。

    第二行开始,往后 m 行,每行输入两个以空格隔开的正整数 u,v,表示从u出发有一条边直FZwLRgerUt接到达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>> bu开发者_JS培训ildAdjacentList(int n, List<int[]> edges) {
            List<List<Integephpr>> 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,http://www.devze.com 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();
            }
        }
    }

    总结

    以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。

    0

    精彩评论

    暂无评论...
    验证码 换一张
    取 消

    关注公众号