对象图表示与邻接表及矩阵表示的比较

我目前正在遵循史蒂夫叶格的建议，准备一个技术节目采访: http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

在关于图表的章节中，他指出:

有三种基本的方法 表示内存中的图形(对象) 以及指针、矩阵和邻接 ) ，并且您应该熟悉 你自己和每个代表 有利有弊。

在 CLRS 中描述了矩阵和邻接列表表示法的优缺点，但是我还没有找到能够将这些表示法与对象表示法进行比较的资源。

只要想一想，我自己就能推断出一些，但是我想确保我没有错过什么重要的东西。如果有人能够全面地描述这一点，或者给我提供一个这样做的资源，我将非常感激。

27595 次浏览
小开

Objects and pointers is mostly the same as adjacency list, at least for the purpose of comparing algorithms that use these representations.

Compare

struct Node {
Node *neighbours[];
};

with

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

You can easily construct the list of neighbours on-the-fly in the latter case, if it is easier to work with than named pointers.

小开

objects and pointers

These are just basic datastructures like hammar said in the other answer, in Java you would represent this with classes like edges and vertices. For example an edge connects two vertices and can either be directed or undirected and it can contain a weight. A vertex can have an ID, name etc. Mostly both of them have additional properties. So you can construct your graph with them like

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

This approach is commonly used for object oriented implementations, since it is more readable and convenient for object oriented users ;).

matrix

A matrix is just a simple 2 dimensional array. Assuming you have vertex ID's that can be represented as an int array like this:

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

This is commonly used for dense graphs where index access is necessary. You can represent a un/directed and weighted structure with this.

adjacency list

This is just a simple datastructure mix, I usually implement this using a HashMap<Vertex, List<Vertex>>. Similar used can be the HashMultimap in Guava.

This approach is cool, because you have O(1) (amortized) vertex lookup and it returns me a list of all adjacent vertices to this particular vertex I demanded. 

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

This is used for representing sparse graphs, if you are applying at Google, you should know that the webgraph is sparse. You can deal with them in a more scalable way using a BigTable.

Oh and BTW, here is a very good summary of this post with fancy pictures ;)

小开

Advantage of the object representation (incidence list) is that two adjacent vertices share the same instance of the edge. This makes it easy to manipulate with undirected edge data (length, cost, flow or even direction). However it uses extra memory for pointers.

小开

Another good resource: Khan Academy - "Representing Graphs"

Besides adjacency list and adjacency matrix, they list "edge lists" as a 3rd type of graph representation. An edge list could be interpreted as a list of "edge objects" like those in Thomas's "objects and pointers" answer.

Advantage: We can store more information about the edge (mentioned by Michal)

Disadvantage: It's a very slow data structure to work with:

  • Lookup an edge: O(log e)
  • Remove an edge: O(e)
  • Find all nodes adjacent to a given node: O(e)
  • Determine whether there exists a path between two nodes: O(e^2)

e = number of edges


提交答案