Pythonデータ構造の図基礎
Pythonデータ構造の図基礎
何が図ですかは多対多の関係を表しています. の頂点セットは、通常、頂点セット をVで表しています.の一群の辺は、通常E(Edge)で辺の集合を表し、辺が頂点のペアであり、向辺の有無と向辺の有無に分けられる.
図の作成
隣接行列 コード 結果 は、隣接行列を用いて図構造を実現し、頂点間の関係をより直感的に理解することができ、対応する頂点の出度と入度を良好に計算することができると結論したが、図なしにおいては隣接行列の使用は、2つの頂点間の2つのエッジ関係を同時に保存し、記憶が浪費されるので、一次元リストの間で記憶し、半分の記憶関係を減らしたり、隣接テーブルを使うことができます. 隣接表コード 結果 は、pythonでは辞書を使って図の隣接表の形を実現できると結論した.これに対しては、どの頂点のすべての隣接点を比較的便利に検索することができ、まばらな図(点が多い側が少ない)が記憶空間を占める面倒を減らし、直観的に頂点となる出度を計算することができる(図がある). 絵の遍歴
DFS(深さ優先検索)
DFSの実装プロセスは、ツリーの最初のシーケンス番号と同じであり、DFSの実装過程では、対応する頂点アクセス標識を設定する必要があります.すでに訪問したノードはアクセスしていません.プロセスを実現するために最も重要なのは、状態のトレースであり、再帰を使用することができます.アルゴリズムは分かりやすいです.一つの道は黒に行きます.だめなら撤退します.もう歩いていません.繰り返します.コード BFS(広さ優先検索素)
BFSは木の階層巡回に相当し、キューを使って頂点を保存して検索することができ、後に先進的に出た頂点の有効辺頂点を検索し、検索したものはもう検索しないので、頂点の検索状態を識別します.コード 参照
検索思想——DFS&BFS(基礎編)
隣接表
データ構造とアルゴリズム–図を一歩ずつ持って、Pythonで図の深さ遍歴と広さを優先的にPythonを経由して、図の深さ遍歴と広さ優先度を実現します.DFSとBFS過程を詳しく説明します.
何が図ですか
図の作成
隣接行列
class Graph:
""" """
def __init__(self, n):
self.vertex_list = []
self.edges = [[0 for i in range(n)] for j in range(n)] #
self.num_of_edges = 0 #
def get_num_of_vertex(self):
""" """
return len(self.vertex_list)
def get_val_by_index(self, index):
""" """
return self.vertex_list[index]
def get_wight(self, v1, v2):
""" """
return self.edges[v1][v2]
def show_graph(self):
for col in self.edges:
print(col)
def insert_edge(self, v1, v2, weight):
""" """
self.edges[v1][v2] = weight
self.edges[v2][v1] = weight
self.num_of_edges += 1
def insert_vertex(self, vertex):
""" """
self.vertex_list.append(vertex)
if __name__ == "__main__":
graph = Graph(5)
print(" ：")
vertex_val = ["A", "B", "C", "D", "E"]
for vertex in vertex_val:
graph.insert_vertex(vertex)
graph.show_graph()
graph.insert_edge(1, 2, 5)
graph.insert_edge(2, 4, 6)
graph.insert_edge(3, 1, 4)
graph.insert_edge(2, 2, 5)
print(" ：")
graph.show_graph()
：
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
：
[0, 0, 0, 0, 0]
[0, 0, 5, 4, 0]
[0, 5, 5, 0, 6]
[0, 4, 0, 0, 0]
[0, 0, 6, 0, 0]
class Vertex:
""" """
def __init__(self, key):
self.id = key
self.connectedTo = {}
def add_neighbor(self, nbr, weight):
self.connectedTo[nbr] = weight
def __str__(self):
return str(self.id) + " connected to " + str([x.id for x in self.connectedTo])
def get_connections(self):
return self.connectedTo.keys()
def get_id(self):
return self.id
def get_weight(self, nbr):
return self.connectedTo[nbr]
class Graph:
""" """
def __init__(self):
self.vertList = {}
self.numVertice = 0
def add_vertex(self, key):
self.numVertice += 1
newVertex = Vertex(key)
self.vertList[key] = newVertex #
return newVertex
def get_vertex(self, n):
if n in self.vertList:
return self.vertList
else:
return None
def __contains__(self, item):
return n in self.vertList
def add_edge(self, f, t, cost=0):
if f not in self.vertList:
nv = self.add_vertex(f)
if t not in self.vertList:
nv = self.add_vertex(t)
self.vertList[f].add_neighbor(self.vertList[t], cost)
def get_vertics(self):
return self.vertList.keys()
def __iter__(self):
return iter(self.vertList.values())
if __name__ == "__main__":
g = Graph()
for i in range(6):
g.add_vertex(i)
g.add_edge(0,1,5)
g.add_edge(0,5,2)
g.add_edge(1,2,4)
g.add_edge(2,3,9)
g.add_edge(3,4,7)
g.add_edge(3,5,3)
g.add_edge(4,0,1)
g.add_edge(5,4,8)
g.add_edge(5,2,1)
for x in g:
print(x)
0 connected to [1, 5]
1 connected to [2]
2 connected to [3]
3 connected to [4, 5]
4 connected to [0]
5 connected to [4, 2]
DFS(深さ優先検索)
DFSの実装プロセスは、ツリーの最初のシーケンス番号と同じであり、DFSの実装過程では、対応する頂点アクセス標識を設定する必要があります.すでに訪問したノードはアクセスしていません.プロセスを実現するために最も重要なのは、状態のトレースであり、再帰を使用することができます.アルゴリズムは分かりやすいです.一つの道は黒に行きます.だめなら撤退します.もう歩いていません.繰り返します.
def get_first_neighbor(self, index):
""" """
for j in range(self.get_num_of_vertexs()):
if self.edges[index][j] > 0:
return j
return -1
def get_next_neighbor(self, v1, v2):
""" """
for j in range(v2 + 1, self.get_num_of_vertexs()):
if self.edges[v1][j] > 0:
return j
return -1
def dfs(self, is_visited, i):
""" """
print(self.get_val_by_index(i), "->", end=" ")
self.is_visited[i] = True
first = self.get_first_neighbor(i)
while first != -1:
if not self.is_visited[first]:
self.dfs(is_visited, first) #
first = self.get_next_neighbor(i, first)
def dfs_override(self):
""" """
for i in range(self.get_num_of_vertexs()):
if not self.is_visited[i]:
self.dfs(self.is_visited, i)
BFSは木の階層巡回に相当し、キューを使って頂点を保存して検索することができ、後に先進的に出た頂点の有効辺頂点を検索し、検索したものはもう検索しないので、頂点の検索状態を識別します.
def get_first_neighbor(self, index):
""" """
for j in range(self.get_num_of_vertexs()):
if self.edges[index][j] > 0:
return j
return -1
def get_next_neighbor(self, v1, v2):
""" """
for j in range(v2 + 1, self.get_num_of_vertexs()):
if self.edges[v1][j] > 0:
return j
return -1
def bfs(self, is_visited, i):
""" """
queue = []
print(self.get_val_by_index(i) + "->", end=" ")
self.is_visited[i] = True
queue.append(i)
while queue:
u = queue.pop(0)
w = self.get_first_neighbor(u)
while w != -1:
if not is_visited[w]:
print(self.get_val_by_index(w), "->", end=" ")
self.is_visited[w] = True
queue.append(w)
w = self.get_next_neighbor(u, w)
def bsf_override(self):
for j in range(self.get_num_of_vertexs()):
if not self.is_visited[j]:
self.bfs(self.is_visited, j)
検索思想——DFS&BFS(基礎編)
隣接表
データ構造とアルゴリズム–図を一歩ずつ持って、Pythonで図の深さ遍歴と広さを優先的にPythonを経由して、図の深さ遍歴と広さ優先度を実現します.DFSとBFS過程を詳しく説明します.