English 字幕

← Complete Graph Solution - Intro to Algorithms


Showing Revision 2 created 05/25/2016 by Udacity Robot.

  1. I told you to use a mathematical formula, so I cheated a little bit.
  2. I wrote a little piece of code to actually generate a complete graph
  3. and then return the number of edges in that graph.
  4. To make a complete graph, I just looped through all the pairs of nodes,
  5. and if one node was smaller than the other, then I made a link between them.
  6. That was mainly to just make sure I didn't make a link from nodes to themselves.
  7. There is no reason not to make a link the other way.
  8. It would have not counted against the total, but this seemed nicer and cleaner.
  9. Let's look at what happens if you loop on all the different values of n
  10. from 1 to 9 and print n and the number of edges in the clique.
  11. A graph with one node has no edges.
  12. A graph with 2 nodes fully connected has one edge, 3 has three--that's a triangle,
  13. 4 has six, which is the square with the x through the middle of it,
  14. 5 is that pentagram-looking thing that we just showed a minute ago,
  15. and it continues growing up like that.
  16. With that as our insight, can we actually write down what the formula is
  17. for a graph with n nodes?
  18. Essentially what happens is each node gets an edge to each other node,
  19. which we can write as each node has an edge to each other node.
  20. Notice what happens if we use that as our formula, we're going to count this edge,
  21. as it goes from this node to this node.
  22. We're also going to count it again, as it goes from this node to this node.
  23. We've double counted everything, so that should be our formula,
  24. which is Î(n²). Let's just double-check this.
  25. If we print n, clique (n), which I counted by actually creating the clique,
  26. compared that to the formula n * (n -1)/2,
  27. you can see that it matches up perfectly.
  28. So, really the answer that you should have given is this--
  29. shouldn't have bothered with any of this creating of stuff.
  30. Now, in addition to all those graphs where the growth rate was linear, we now have one that's quadratic.