比较对象图表示与邻接列表和矩阵表示

Question

我正在关注Steve Yegge关于准备技术编程访谈的建议:http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

在他关于图表的部分中,他指出:

在内存中表示图形有三种基本方法(对象和指针,矩阵和邻接列表),您应该熟悉每种表示及其优缺点.

CLRS中描述了矩阵和邻接列表表示的优缺点,但我无法找到将这些表示与对象表示进行比较的资源.

只要想一想,我就可以自己推断一些,但我想确保我没有错过一些重要的东西.如果有人能够全面地描述这一点,或者指向一个这样做的资源,我将非常感激.

Answer 1

对象和指针

这些只是像哈马尔在另一个答案中所说的基本数据结构,Java你可以用像边和顶点这样的类来表示它.例如,边缘连接两个顶点,并且可以是定向的或不定向的,并且它可以包含权重.顶点可以有ID,名称等.大多数它们都有其他属性.所以你可以用它们构建你的图形

Vertex a = new Vertex(1);
Vertex b = new Vertex(2);
Edge edge = new Edge(a,b, 30); // init an edge between ab and be with weight 30  

这种方法通常用于面向对象的实现,因为它对于面向对象的用户来说更具可读性和便利性;).

矩阵

矩阵只是一个简单的二维数组.假设您有顶点ID,可以表示为这样的int数组:

int[][] adjacencyMatrix = new int[SIZE][SIZE]; // SIZE is the number of vertices in our graph
adjacencyMatrix[0][1] = 30; // sets the weight of a vertex 0 that is adjacent to vertex 1

这通常用于需要索引访问的密集图.您可以使用此表示非/定向和加权结构.

邻接名单

这只是一个简单的数据结构组合,我通常使用a来实现HashMap<Vertex, List<Vertex>>.类似的用途可以是HashMultimap番石榴.

这种方法很酷,因为你有O(1)(摊销)顶点查找,它返回一个我要求的这个特定顶点的所有相邻顶点的列表.

ArrayList<Vertex> list = new ArrayList<>();
list.add(new Vertex(2));
list.add(new Vertex(3));
map.put(new Vertex(1), list); // vertex 1 is adjacent to 2 and 3

这用于表示稀疏图形,如果您在Google上应用,您应该知道该网页是稀疏的.您可以使用BigTable以更具伸缩性的方式处理它们.

哦,顺便说一句,这里有一个非常好的总结这篇文章与花哨的图片;)

Answer 2

对象和指针与邻接列表大致相同,至少为了比较使用这些表示的算法.

相比

struct Node {
    Node *neighbours[];
};

同

struct Node {
    Node *left;
    Node *right;
};

如果比命名指针更容易使用,则可以在后一种情况下轻松构建邻居列表.