Return to Video

13ps-04 Cover By Tree Solution

  • 0:00 - 0:02
    Alright, let's go ahead and take a look at this code.
  • 0:02 - 0:06
    We start out by grabbing the length of the n by n matrix
  • 0:06 - 0:09
    that we're interested in, and we store that in n.
  • 0:09 - 0:14
    Then we said v equaled -1; this is the vertex that we're currently looking at.
  • 0:14 - 0:19
    Now, for every element in the graph, every vertex in the graph,
  • 0:19 - 0:22
    we check if the assignment is none.
  • 0:22 - 0:26
    And if so, we set that to be the vertex that we are looking at right now.
  • 0:26 - 0:31
    Then we check, for each of those vertices, whether there is an edge
  • 0:31 - 0:34
    between that and any other vertices.
  • 0:34 - 0:41
    If there is, then either the assignment for i or j, the vertex we're starting at
  • 0:41 - 0:44
    and the vertex we're ending at, should be 1.
  • 0:44 - 0:50
    If both are zero, then this isn't going to work, so we return float infinity.
  • 0:50 - 0:53
    Now if we fall through checking every single element, and we don't get
  • 0:53 - 0:58
    float infinity as a return value, then if v is still equal to -1,
  • 0:58 - 1:03
    then we set the size equal to zero, and for every element in the assignment
  • 1:03 -
    that is equal to 1, we increase the size of the vertex cover until we return the total size.
Cím:
13ps-04 Cover By Tree Solution
Team:
Udacity
Projekt:
CS313 - Theoretical Computer Science
Duration:
01:10
Amara Bot hozzáadott egy fordítást

English subtitles

Felülvizsgálatok