实施加权图 class，其中输入为 <u,v,w> Python

Question

我已经能够实现一个图 class，其中首先给出每个单独的顶点，然后添加边。但这是浪费内存。输入示例：

total_vertices = 7
my_graph = Graph(total_vertices)
edges = []
edges.append((3,1,5))
edges.append((1,2,1))
my_graph.add_edges(edges)

这是我的代码

class Graph:
    def __init__(self, N):
        self.vertices = [None] * N
        for i in range(N):
            self.vertices[i] = Vertex(i)

    def add_edges(self, edges_list):
        for edge in edges_list:
            u = edge[0]
            v = edge[1]
            w = edge[2]
            current_edge = Edge(u,v,w)
            current_vertex = self.vertices[u]
            current_vertex.add_edge_to_vertex(current_edge)

class Vertex:
    def __init__(self, vertex):
        self.vertex = vertex
        self.vertex_edges = []

    def add_edge_to_vertex(self, edge):
        self.vertex_edges.append(edge)

class Edge:
    def __init__(self, u, v, w):
        self.u = u
        self.v = v
        self.w = w

所以我想在 python 中实现一个图 class，其中输入的形式为 <u,v,w>，其中 u 是父顶点，v是子顶点，w直接是权重不用先指明顶点数。输入如下所示：

edgelist = [(0,2,4),(0,1,2),(0,3,3),(2,3,2), (3,0,3)]
graph = Graph(edgelist)
print(graph)

欢迎任何help/suggestions

示例输入：

edgelist = [(0,2,4),(0,1,2),(0,3,3),(2,3,2), (3,0,3)]
graph = Graph(edgelist)
print(graph)

Answer 1

您可能可以使用字典来存储顶点和边：

import collections

class Graph:
    def __init__(self, edge_list):
        self.edges = collections.defaultdict(dict)
        for u, v, w in edge_list:
            self.edges[u][v] = w

    def get_weight(self, u, v):
        return self.edges[u][v]

    def __repr__(self):
        return f'{self.__class__.__qualname__}({dict(self.edges)})'

    def __str__(self):
        return str(dict(self.edges))

用法：

# Create an instance of a graph
edgelist = [(0, 2, 4), (0, 1, 2), (0, 3, 3), (2, 3, 2), (3, 0, 3)]
graph = Graph(edgelist)
print(graph)

# Get the weight between u and v
u, v = 0, 1
print(graph.get_weight(u, v))

Answer 2

只有两个属性：self._nodes 和 self._edges，每次添加节点或边时它们都会被修改。我只是删除了 Vertex class 但你实际上可以保留它（在你的代码中不需要），还有我最终没有删除的 Edge class。

我修改了边元组以区分节点和权重...

class Graph:
    def __init__(self, edges_list=None):
        self._nodes = []
        self._edges = []
        if edges_list is not None:
            self.add_edges(edges_list)

    def add_node(self, v):
        self._nodes.append(v)

    def add_edge(self, ab, w):
        a, b = ab
        if a not in self._nodes:
            self._nodes.append(a)
        if b not in self._nodes:
            self._nodes.append(b)
        my_new_edge = Edge(ab, w)
        self._edges.append(my_new_edge)

    def add_edges(self, e_list):
        for ab, w in e_list:
            self.add_edge(ab, w)

    def __str__(self):
        return f"{self._nodes}\n{self._edges}"


class Edge:
    def __init__(self, ab, w):
        a, b = ab
        self._from = a
        self._to = b
        self._weight = w

    def __repr__(self):
        return f"from {self._from} to {self._to} weighted {self._weight}"


edgelist = [((0, 2), 4),
            ((0, 1), 2),
            ((0, 3), 3),
            ((2, 3), 2),
            ((3, 0), 3)]
g = Graph(edgelist)

print(g)
# [0, 2, 1, 3]
# [from 0 to 2 weighted 4, from 0 to 1 weighted 2, from 0 to 3 weighted 3, from 2 to 3 weighted 2, from 3 to 0 weighted 3]

编辑向 Graph 构造函数添加一个可选参数，以便它接受边列表。

实施加权图 class，其中输入为 <u,v,w> Python

Implementing a weighted graph class where inputs are <u,v,w> Python

python

oop

graph