我正在使用邻接表表示。
基本上
A:[B,C,D] means A is connected to B,C and D
现在我正在尝试添加一个方法（在 python 中）以在图中添加边。
但在我添加边缘之前。我想检查两条边是否连接。因此，例如，我想在两个节点 D 和 A 之间添加一条边（不知道 A 和 D 是连接的事实）。
因此，由于哈希/字典中没有键“D”，它将返回 false。
现在，非常天真地，我可以检查 D 和 A，然后也检查 A 和 D.. 但这很不合时宜。或者每当我连接两个节点时，我总是可以复制..
即当连接 A 和 E.. A:[E] 创建 E:[A]
但这不是很节省空间。
基本上我想让这个图形方向独立。
是否有任何数据结构可以帮助我解决这个问题。
我希望我的问题是有道理的。
对于无向图，您可以使用一个简单的边列表来存储所有边对。这将节省空间并降低性能，但您应该知道您不能同时拥有两者，因此您始终必须做出权衡。
否则，您可以使用三角形邻接矩阵，但为了避免浪费一半空间，您必须以特定方式存储它（通过开发一种有效的方式来检索边缘存在而不浪费空间）。你确定这是值得的，而且不仅仅是过早的优化吗？
邻接表大部分都很好，即使您必须将每个无向边存储两次，您的图有多大？
看看我的答案：Graph representation benchmarking，所以你可以选择你喜欢的那个。
您遇到了经典的空间与时间权衡。
如您所说，如果没有找到D->A，则可以搜索A->D。这将使您的执行时间最多增加一倍。或者，当插入 A->D 时，也创建 D->A，但这是以额外空间为代价的。
最坏的情况，为了时间权衡，您将进行 2 次查找，仍然是 O(N)（使用更好的数据结构更快）。对于空间权衡，您将（在最坏的情况下）在每组节点之间创建一个链接，大约为 O(N^2)。因此，我只会进行 2 次查找。
假设每种contains()方法都非常广泛，并且您希望不惜一切代价避免这样做，可以使用布隆过滤器，并检查是否存在边缘 - 从而减少contains()调用次数。
这个想法是：每个节点都将拥有自己的布隆过滤器，它将指示哪些边连接到它。检查布隆过滤器相当容易且便宜，并且在添加边缘时也可以对其进行修改。
如果您检查了布隆过滤器 - 它说“不” - 您可以安全地添加边缘 - 它不存在。
然而，布隆过滤器有误报——所以，如果布隆过滤器说“边缘存在”——你必须检查列表是否确实存在。
注意：
（1）如果使用布隆过滤器，去除边缘将是一个问题。
(2) 布隆过滤器为您提供了很好的时间/空间折衷——因为误报的数量随着过滤器大小的增加而减少。
(3) 但是，当边缘确实存在时 - 无论过滤器的大小是多少，您都必须使用该contains()方法。
假设可以比较您的节点名称，您可以简单地始终存储边，以便第一个端点小于第二个端点。然后，您只需执行一次查找。这绝对适用于字符串。