日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

python實現鄰接表轉鄰接矩陣_python

作者：Ming_Che ? 更新時間： 2023-01-17 編程語言

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]的值為

?A[i][j]=\begin{cases} 1 & \text{ if there is an edge from i to j } \\ 0 & \text{ if there is no edge from i to j } \end{cases}

上面例子的圖的鄰近矩陣如下：

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

鄰接表

假如有向圖中有n個頂點，鄰接表是一個長度為n的數組，其索引為i的元素保存的是從頂點i可直接到達的頂點的列表

上面例子的圖的鄰接表如下：

0： 1 2
1： 3
2： 3
3： 4
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();
        }
    }
}

總結

原文鏈接：https://blog.csdn.net/qq_39290880/article/details/89078105

欄目分類
最近更新