最好的方式存儲在一個文本文件

Question

我的問題涉及到創建一個有向圖，檢測是否通過與包含圖形的文本文件，如果它是獨一無二的，其附加到文件獨特。在這種情況下使用圖的最佳表示是什麼？ 我使用Python和我將使用蠻力，以檢查是否圖是同構的，因爲該圖是小的，並且有一定的限制。

Answer 1

假設是這樣的曲線是如何表示你可能是確定用一個簡單的CSV格式，其中一條線是一條邊的簡單情況和療法的圖形之間的一些分離器，如：

graph_4345345 
A,B 
B,C 
C,E 
E,B 
graph_3234766 
F,D 
B,C 

等。

然後，您可以利用https://docs.python.org/3/library/csv.html

Answer 2

我想這取決於你如何去表現你的圖作爲數據結構。

兩個最公知的圖形表示爲數據結構有：

1. 鄰接矩陣
2. 鄰接列表

鄰接矩陣

對於一個圖表，|V|頂點，一個鄰接矩陣是0和1的一個|V|X|V|矩陣，其中行i和列j中的條目是1，當且僅當邊緣（i，j）在圖中。如果你想表示邊權重，把它排在我列Ĵ條目，並保留一個特殊值（可能爲空）來表示一個缺席邊緣。 隨着鄰接矩陣，我們可以找出邊緣是否存在在固定時間內，僅通過查找在矩陣中的對應條目。例如，如果鄰接矩陣被命名爲圖，則我們可以查詢邊緣（I，J）是否處於圖形通過查看graph[i][j]。

對於無向圖，鄰接矩陣是對稱的：行我，柱Ĵ條目爲1當且僅當該行Ĵ，柱我條目是1。對於一個有向圖，鄰接矩陣不需要是對稱的。

---

鄰接列表

表示與鄰接列表的圖表結合鄰接矩陣與邊列表。對於每個頂點，存儲一個頂點數組。我們通常有一個| V |的數組鄰接列表，每個頂點有一個鄰接列表。

在鄰接表頂點編號不需要出現在任何特定的順序，但它往往是方便的將它們列在遞增的順序。

我們可以在恆定時間內到達每個頂點的鄰接列表，因爲我們只需要索引到一個數組中。要找出一個邊緣（I，J）是否出現在圖中，我們去我的鄰接表在不斷的時間，然後找Ĵ在我的鄰接表。

在無向圖中，頂點Ĵ是在頂點我的鄰接表當且僅當我是Ĵ的鄰接表。如果圖形是加權的，則每個鄰接列表中的每個項目是一個兩項目數組或一個對象，給出頂點數和邊權重。

---

導出到文件

如何將數據結構導出到文本文件？那麼，這取決於您如何閱讀文本文件並將其導入到您決定使用的數據結構中。

如果我要這樣做，我可能會嘗試以最簡單的方式轉儲它，以便以後知道如何讀取並解析它回到數據結構。

Answer 3

有一種標準的基於文本的格式，名爲DOT，它允許您使用有向圖和無向圖，並且可以讓您使用各種不同的庫來處理圖形。值得注意的是graphviz它允許您讀取和寫入DOT文件，並使用matplotlib以圖形方式繪製它們。

Answer 4

鄰接表

商店圖表在這種格式：

第一行包含兩個整數：N（數量的節點）和E（邊數）。 然後E行跟隨每個包含兩個整數U和V。每一行代表一個邊（邊從U戈林到V）

這是怎樣的四個節點週期圖形看起來像：

4 4 
1 2 
2 3 
3 4 
4 1 

爲了表示圖表在Python中，你可以用列表的列表。

N, E = input()  # input will take two comma separated integers 

graph = [[] for x in range(N+1)] # initially no edge is inserted 

for x in range(E): #to read E edges 
    u, v = input() 

    # inserting edge u->v 
    graph[u].append(v)