저는 인기있는 케빈 베이컨 게임에 대한 그래프 표현을 만들려고했습니다. 그래프와 버텍스 클래스를 만들었지 만 그래프를 가로 지르는 첫 번째 검색 방법을 만들고 케빈 베이컨에서 배우까지의 최단 경로를 찾아 문제의 가장자리를 인쇄하는 데 어려움을 겪고 있습니다. 사용자는 배우를 입력해야하며, 프로그램은 케빈 베이컨에서 해당 배우까지의 최단 경로를 찾아야합니다. 사용자는 계속해서 액터에 들어가고 그 액터에 대한 최단 경로를 취하게되고 케빈 베이컨 번호가 출력됩니다. 그렇지 않으면 아무 것도 출력하지 않습니다.케빈 베이컨 게임에 대한 최단 경로 그래프 탐색
버텍스 및 그래프 클래스가 있습니다. 정점 클래스는 연결된 다른 정점과 모서리를 포함하는 사전입니다.
이 같은 외모와 협력하고 데이터 :
정점 :
[ "케빈 베이컨", "actor1", "actor2", "actor3", "actor4", "actor5" "actor6"]
가장자리 :
("케빈 베이컨", "actor1", "극장 1")
("케빈 베이컨", "actor2", "극장 1")
("actor1", "actor2", "극장 1")
("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