reset password
Author Message
hal255
Posts: 51
Posted 22:41 Oct 22, 2014 |

#2:

I do not know how to approach this problem for finding the MAXIMUM number of edges. I really thought it would be the same answer as number 1.

#3:

I do not know how to get the right answer. I rewatched the video about adjacency lists, and it appears to be theta of 2|E|. I counted once by list of edges, and each edge points to its endpoint... thus 2|E|. Is that correct?

#5:

Visually, I pictured all the edges going towards a particular V, so I thought the answer would be E, but I realized not all the edges would go to that vertex, so E would be wrong. Thus, I pictured going through all the vertices and check if they connect to that particular V and this should give me the right answer. Is this correct?

#6.

I thought it was V^2 because worst case scenario would be traversing through the entire matrix, checking each vertex if there's an edge, and not finding an edge. Since the size of the matrix is V x V, I thought the result would be V^2.

skim144
Posts: 63
Posted 23:04 Oct 22, 2014 |

#2.

Talking about #1, the max number of edges in undirected graph is given by n(n-1)/2. Now this is directed graph, for every edge there should be twice as many, because (A to B) (B to A) are distinct edges. So the answer is n(n-1).

#3

Yes

#5

I got this one wrong, so here is how I think. For a particular vertex u, the maximum number of its adjacent vertex would be

|V| - 1 ( -1 comes from u itself). You just need to iterate that one row in the matrix. So the answer would be O(|V|). Somebody correct me if I'm wrong on this one!

#6

Given an index i and j, you just need to check that index(think about ArrayList, you don't need to iterate through the whole array, since you know which index you want to check). So it would only take constant time.

hal255
Posts: 51
Posted 23:11 Oct 22, 2014 |

Wow, number 6, I completely misread what it asked for. Thanks for the response. 

vsluong4
Posts: 87
Posted 23:39 Oct 22, 2014 |

Rewatch the video on Adjacency Lists, you seem to be missing the point.

 

Yes, the AL is going to have redundant data (it's not being 100% efficient at data storage)

No, we are not going to modify it so it is more efficient

Yes, you are free to go and do that on your own