0

在斯坦福算法讲座中，Roughgarden 教授列出了邻接表的以下成分：

  1. 数组或顶点列表
  2. 边的数组或列表
  3. 顶点列表中的每个顶点都指向入射在其上的边。
  4. 边列表中的每条边都指向它的边点。

如何在 python 中实现这一点，尤其是 3 和 4 的组合？这对我来说一直是个挑战。我在 C++ 中使用指针完成了该操作。我可以想到一种方法，如果您认为它是正确的，请告诉我。数字 4 可以通过一个元组列表来完成， Edges = [(1,2),(3,2),(4,1)]或者向元组添加另一个元素以获得权重值。如何使 List of Vertices 指向事件的边缘呢？ Vertices = {1 : [0,2] 2: [0,1] 3: [1] 4:[3]}这里 Vertices 是一个字典，每个键（顶点）的值是包含键（顶点）的边的索引列表。这看起来合理吗？

好的，我也会给出它的C++实现。

struct Node;
struct Arcs; //Forward declarations as each of them references each other
using namespace std
struct SimpleGraph  // Has all the nodes
{
   set<Node *> nodes;
   set<Arc *> arcs;
}
//Node contains node_number and the set of arcs/edges from this node.
struct Node
{  
   int node_number; 
   set<Arc *> arcs;
}
// Arc contains start and finish node and the cost associated with the Arc/Edge
struct Arc
{
  Node* start;
  Node* finish;
  double cost;
}

因为我们在 C++ 中使用指针，所以 Arc 信息的变化会自动反映在节点中。缺少指针使得在 python 中很难做到这一点。所以我努力做到我能做到的最好。

4

1 回答 1

0

在 python 中，基本上一切都是对象，因此列表、字典和映射也是对象，因此通过它们的地址访问（就像 C++ 在使用引用调用时所做的那样）。

看看下面的代码示例，它证明了这一点：

list_a = ['a', 'b', 'c']
list_b = ['d', 'e', 'f']

one_dict = {'entry1': list_a, 'entry2': list_b}

def add_entry(target_list, entry):
    target_list.append(entry)

print("Our example dict:")
print(one_dict)

print("Modifying 'list_a' and 'list_b'.")
list_a[1] = 'B'
list_b[2] = 'F'
print(list_a)
print(list_b)

print("Appending new entries to 'list_a' and 'list_b'")
add_entry(list_a, 'q')
add_entry(list_b, list_a)
print(list_a)
print(list_b)

print("'list_a' and 'list_b' can still being accessed via 'one_dict'.")
print(one_dict)

这是输出，您可以清楚地看到 one_dict 保存对这些列表的引用：

Our example dict:
{'entry2': ['d', 'e', 'f'], 'entry1': ['a', 'b', 'c']}
Modifying 'list_a' and 'list_b'.
['a', 'B', 'c']
['d', 'e', 'F']
Appending new entries to 'list_a' and 'list_b'
['a', 'B', 'c', 'q']
['d', 'e', 'F', ['a', 'B', 'c', 'q']]
'list_a' and 'list_b' can still being accessed via 'one_dict'.
{'entry2': ['d', 'e', 'F', ['a', 'B', 'c', 'q']], 'entry1': ['a', 'B', 'c', 'q']}

因此，实现非常简单，就像您的 C++ 代码一样。

于 2013-07-18T21:57:44.533 回答