对象和指针图表示法

Question

对象和指针图表示法

data-structuresgraph

17

我经常看到有关表示图形的三种方式：

对象和指针
邻接矩阵
邻接表

然而，我根本不明白这些对象和指针表示是什么 - 然而每个招聘人员和许多博客都引用Steve Yegge的博客，证明它们确实是一种单独的表示。

这个广为接受的答案对一个非常类似的问题似乎表明，顶点结构本身没有内部指向其他顶点的指针，而所有边都由包含指向相邻顶点的指针的边结构表示。

在任何情况下，这种表示如何提供任何可辨别的分析优势呢？

- Kat

4个回答

1

对象和指针的表示将空间复杂度降至精确的V+E，其中V是顶点数，E是边数（从V+2E降至邻接表甚至2V+2E，如果您在单独的哈希映射中存储索引->顶点映射），牺牲时间复杂度：特定边查找将需要O(E)，在稠密图中等于O(V^2)（从邻接表的O(V)上升）。通过删除出现在邻接表中的重复边来实现节省空间。

- Serge Mosin

0

这是我一直在使用的一种创建图形的方法：

#include <vector>

class Node
{
    public:
        Node();
        void setLink(Node *n); // *n as argument to pass the address of the node
        virtual ~Node(void);
    private:
        vector<Node*> m_links;
};

负责创建顶点之间链接的函数是：

void Node::setLink(Node *n)
{
    m_links.push_back(n);
}

- The game

0

目前我在找一个熟练掌握常规“图算法”的专业人士方面遇到了困难。但是，如果你将其视为白板上绘制内容的一种表示，使用对象和指针表示图形是可能的，也是非常自然的事情。

想象一种场景，您希望按特定顺序组合图的节点。节点具有包含域数据的有效负载，图结构本身不是程序的核心方面。

当然，您可以为每个操作更新列表/矩阵，但是如果采用“对象和指针”结构，可以在本地执行合并。此外，如果节点具有负载，则意味着列表/矩阵将包含标识实际节点对象的节点ID。组合将意味着您会更新图形表示，跟随节点标识符并进行实际处理。在折叠邻居（并删除该节点）时，直接处理节点对象并删除指针可能更自然。

此外，还有更多表示图的方法：

例如像三元组一样，比如Turle
或者作为偏移量表示（每个节点到一个边数组的偏移量），例如这种Boost数据结构（免责声明：我没有亲自测试过链接的实现）
等等

- b.buchhold

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- xyz · Accepted Answer

从我头脑中得出，希望我的事实是正确的。

概念上，图尝试表示一组节点（或顶点）如何相互关联（通过边缘连接）。然而，在实际物理设备（内存）中，我们有一个连续的内存单元数组。

因此，为了表示图形，我们可以选择使用矩阵。在这种情况下，我们使用顶点索引作为行和列，如果顶点相邻，则条目的值为1，否则为0。

另外，您还可以通过分配对象来表示节点/顶点，该对象指向其所有相邻节点的列表来表示图形。

矩阵表示在图形稠密时具有优势，这意味着大多数节点/顶点彼此相连。这是因为在这种情况下，通过使用矩阵的条目，它可以节省我们为每个连接分配额外指针（需要一个字大小的内存）。

对于稀疏图，列表方法更好，因为当顶点之间没有连接时，您不需要考虑0条目。

希望它有所帮助。