基于三国人物关系数据,构建三国人物关系图。图的顶点为三国人物。边为人物关系(如儿子、义弟、主公)。本题需要实现在图结构上做的各种人物关系查询。人物的属性包括:人名、所属国。 如刘备(刘备,蜀国) 【功能】 1.基于邻接表构建三国人物关系图,并能输出展示邻接表,保存在文件”TRKGraph.txt”中。文件格式如下: 刘备-->张飞--->关羽--->赵云 注意:图的构建,应该先整理图中的顶点数据,即要整理所有三国人物数据作为图顶点。 2.统计人物关系数量最多的前10个三国人物及其所属国。 3.输入2个人物,查找2个人物之间所有关系。基于图的深度遍历,展示关系路径。并能说明最短路径是哪条。答辩时候展示:有关系的人物。无关系的人物。 4.智能问答。输入荀彧的主公的儿子是谁?能输出关系路径,并给出答案。
时间: 2024-04-04 13:32:45 浏览: 84
人物关系图
5星 · 资源好评率100%
很抱歉,作为一个 AI,我没有本地存储数据的能力,也没有文件读写的权限。但是我可以为您提供一些实现思路和代码示例。
【实现思路】
1. 建立三国人物关系的图。可以使用邻接表来表示图。每个顶点为一个人物,每条边表示两个人物之间的关系。边的类型可以使用字符串来表示(如“儿子”、“义弟”、“主公”等)。
2. 统计人物关系数量。可以使用图的深度优先遍历算法,遍历所有顶点和边,统计每个顶点的出边数量。然后按照出边数量从大到小排序,取前10个顶点作为结果。
3. 查找两个人物之间的关系。可以使用图的深度优先遍历算法,从一个人物开始,遍历所有相邻的顶点,直到找到另一个人物。可以记录遍历路径,并输出路径信息。最短路径可以使用广度优先遍历算法来实现。
4. 智能问答。可以使用图的深度优先遍历算法,从一个人物开始,遍历所有相邻的顶点,直到找到目标人物。可以记录遍历路径,并输出路径信息和答案。
【示例代码】
以下是一个简单的示例代码,实现了图的构建、邻接表的输出和深度优先遍历算法。您可以根据自己的需求进行修改和扩展。
```python
class Vertex:
def __init__(self, name, country):
self.name = name
self.country = country
self.adjacent = {}
def add_neighbor(self, vertex, relation):
self.adjacent[vertex] = relation
def get_connections(self):
return self.adjacent.keys()
def get_relation(self, vertex):
return self.adjacent[vertex]
def __str__(self):
return self.name + ' (' + self.country + ')'
class Graph:
def __init__(self):
self.vertices = {}
def add_vertex(self, vertex):
self.vertices[vertex.name] = vertex
def get_vertex(self, name):
return self.vertices.get(name)
def add_edge(self, v1, v2, relation):
if v1 not in self.vertices:
self.add_vertex(Vertex(v1))
if v2 not in self.vertices:
self.add_vertex(Vertex(v2))
self.vertices[v1].add_neighbor(self.vertices[v2], relation)
def get_vertices(self):
return self.vertices.keys()
def __iter__(self):
return iter(self.vertices.values())
def build_graph():
# 构建三国人物关系图
graph = Graph()
# 添加顶点
graph.add_vertex(Vertex('刘备', '蜀国'))
graph.add_vertex(Vertex('张飞', '蜀国'))
graph.add_vertex(Vertex('关羽', '蜀国'))
graph.add_vertex(Vertex('赵云', '蜀国'))
graph.add_vertex(Vertex('曹操', '魏国'))
graph.add_vertex(Vertex('曹丕', '魏国'))
graph.add_vertex(Vertex('司马懿', '魏国'))
graph.add_vertex(Vertex('孙权', '吴国'))
graph.add_vertex(Vertex('周瑜', '吴国'))
graph.add_vertex(Vertex('诸葛亮', '蜀国'))
graph.add_vertex(Vertex('荀彧', '魏国'))
# 添加边
graph.add_edge('刘备', '张飞', '义弟')
graph.add_edge('刘备', '关羽', '义兄')
graph.add_edge('关羽', '赵云', '将军')
graph.add_edge('曹操', '曹丕', '儿子')
graph.add_edge('曹操', '司马懿', '谋士')
graph.add_edge('孙权', '周瑜', '同盟')
graph.add_edge('孙权', '诸葛亮', '敌国谋士')
graph.add_edge('荀彧', '曹操', '谋士')
graph.add_edge('荀彧', '曹丕', '主公之子')
return graph
def show_adjacency_list(graph):
# 输出邻接表
with open('TRKGraph.txt', 'w') as f:
for v in graph:
f.write(str(v) + ' --> ')
for neighbor in v.get_connections():
f.write(str(neighbor) + '(' + v.get_relation(neighbor) + ')' + ' ---> ')
f.write('\n')
def dfs(graph, start, end, path=None):
# 深度优先遍历,查找两个人物之间的关系
if path is None:
path = []
path = path + [start]
if start == end:
return path
for vertex in graph.get_vertex(start).get_connections():
if vertex.name not in path:
newpath = dfs(graph, vertex.name, end, path)
if newpath:
return newpath
return None
if __name__ == '__main__':
# 构建三国人物关系图
graph = build_graph()
# 输出邻接表
show_adjacency_list(graph)
# 查找两个人物之间的关系
print(dfs(graph, '刘备', '赵云'))
```
阅读全文