GraphAcademy/prims.html at master · Nitin-Rajasekar/GraphAcademy · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
<!DOCTYPE html>
<html>
<title>Graph_academy</title>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<link rel="stylesheet" href="https://www.w3schools.com/w3css/4/w3.css">
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Nunito">
<link rel="stylesheet" type="text/css" href="mystyle.css">
<link rel="stylesheet" type="text/css" href=" https://maxcdn.bootstrapcdn.com/bootstrap/4.0.0/css/bootstrap.min.css ">
<link rel="stylesheet" type="text/css" href=" https://cdnjs.cloudflare.com/ajax/libs/font-awesome/4.7.0/css/font-awesome.min.css ">
<script src="alert/dist/sweetalert-dev.js"></script>
  <link rel="stylesheet" href="alert/dist/sweetalert.css">
  <script src="http://unpkg.com/sweetalert/dist/sweetalert.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/sweetalert2@7.26.9/dist/sweetalert2.all.min.js"></script>
  <script type="text/javascript">
function JSalert_e(){

	swal("Try again!", "Mistakes are the stepping stones to success", "error");
}


function JSalert_s(){

	swal("Congrats!", "One step closer to mastery", "success");
}


function JSalert_s_2(){

	swal("Congrats!", "The MST would consist of BD, DE, DC and CA", "success");
}
</script>
<style>
body, html {
  height: 100%;
  font-family: "Nunito", sans-serif;

}

.bgimg {
  background-position: 50% 35%;
  background-size: 110%;
    background-repeat: no-repeat;

  background-image: url("https://alchetron.com/cdn/vojtch-jarnk-d6805baf-4d09-402b-81eb-a999a4a98cc-resize-750.jpg");
  min-height: 75%;
    min-width: 55%;
}

.menu {
  display: none;
}

mark {
  background-color: dodgerblue;
  color: white;
}

</style>


<body>

<div class="w3-top">
  <div class="w3-bar w3-blue w3-wide w3-padding w3-card">
    <a href="index.html" class="w3-bar-item w3-button">Graph Academy</a>
    <!-- Float links to the right. Hide them on small screens -->
    <div class="w3-right w3-hide-small">


    </div>
  </div>
</div>


<!-- Header with image -->
<header class="bgimg w3-display-container w3-grayscale-min" id="home">

  <div class="w3-display-middle w3-center">
    <span class="w3-padding w3-black w3-opacity-min" style="font-size:90px">Prim's</span>
  </div>

</header>

<!-- Add a background color and large text to the whole page -->
<div class="w3-sand w3-grayscale w3-large">

<!-- About Container -->
<div class="w3-container" id="about">
  <div class="w3-content" style="max-width:700px" >
  <br><br><br>
    <center><h5><mark>What does it do ?</mark></h5></center><br>
    <p>Prim's algorithm is used to help one find the minimum spanning tree of a graph.</p>

     <br><br><br>
    <center><h5><mark>A minimum spanning tree ?</mark></h5></center><br><br>
    <p>A minimum spanning tree is a subset of a connected undirected graph that connects all vertices, and has the minmum possible weight of any subset that satisfies these conditions.</p>

 <center><h5><mark>What's the idea ?</mark></h5></center><br><br>

     <p>
     1) Choose a starting vertex A, and add it to the MST.<br><br>
     2) Choose the lowest-weighted edge which A is a part of (connecting it to an unvisited node), say AB, such that including it in the MST will not lead to a cycle.<br>
        Add it to the MST.<br><br>
     3) Now similarly consider the lowest weighted edge which any of the already included vertices (A and B here) are a part of, say BC (again, no cycle).<br>
        Add it to the MST as well.<br><br>
     4) Now do the same thing with the updated vertex set, and so on..until all the vertices have been accounted for.<br><br>


     <div class="wrapper bg-white rounded">
    <div class="content"> <a href="#"></span></a>
       <p class="text-muted">Test yourself</p>
        </p>

        <p class="text-justify h5 pb-2 font-weight-bold">Consider the following graph..<br>
      <img src="https://i.imgur.com/VHFmi1S.png">
      <p>
        <p class="text-justify h5 pb-2 font-weight-bold">Say we start with vertex..B<br>
      Which three edges would you add to the MST first ?</p>
        <div class="options py-3"> <label class="rounded p-2 option" onclick="JSalert_s()"> BD, DE, DC <input type="radio" name="radio">  </label> <label class="rounded p-2 option" onclick="JSalert_e()">  BD, DE, EC <input type="radio" name="radio">  </label> <label class="rounded p-2 option" onclick="JSalert_e()"> BC, CA, CE <input type="radio" name="radio">  </label> <label class="rounded p-2 option" onclick="JSalert_e()"> BD BC DE <input type="radio" name="radio">  </label> </div>


        <p class="text-justify h5 pb-2 font-weight-bold">What would be the length of the resultant MST ?<br></p>
        <div class="options py-3"> <label class="rounded p-2 option" onclick="JSalert_e()"> 14 <input type="radio" name="radio">  </label> <label class="rounded p-2 option" onclick="JSalert_e()">  7 <input type="radio" name="radio">  </label> <label class="rounded p-2 option" onclick="JSalert_s_2()"> 10 <input type="radio" name="radio">  </label> <label class="rounded p-2 option" onclick="JSalert_e()"> 12 <input type="radio" name="radio">  </label> </div>

    </div>
</div>


    <br><br><br><br><br><br><br><br><br><br><br><br><br><br>


</body>
</html>