English subtitles

← 13ps-04 Cover By Tree Solution

Get Embed Code
1 Language

Showing Revision 1 created 10/24/2012 by Amara Bot.

  1. Alright, let's go ahead and take a look at this code.
  2. We start out by grabbing the length of the n by n matrix
  3. that we're interested in, and we store that in n.
  4. Then we said v equaled -1; this is the vertex that we're currently looking at.
  5. Now, for every element in the graph, every vertex in the graph,
  6. we check if the assignment is none.
  7. And if so, we set that to be the vertex that we are looking at right now.
  8. Then we check, for each of those vertices, whether there is an edge
  9. between that and any other vertices.
  10. If there is, then either the assignment for i or j, the vertex we're starting at
  11. and the vertex we're ending at, should be 1.
  12. If both are zero, then this isn't going to work, so we return float infinity.
  13. Now if we fall through checking every single element, and we don't get
  14. float infinity as a return value, then if v is still equal to -1,
  15. then we set the size equal to zero, and for every element in the assignment
  16. that is equal to 1, we increase the size of the vertex cover until we return the total size.