实施有向加权图

Question

我能够使用字典为未加权和无向图创建普通图类。我想将我的普通图类修改为有向加权图。我不确定如何使用我创建的普通图形类来执行此操作。而且我也不明白我应该“做什么”使它指向。.

这是我的MyGraph类：

from typing import NewType, List, Dict
Vertex = NewType('Vertex',object) 

class MyGraph:
    def __init__(self):
        self._Dict: Dict[Vertex,List[Vertex]]= {}
    def reset(self):
        self._Dict.clear()
    def is_vertex(self, u: Vertex):
        return u in self._Dict
    def is_edge(self, u: Vertex, v: Vertex):
        if self.is_vertex(u):
            return v in self._Dict[u]
        return False
    def add_vertex(self, u: Vertex):
        if not self.is_vertex(u):
            self._Dict[u]=[]
    def add_edge(self, u: Vertex, v:Vertex):
        if not (self.is_edge(u,v)) and self.is_vertex(u) and self.is_vertex(v):
            self._Dict[u].append(v)

    def neighbourhood(self, u:Vertex):
        return self._Dict[u]

    def all_vertices(self):
        return list(self._Dict)
    def print_graph(self):
        print(self._Dict)

感谢您的任何帮助！

Answer 1

您已经实现了有向图。我已经修改了您的代码以包括权重。

from typing import NewType, List, Dict
Vertex = NewType('Vertex',object) 
Weight = NewType('Weight',object) 

class MyGraph:
    def __init__(self):
        self._Dict: Dict[Vertex,(List[Vertex], List[Weight])]= {}
    def reset(self):
        self._Dict.clear()
    def is_vertex(self, u: Vertex):
        return u in self._Dict
    def is_edge(self, u: Vertex, v: Vertex):
        if self.is_vertex(u):
            return v in self._Dict[u]
        return False
    def add_vertex(self, u: Vertex):
        if not self.is_vertex(u):
            self._Dict[u]=[]
    def add_edge(self, u: Vertex, v:Vertex, w:Weight):
        if not (self.is_edge(u,v)) and self.is_vertex(u) and self.is_vertex(v):
            self._Dict[u].append((v,w))

    def neighbourhood(self, u:Vertex):
        return self._Dict[u]

    def all_vertices(self):
        return self._Dict
    def print_graph(self):
        print(self._Dict)


g =MyGraph()
g.add_vertex('u')
g.add_vertex('v')
g.add_vertex('w')
g.add_vertex('x')
g.add_vertex('y')
g.add_vertex('z')
g.add_edge('u', 'v', 5)  
g.add_edge('u', 'w', 7)
g.add_edge('u', 'z', 4)
g.add_edge('v', 'w', 1)
g.add_edge('v', 'x', 5)
g.add_edge('w', 'x', 8)
g.add_edge('w', 'z', 3)
g.add_edge('x', 'y', 4)
g.add_edge('y', 'z', 7)
print(g.all_vertices())

这将字典打印为：

{'u'：[（'v'，5），（'w'，7），（'z'，4）]，'v'：[（'w'，1），（'x' ，5）]，'w'：[（'x'，8），（'z'，3）]，'x'：[（'y'，4）]，'y'：[（'z'，7）]，'z'： []}

基本上包括称为权重的新类型。

Weight = NewType('Weight',object) 

然后修改了self._Dict，以使每个顶点现在都与（顶点，权重）的元组列表相关联

self._Dict: Dict[Vertex,(List[Vertex], List[Weight])]= {}

最后修改了add_edge(self, u: Vertex, v:Vertex, w:Weight)方法以添加额外的参数Weight。

def add_edge(self, u: Vertex, v:Vertex, w:Weight):
    if not (self.is_edge(u,v)) and self.is_vertex(u) and self.is_vertex(v):
        self._Dict[u].append((v,w))