English subtitles

← Zero One Graph Solution - Intro to Theoretical Computer Science

Get Embed Code
1 Language

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

  1. So the times you see are two given vertices are connected.
  2. Well, if we can access every element of the adjacency matrix in constant time,
  3. well then we can just check that given element in the matrix in constant time.
  4. Similarly, the time required to add and edge between two vertices--
  5. well, we can access that element in constant time and then just change it from 0 to 1
  6. that's constant time, and similarly, we can change from 1 to 0 to remove an edge
  7. between two vertices.
  8. Now, the time to find the degree of a vertex.
  9. It's a little bit harder to find the degree of a vertex where the degree is
  10. the number of vertices that are connected to it.
  11. In order to find all the vertices that are connected to a given vertex, well, we have to go down
  12. that row or that column one by one.
  13. Since we have to do this n times, well this is what it end at least.
  14. Now, these questions are somewhat tricky and memory required to represent a graph
  15. with O(n) edges as an adjacency matrix and O(n²) edges as an adjacency matrix.
  16. This is a bit of a trick question. If we have n vertices, then we have an n x n,
  17. which is n² total elements.
  18. So we're going to need n² memory slots to put each of those elements in.
  19. You can pare that down a little bit if you're really clever, but if any of adjacency matrix approach,
  20. then the memory required isn't really a function of the number of edges
  21. so much as it is the number of vertices.
  22. So we want to go ahead and put n² for both of those.