时间戳

首页 > 解决方案 > 图上实现算法的输出

python - 图上实现算法的输出

问题描述

这段代码是对图的一些操作，基本上输入指令如下：

class NodoArvore:
    def __init__(self, chave=None, esquerda=None, direita=None):
        self.chave = chave
        self.esquerda = esquerda
        self.direita = direita

    def __repr__(self):
        return '%s <- %s -> %s' % (self.esquerda and self.esquerda.chave,
                                    self.chave,
                                    self.direita and self.direita.chave)

raiz = NodoArvore(40)

raiz.esquerda = NodoArvore(20)
raiz.direita  = NodoArvore(60)

raiz.direita.esquerda  = NodoArvore(50)
raiz.direita.direita   = NodoArvore(70)
raiz.esquerda.esquerda = NodoArvore(10)
raiz.esquerda.direita  = NodoArvore(30)

标签： python

解决方案

我稍微清理了你的函数并添加了最终计算。我还使用字典而不是边/权重列表来使图形更改更容易实现（并且更有效）：

graph    = dict()
directed = True

def add_node(v):
    if v in graph: return print(v, "is already part of the graph")
    graph[v] = dict()

def add_edge(v1,v2,weight):
    if v1 not in graph or v2 not in graph: 
        return print(v1,"or",v2,"not part of the graph")
    if v2 in graph[v1]:
        return print((v1,v2),"already part of the graph")
    graph[v1][v2] = weight
    if not directed: graph[v2][v1] = weight
        
def delete_edge(v1,v2):
    if v1 not in graph or v2 not in graph[v1]: 
        return print((v1,v2),"not part of the graph")
    graph[v1].pop(V2)
    if not directed: graph[v2].pop(V1)

def delete_node(v):
    if v not in graph: return print(v,"not part of the graph")        
    for e in graph.values():
        if v in e: e.pop(v)
    graph.pop(v)

def count_edges():
    return sum(map(len,graph.values()))//[2,1][directed]

def count_weights():
    return sum(w for e in graph.values() for w in e.values())/[2,1][directed]

用法：

no_operations = int(input("Enter number of operations: "))

for _ in range(no_operations):
    command = input("Enter command: ")
    oper,v1,v2, weight,*_ = command.split(" ") + ["",""]
    if   oper == 'IV': add_node(v1)
    elif oper == 'IA': add_edge(v1,v2,float(weight))
    elif oper == 'RV': delete_node(v1)
    elif oper == 'RA': delete_edge(v1,v2)
    else:print("Invalid command")

nodeCount = len(graph)
edgeCount = count_edges()
weights   = count_weights()

print(nodeCount,"vertex(s),",edgeCount,"edge(s) and total weight",weights)

print(graph)

样品运行：

Enter number of operations: 4
Enter command: IV A
Enter command: IA B A 1
not part of the graph
Enter command: IV B
Enter command: IA A B 2
2 vertex(s), 1 edge(s) and total weight 2.0
{'A': {'B': 2.0}, 'B': {'A': 2.0}}

...

# directed graph:

Enter number of operations: 14
Enter command: IV A
Enter command: IV B
Enter command: IV C
Enter command: IV D
Enter command: IA A B 0.1
Enter command: IA A C 0.2
Enter command: IA B A 0.3
Enter command: IA B C 0.4
Enter command: IA C A 0.5
Enter command: IA C B 0.6
Enter command: IV D
D is already part of the graph
Enter command: IV E
Enter command: IA D E -10
Enter command: RV A
4 vertex(s), 3 edge(s) and total weight -9.0
{'B': {'C': 0.4}, 'C': {'B': 0.6}, 'D': {'E': -10.0}, 'E': {}}

推荐阅读