私は人気のあるケビンベーコンゲームのグラフ表現を作成しようとしています。私はグラフと頂点のクラスを作成しましたが、グラフを横断してケビン・ベーコンから俳優までの最短経路を見つけ出し、途中でエッジをプリントアウトするための最初の検索方法を作成するのに問題があります。 ユーザーは俳優を入力する必要があり、プログラムはケビンベーコンからその俳優までの最短経路を見つけなければなりません。ユーザーは俳優に入り続け、その俳優への最短経路がとられ、ケビンベーコンの番号が印刷されます。そうでなければ、それは印刷されません。ケビンベーコンゲームの最短経路グラフトラバーサル
頂点とグラフのクラスがあります。頂点クラスは、それが接続されている他の頂点と辺を含むディクショナリです。
私はこのようなルックスで働いていたデータ：
頂点：
[ "ケビン・ベーコン"、 "actor1"、 "ACTOR2"、 "ACTOR3"、 "actor4"、 "actor5"、 "actor6"]
エッジ：
（ "ケビン・ベーコン"、 "actor1"、 "MOVIE1"）
（ "ケビン・ベーコン"、 "ACTOR2"、 "MOVIE1"）
（ "actor1"、 "ACTOR2"、 "MOVIE1"）
（ "actor1"、 "ACTOR3"、 "MOVIE2"）
（ "ACTOR3"、 "ACTOR2"、 "movie3"）
（ "ACTOR3"、 "actor4"、 "movie4"）
（ "actor5"、 "actor6"、 "movie5"）映画は、エッジ名または量が
、及びタプルの他の部分は頂点です。 BFSアルゴリズムですべてのエッジとケビンベーコンの番号を出力したり、アクターに到達できない場合は不可能であることを表示したりします。
ここまではコードです。どんなアドバイスや助けもありがとうございます。
は
class Vertex:
'''
keep track of the vertices to which it is connected, and the weight of each edge
'''
def __init__(self, key):
'''
'''
self.ID = key
self.connected_to = {}
def add_neighbor(self, neighbor, weight=0):
'''
add a connection from this vertex to anothe
'''
self.connected_to[neighbor] = weight
def __str__(self):
'''
returns all of the vertices in the adjacency list, as represented by the connectedTo instance variable
'''
return str(self.ID) + ' connected to: ' + str([x.ID for x in self.connected_to])
def get_connections(self):
'''
returns all of the connections for each of the keys
'''
return self.connected_to.keys()
def get_ID(self):
'''
returns the current key id
'''
return self.ID
def get_weight(self, neighbor):
'''
returns the weight of the edge from this vertex to the vertex passed as a parameter
'''
return self.connected_to[neighbor]
class Graph:
'''
contains a dictionary that maps vertex names to vertex objects.
'''
def __init__(self):
'''
'''
self.vert_list = {}
self.num_vertices = 0
def __str__(self):
'''
'''
edges = ""
for vert in self.vert_list.values():
for vert2 in vert.get_connections():
edges += "(%s, %s)\n" %(vert.get_ID(), vert2.get_ID())
return edges
def add_vertex(self, key):
'''
adding vertices to a graph
'''
self.num_vertices = self.num_vertices + 1
new_vertex = Vertex(key)
self.vert_list[key] = new_vertex
return new_vertex
def get_vertex(self, n):
'''
'''
if n in self.vert_list:
return self.vert_list[n]
else:
return None
def __contains__(self, n):
'''
in operator
'''
return n in self.vert_list
def add_edge(self, f, t, cost=0):
'''
connecting one vertex to another
'''
if f not in self.vert_list:
nv = self.add_vertex(f)
if t not in self.vert_list:
nv = self.add_vertex(t)
self.vert_list[f].add_neighbor(self.vert_list[t], cost)
def get_vertices(self):
'''
returns the names of all of the vertices in the graph
'''
return self.vert_list.keys()
def __iter__(self):
'''
for functionality
'''
return iter(self.vert_list.values())
def bfs(self):
'''
Needs to be implemented
'''
pass