python實(shí)現(xiàn)鄰接表轉(zhuǎn)鄰接矩陣
python鄰接表轉(zhuǎn)鄰接矩陣
閑話少說(shuō),前段時(shí)間看到有同學(xué)問(wèn)怎么把鄰接表轉(zhuǎn)成鄰接矩陣,想了想做了一下,僅供參考。= =
- _python 2.7 _
- 包:networkX,numpy
# coding:utf-8 #將一個(gè)圖,network轉(zhuǎn)換為鄰接矩陣 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 能夠方便讀寫網(wǎng)絡(luò),并且寫成我們需要的各種格式。
最后生成的結(jié)果為 txt 格式,手動(dòng)導(dǎo)入excel然后按照空格分列就可以了。
圖的存儲(chǔ)—鄰接矩陣與鄰接表
有向圖最常見的存儲(chǔ)方式有兩種:鄰接矩陣和鄰接表。
我們以這樣一個(gè)圖為例子演示這兩種存儲(chǔ)方式。
鄰接矩陣
假如有向圖中有n個(gè)頂點(diǎn),鄰接矩陣是一個(gè)n*n的矩陣A,其元素A[i][j]的值為
上面例子的圖的鄰近矩陣如下:
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個(gè)頂點(diǎn),鄰接表是一個(gè)長(zhǎng)度為n的數(shù)組,其索引為i的元素保存的是從頂點(diǎn)i可直接到達(dá)的頂點(diǎn)的列表
上面例子的圖的鄰接表如下:
0: | 1 | 2 |
---|---|---|
1: | 3 | |
2: | 3 | |
3: | 4 | |
4: |
入度與出度
到達(dá)圖中某個(gè)頂點(diǎn)的邊的條數(shù)稱為這個(gè)圖的入度,從某個(gè)頂點(diǎn)出發(fā)的邊的條數(shù)稱為這個(gè)圖的出度
書面練習(xí)
請(qǐng)給出以下幾例圖的鄰接矩陣和鄰接表。
編程練習(xí)
題目描述
給定一個(gè) n個(gè)頂點(diǎn) m 條邊的有向圖。請(qǐng)以鄰接矩陣和鄰接表的形式輸出這一張圖。
輸入格式
第一行輸入兩個(gè)正整數(shù) n 和 m,表示圖的頂點(diǎn)數(shù)和邊數(shù)。頂點(diǎn)的編號(hào)為0 ~ n-1。
第二行開始,往后 m 行,每行輸入兩個(gè)以空格隔開的正整數(shù) u,v,表示從u出發(fā)有一條邊直接到達(dá)v。
輸出格式
首先輸出 n 行 n 列的矩陣,以空格隔開每一行之間的數(shù)表示鄰接矩陣。第 i 行第 j 列的數(shù)為 1 則表示從頂點(diǎn) i 出發(fā)有一條邊直接到達(dá) j ;若為 0 則表示沒(méi)有直接到達(dá)的邊。
然后空一行。
再往后輸出 n 行,按頂點(diǎn)編號(hào)從小到大順序。每一行首先先輸出一個(gè)整數(shù) d?,表示這個(gè)頂點(diǎn)的出度,再按照從小到大的順序,依次輸出從該頂點(diǎn)出發(fā)可直接到達(dá)的所有頂點(diǎn)。
輸入輸出樣例
輸入#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
請(qǐng)先嘗試自主編寫,再閱讀下面示例代碼
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(); } } }
總結(jié)
以上為個(gè)人經(jīng)驗(yàn),希望能給大家一個(gè)參考,也希望大家多多支持腳本之家。
相關(guān)文章
Python?tkinter庫(kù)繪圖實(shí)例分享
這篇文章主要給大家分享了Python?tkinter庫(kù)繪圖實(shí)例,主要分享實(shí)例有小房子繪制、彩色氣泡動(dòng)畫繪制內(nèi)容,需要的小伙伴可以參考一下,希望對(duì)你的學(xué)習(xí)有所幫助2022-04-04python3實(shí)現(xiàn)字符串的全排列的方法(無(wú)重復(fù)字符)
這篇文章主要介紹了python3實(shí)現(xiàn)字符串的全排列的方法(無(wú)重復(fù)字符),小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-07-07Python實(shí)現(xiàn)制作透明背景的電子印章
這篇文章主要為大家詳細(xì)介紹了如何利用Python語(yǔ)言實(shí)現(xiàn)制作透明背景的電子印章,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以嘗試一下2022-09-09淺析Django 接收所有文件,前端展示文件(包括視頻,文件,圖片)ajax請(qǐng)求
這篇文章主要介紹了Django 接收所有文件,前端展示文件(包括視頻,文件,圖片)ajax請(qǐng)求,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值 ,需要的朋友可以參考下2020-03-03使用Python實(shí)現(xiàn)tail的示例代碼
tail是一個(gè)常用的Linux命令, 它可以打印文件的后面n行數(shù)據(jù), 也能實(shí)時(shí)輸出文件的追加數(shù)據(jù)。本文就來(lái)用Python實(shí)現(xiàn)tail,感興趣的可以了解一下2023-03-03