2

Suppose there are 236 web pages and on average each web page has 24 hyperlinks. Consider the directed graph with one vertex per web page and an edge between two vertices if there is a hyperlink between the web pages the vertices represent. How many terabytes would it take to represent the graph using an adjacency matrix? Using an adjacency list? My question is what would be the main difference between the list and the matrix?

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
user597861
  • 93
  • 2
  • 9
  • Is this homework? Have you tried to work out how much storage each approach would require? – Flexo Feb 10 '11 at 21:47
  • 3
    This is not a real question... IMO. –  Feb 10 '11 at 21:47
  • this is homework and i'm trying to come with an answer my what i was thinking is that for a list it would be ((2^36)*(2^4))^2 and for the matrix it would be (2^36)*(2^4) but i don't think this is right:( – user597861 Feb 10 '11 at 21:53
  • 2
    @Jens: The answer depends on a lot of factors and is too vague to answer properly. For instance, I could compress the data with different compression algorithms, giving a different answer each time... –  Feb 10 '11 at 21:55
  • The matrix has to be square. The only thing that influences its size is the number of vertices. For lists you need one list per vertex (even if it's empty) and then one entry in the list for each link. – Flexo Feb 10 '11 at 21:56
  • @user597861- Well, now I feel bad because I just did your homework for you. :-( Please tag your questions as homework questions if they are for homework; otherwise you're almost blatantly cheating and being dishonest. – templatetypedef Feb 10 '11 at 22:01

1 Answers1

4

To answer your question, "What is the main difference between a list representation and matrix representation of a matrix?"

A list representation of a graph is usually a list of tuples, where each element of the list is a node, and the tuples are the nodes connected to it. Say we have 3 nodes A, B, C, so we will have a list of length 3. Say there is a node from A->B, then element in the Ath position, say the first element, will contain the node B. Say there is also a link from A->C, the first element will contain B and C. The total space required for an adjacency list is (space to represent a node) * (number of edges).

On the other hand, a matrix representation is a matrix, usually implemented as a 2-d array, where every node is listed on both the row and column axis. If there is a link between 2 nodes, then mark that spot in the matrix. For example, if we have 3 nodes A, B, C, we have a 3x3 array array. Let's call A=index 0, B=index 1, C=index 2, and suppose we have a link from A -> B, then fill in a 1 at array[0][1]. If our graph was undirected, we'd also add a 1 to the spot at array[1][0]. Total space required is the number of nodes N^2 times the space required by each link (can be done with 1 bit, 0 or 1), so total = N^2.

A list is good for sparse graphs because it doesn't require any extra storage. That is, links that don't exist aren't represented by anything. By contrast, if our graph is very dense, then a matrix representation is better because every possible link is denoted by only 1 bit (0 or 1). As you can see from the examples above, the total space required by a list representation is a function of the number of edges, while the space for a matrix representation is a function of the number of nodes.

Now think about your specific problem. How many total nodes would you have? Total edges? Does that seem sparse or dense?

prelic
  • 4,450
  • 4
  • 36
  • 46