tag:blogger.com,1999:blog-13848395965211884672024-03-19T02:35:00.595-07:00Data Structures NotesNashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.comBlogger44125tag:blogger.com,1999:blog-1384839596521188467.post-7678130791728256692009-03-30T09:51:00.000-07:002009-04-17T06:08:15.365-07:00Prim-Jarnik's algorithm for extracting Minimum Spanning Tree (MST)This algorithm comes under the greedy method, which means that the objects are chosen to join a growing collection by iteratively picking an object that minimizes some cost function.<br /><br />Now, taking account of the above mentioned greedy method, the Prim-Jarnik's algorithm is similar to the <a href="http://datastructuresnotes.blogspot.com/2009/03/find-shortest-path-using-dijkstras.html">Dijkstra's shortest-path algorithm</a> to grow the Minimum Spanning Tree (MST) from a single cluster starting with a randomly chosen single root vertex.<br /><br />The Prim-Jarnik's algorithm can be broken down as follows:<br /><span style="font-weight: bold;">Step 1</span>: Define the starting "cloud" of vertices [C] by selecting some random vertex [v] initially<br /><span style="font-weight: bold;">Step 2</span>: Iteratively choose a min-weight edge [e=(v,u)], thereby connecting a vertex [v] in the cloud [C] to a vertex [u] outside of [C]. After choosing [e] the vertex [u] is brought into the cloud [C] continuously until a spanning tree emerges.<br /><br /><br /><span style="font-weight: bold;">Pseudo-code of the Prim-Jarnik's algorithm</span><br />// Prim-Jarnik(G) [Time complexity = O(m * log * n)]<br />// Input: A weighted connected graph [G] with n number of vertices & m number of edges<br />// Output: A minimum spanning tree [T] for [G]<br /><br />// Pick a root vertex [v] of [G]<br /><span style="font-family:courier new;">D[v] <- 0</span><br /><br />// All vertices connected to the root vertex, hence it necessary to define the cost function.<br />// The cost function "D[u] = +infinity" when vertex [u] doesn't connect to vertex [v].<br /><span style="font-family:courier new;">for each vertex u != v do</span><br /><span style="font-family:courier new;">D[u] <- +infinity</span><br /><br />// Initialise the MST<br /><span style="font-family:courier new;">T <- null </span><br /><br />// Initialise a priority queue Q with an entry ((u,null),D[u]) for each vertex [u],<br />// where (u,null) is the element & D[u] in the key<br /><span style="font-family:courier new;">while Q is not empty do</span><br /><span style="font-family:courier new;"> (u,e) <- Q.removeMin()</span><br /><span style="font-family:courier new;"> Add vertex u and edge e to T</span><br /><br />// Perform the relaxation procedure on the edge of the vertex [z] adjacent to [u]<br /><span style="font-family:courier new;">For each vertex z adjacent to u such that z is in Q do</span><br /><span style="font-family:courier new;"> if W((u,z)) <><br /><span style="font-family:courier new;"> D[z] <- W((u,z))</span><br /><span style="font-family:courier new;"> Change to (z,(u,z)) the element of vertex z in Q</span><br /><span style="font-family:courier new;"> Change to D[z] the key of vertex z in Q</span><br /><span style="font-family:courier new;">return the tree T</span></span><br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiEbi7Wbd_atIr8ab1_n1HPgQSu-4ro9q7KTm_nthCV4KvANofv5iXatKmO-nDGX1OGTVSrwOXIcT-CgqCFYOyX5irHhWjMY-twQZx2pESESjeWy3bwEPU-lCd7KSoQkuGfAvVceO2UV-E/s1600-h/Prim-JarnikAlgorithm01.jpg"><img style="cursor: pointer; width: 445px; height: 271px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiEbi7Wbd_atIr8ab1_n1HPgQSu-4ro9q7KTm_nthCV4KvANofv5iXatKmO-nDGX1OGTVSrwOXIcT-CgqCFYOyX5irHhWjMY-twQZx2pESESjeWy3bwEPU-lCd7KSoQkuGfAvVceO2UV-E/s320/Prim-JarnikAlgorithm01.jpg" alt="" id="BLOGGER_PHOTO_ID_5322670664665705714" border="0" /></a><br /><br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg8fUdtaNmKgXmsgSr8BJY8Dm67TbveVdEih5rG8qt_E-o9O7zniWd2M8letkne27HTBUda9_ZHxyw0KilTdyc2EobJTiVPfVetBoNvj3GijF9uJmARYMQYiAaf2niI47kzW6ITpmuV1pU/s1600-h/Prim-JarnikAlgorithm02.jpg"><img style="cursor: pointer; width: 445px; height: 291px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg8fUdtaNmKgXmsgSr8BJY8Dm67TbveVdEih5rG8qt_E-o9O7zniWd2M8letkne27HTBUda9_ZHxyw0KilTdyc2EobJTiVPfVetBoNvj3GijF9uJmARYMQYiAaf2niI47kzW6ITpmuV1pU/s320/Prim-JarnikAlgorithm02.jpg" alt="" id="BLOGGER_PHOTO_ID_5322670664900555170" border="0" /></a><br /><br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhm4zwSRSsHLqCOBD9gNLN1z5OmnIvBL3iAVbt4N9Jc8XVi9AWV1uR69KuugkPf7jqLCd9dLM3toPq9ez1PodAnsQbIpJsCKUAdL0shDg-7PUat30DKrFtFSCyeq3UpZXHyMmhF4ItDkiY/s1600-h/Prim-JarnikAlgorithm03.jpg"><img style="cursor: pointer; width: 446px; height: 285px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhm4zwSRSsHLqCOBD9gNLN1z5OmnIvBL3iAVbt4N9Jc8XVi9AWV1uR69KuugkPf7jqLCd9dLM3toPq9ez1PodAnsQbIpJsCKUAdL0shDg-7PUat30DKrFtFSCyeq3UpZXHyMmhF4ItDkiY/s320/Prim-JarnikAlgorithm03.jpg" alt="" id="BLOGGER_PHOTO_ID_5322670664065852962" border="0" /></a>Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-74296594969658067862009-03-30T09:29:00.000-07:002009-04-03T07:24:53.379-07:00Kruskal's algorithm for extracting Minimum Spanning Tree (MST)This algorithm comes under the greedy method, which means that the objects are chosen to join a growing collection by iteratively picking an object that minimizes some cost function.<br /><br />Now, taking account of the above mentioned greedy method, the <span class="blsp-spelling-error" id="SPELLING_ERROR_0">Kruskal's</span> algorithm with a graph considers the edges in order of their weights to grow the Minimum Spanning Tree (MST) in clusters.<br /><br />The <span class="blsp-spelling-error" id="SPELLING_ERROR_1">Kruskal's</span> algorithm can be broken down as follows:<br /><span style="font-weight: bold;">Step 1</span>: In a given undirected graph [G] consider each vertex is in its own cluster all by itself i.e. if a [G] has four <span class="blsp-spelling-error" id="SPELLING_ERROR_2">vertices</span> then you have four cluster <span class="blsp-spelling-corrected" id="SPELLING_ERROR_3">initially</span><br /><span style="font-weight: bold;">Step 2</span>: Look for each edges in turn, ordered by increasing weight i.e. arrange all the edges in ascending order<br /><span style="font-weight: bold;">Step 3</span>: Start with the smallest weighing edge. If this edge connects two different clusters then it is considered as the min-weight "bridge" edge [e] and added to the set of edges of the MST. In this initial stages, due to addition of [e] to the MST (i.e. the growth of the MST), the two clusters then are merged into a single cluster. However, if a given [e] connects to two <span class="blsp-spelling-error" id="SPELLING_ERROR_4">vertices</span> that are already in the identified cluster then this [e] is discarded.<br /><span style="font-weight: bold;">Step 4</span>: Now iteratively the algorithm adds enough [e] to a set of edges of spanning tree, it terminates and outputs this tree as the MST.<br /><br /><br /><span style="font-weight: bold;">Pseudo-code of the <span class="blsp-spelling-error" id="SPELLING_ERROR_5">Kruskal's</span> algorithm</span><br />// <span class="blsp-spelling-error" id="SPELLING_ERROR_6">Kruskal</span>(G) [Time complexity = O(m * log * n)]<br />// Input: A simple connected weight graph [G] with [n] <span class="blsp-spelling-error" id="SPELLING_ERROR_7">vertices</span> and [m] edges<br />// Output: A minimum spanning tree [T] for [G]<br /><span style="font-family:courier new;">for each vertex [v] in [G] do</span><br /><span style="font-family:courier new;"> Define an elementary cluster C(v) <- {v}</span><br /><br />// Initialise a priority queue Q to contain all edges in [G], using the weights as keys<br /><span style="font-family:courier new;">T <- null </span><br />// The above [T] will ultimately contain the edges of the MST<br /><br /><span style="font-family:courier new;">while [T] has fewer then n-1 edges do</span><br /><span style="font-family:courier new;"> (u,v) <- Q</span><span style="font-family:courier new;">.<span class="blsp-spelling-error" id="SPELLING_ERROR_8">removeMin</span>()</span><br />// Let C(v) be the cluster containing v, and let C(u) be the cluster containing u.<br /><span style="font-family:courier new;"> if C(v) != C(u) the</span><br /><span style="font-family:courier new;"> Add edges (v,u) to T</span><br /><span style="font-family:courier new;"> Merge C(v) & C(u)</span><br />// The above union of C(v) & C(u) <span class="blsp-spelling-corrected" id="SPELLING_ERROR_9">yields</span> a single cluster<br /><span style="font-family:courier new;">return tree T<br /><br /></span><span style="font-weight: bold;">Example below shows the Kruskal's algorithm that extracts the MST from a spanning tree</span>. This spanning tree depicts a subset of Finnish intercity roadways route:<br /><br />--------------------------------------------<br /><span style="font-weight: bold;">Stage 1.</span><br />--------------------------------------------<br />Main cluster (C) contains the following vertices: null<br />Elementary Cluster (C1) contains the following vertices: null<br /><br />Priority Queue (Q)<br />------------------<br />----<br />110<br />----<br />137<br />---<br />141<br />---<br />164<br />---<br />177<br />---<br />294<br />---<br />381<br />---<br />409<br />---<br />534<br />---<br />549<br />---<br />------------------<br /><br />Set of min-weight "bridge" edges e = {null}<br />Set of discarded edges d = {null}<br /><br />--------------------------------------------<br /><span style="font-weight: bold;">Stage 2.</span><br />--------------------------------------------<br />Main cluster (C) contains the following vertices:null<br />Elementary Cluster (C1) contains the following vertices: Pori+Tampere<br /><br />Priority Queue (Q)<br />------------------<br />----<br />137<br />---<br />141<br />---<br />164<br />---<br />177<br />---<br />294<br />---<br />381<br />---<br />409<br />---<br />534<br />---<br />549<br />---<br />------------------<br /><br />Set of min-weight "bridge" edges e = {110}<br />Set of discarded edges d = {null}<br /><br />--------------------------------------------<br /><span style="font-weight: bold;">Stage 3.</span><br />--------------------------------------------<br />Main cluster (C) contains the following vertices:null<br />Elementary Cluster (C1) contains the following vertices: Pori+Tampere<br />Elementary Cluster (C2) contains the following vertices: Helsinki+Kouvola<br /><br />Priority Queue (Q)<br />------------------<br />---<br />141<br />---<br />164<br />---<br />177<br />---<br />294<br />---<br />381<br />---<br />409<br />---<br />534<br />---<br />549<br />---<br />------------------<br /><br />Set of min-weight "bridge" edges e = {110,137,}<br />Set of discarded edges d = {null}<br /><br />--------------------------------------------<br /><span style="font-weight: bold;">Stage 4.</span><br />--------------------------------------------<br />Main cluster (C) contains the following vertices:null<br />Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku<br />Elementary Cluster (C2) contains the following vertices: Helsinki+Kouvola<br /><br />Priority Queue (Q)<br />------------------<br />---<br />164<br />---<br />177<br />---<br />294<br />---<br />381<br />---<br />409<br />---<br />534<br />---<br />549<br />---<br />------------------<br /><br />Set of min-weight "bridge" edges e = {110,137,141}<br />Set of discarded edges d = {null}<br /><br />--------------------------------------------<br /><span style="font-weight: bold;">Stage 5.</span><br />--------------------------------------------<br />Main cluster (C) contains the following vertices:null<br />Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola<br /><br />Priority Queue (Q)<br />------------------<br />---<br />177<br />---<br />294<br />---<br />381<br />---<br />409<br />---<br />534<br />---<br />549<br />---<br />------------------<br /><br />Set of min-weight "bridge" edges e = {110,137,141,164,}<br />Set of discarded edges d = {null}<br /><br />--------------------------------------------<br /><span style="font-weight: bold;">Stage 6.</span><br />--------------------------------------------<br />Main cluster (C) contains the following vertices:null<br />Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola<br /><br />Priority Queue (Q)<br />------------------<br />---<br />294<br />---<br />381<br />---<br />409<br />---<br />534<br />---<br />549<br />---<br />------------------<br /><br />Set of min-weight "bridge" edges e = {110,137,141,164,}<br />Set of discarded edges d = {177,}<br /><br />--------------------------------------------<br /><span style="font-weight: bold;">Stage 7.</span><br />--------------------------------------------<br />Main cluster (C) contains the following vertices:null<br />Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola+Kuopio<br /><br />Priority Queue (Q)<br />------------------<br />---<br />381<br />---<br />409<br />---<br />534<br />---<br />549<br />---<br />------------------<br /><br />Set of min-weight "bridge" edges e = {110,137,141,164,294}<br />Set of discarded edges d = {177,}<br /><br />--------------------------------------------<br /><span style="font-weight: bold;">Stage 8.</span><br />--------------------------------------------<br />Main cluster (C) contains the following vertices:null<br />Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola+Kuopio<br /><br />Priority Queue (Q)<br />------------------<br />---<br />409<br />---<br />534<br />---<br />549<br />---<br />------------------<br /><br />Set of min-weight "bridge" edges e = {110,137,141,164,294,}<br />Set of discarded edges d = {177,381}<br /><br />--------------------------------------------<br /><span style="font-weight: bold;">Stage 9.</span><br />--------------------------------------------<br />Main cluster (C) contains the following vertices:null<br />Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola+Kuopio<br /><br />Priority Queue (Q)<br />------------------<br />---<br />534<br />---<br />549<br />---<br />------------------<br /><br />Set of min-weight "bridge" edges e = {110,137,141,164,294}<br />Set of discarded edges d = {177,381,409}<br /><br />--------------------------------------------<br /><span style="font-weight: bold;">Stage 10.</span><br />--------------------------------------------<br />Main cluster (C) contains the following vertices:null<br />Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola+Kuopio+Oulu<br /><br />Priority Queue (Q)<br />------------------<br />---<br />549<br />---<br />------------------<br /><br />Set of min-weight "bridge" edges e = {110,137,141,164,294,534,}<br />Set of discarded edges d = {177,381,409}<br /><br />--------------------------------------------<br /><span style="font-weight: bold;">Stage 11.</span><br />--------------------------------------------<br /><span style="font-weight: bold;">Main cluster (C) contains the following vertices = C1</span><br />Elementary Cluster (C1) contains the following vertices: Pori+Tampere+Turku+Helsinki+Kouvola+Kuopio+Oulu+Ivalo<br /><br />Priority Queue (Q)<br />------------------<br />null<br />------------------<br /><br />Set of min-weight "bridge" edges e = {110,137,141,164,294,534,549}<br />Set of discarded edges d = {177,381,409}<br /><br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjLDJrQipE0C48stWUcdPfE0WG7960eQ5ZNJjsHaIVfdy_z7Vpv4rav9U0FFtNt6YxYgqmcPEPuEJ_rq65v2qqeWsjFbg_Tv2IlU78DXTqCJznmt3TeJtIthdyIa7R0x_COXJTTnfEEKgM/s1600-h/KruskalAlgorithmExtractsMST-FinnishRoadways-RouteMap-Stages12.jpg"><img style="cursor: pointer; width: 286px; height: 320px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjLDJrQipE0C48stWUcdPfE0WG7960eQ5ZNJjsHaIVfdy_z7Vpv4rav9U0FFtNt6YxYgqmcPEPuEJ_rq65v2qqeWsjFbg_Tv2IlU78DXTqCJznmt3TeJtIthdyIa7R0x_COXJTTnfEEKgM/s320/KruskalAlgorithmExtractsMST-FinnishRoadways-RouteMap-Stages12.jpg" alt="" id="BLOGGER_PHOTO_ID_5320468487058898514" border="0" /></a><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjWU_ob4LVAmroqDptlP7hPT0f2IVYEu5f_qrHRy3y-M9Cv9We9mYdJMimApvc06xe_hPuDCvJFHBOvma5iPc6s543x2s4f8MjTmRr4SwPPaAugIsPIfrxazlZtcxRmQu1q1bo7_3gEOn4/s1600-h/KruskalAlgorithmExtractsMST-FinnishRoadways-RouteMap-Stages34.jpg"><img style="cursor: pointer; width: 303px; height: 320px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjWU_ob4LVAmroqDptlP7hPT0f2IVYEu5f_qrHRy3y-M9Cv9We9mYdJMimApvc06xe_hPuDCvJFHBOvma5iPc6s543x2s4f8MjTmRr4SwPPaAugIsPIfrxazlZtcxRmQu1q1bo7_3gEOn4/s320/KruskalAlgorithmExtractsMST-FinnishRoadways-RouteMap-Stages34.jpg" alt="" id="BLOGGER_PHOTO_ID_5320468336498771794" border="0" /></a><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjAlh9fB5T1z82EJmrvhOem6n13uWn-5OBal9LVj3bGEkcrYL4Xu1C2LJlyWuo5YP_TxRvhZSSFpyKb272uADWhazuUipb9lNHjBiT28kzuARayyfDzjrHJjWFAQkjkNEpRVWe20iDIGCo/s1600-h/KruskalAlgorithmExtractsMST-FinnishRoadways-RouteMap-Stages56.jpg"><img style="cursor: pointer; width: 302px; height: 320px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjAlh9fB5T1z82EJmrvhOem6n13uWn-5OBal9LVj3bGEkcrYL4Xu1C2LJlyWuo5YP_TxRvhZSSFpyKb272uADWhazuUipb9lNHjBiT28kzuARayyfDzjrHJjWFAQkjkNEpRVWe20iDIGCo/s320/KruskalAlgorithmExtractsMST-FinnishRoadways-RouteMap-Stages56.jpg" alt="" id="BLOGGER_PHOTO_ID_5320468331821041730" border="0" /></a><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg7ZXZiSyDpobY5j897CzeYyPZanSHvR0mE8ppccHKE0KmGa-p9ZKd-JZjXQmpYBI3AfW5twysmSv_8ibrJPyiVKFV3kIygm9ghBieUpp3TEFIKOcVVg6UA5JbhuaJ2SNsGewUYe2A_-fU/s1600-h/KruskalAlgorithmExtractsMST-FinnishRoadways-RouteMap-Stages78.jpg"><img style="cursor: pointer; width: 304px; height: 320px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg7ZXZiSyDpobY5j897CzeYyPZanSHvR0mE8ppccHKE0KmGa-p9ZKd-JZjXQmpYBI3AfW5twysmSv_8ibrJPyiVKFV3kIygm9ghBieUpp3TEFIKOcVVg6UA5JbhuaJ2SNsGewUYe2A_-fU/s320/KruskalAlgorithmExtractsMST-FinnishRoadways-RouteMap-Stages78.jpg" alt="" id="BLOGGER_PHOTO_ID_5320468333935951474" border="0" /></a><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi-4bNW1r1gHPUiWUGiTy9WMbhWNC1VKAbMwN9Oh1p1K9KohnMir28vjUW0HritGVNp7aYkDbIsPqdVmi4IJGK_jtoTmNAe5x0aslrqjjb4KSF0strfoM5NHZI01XvcGHLoJO_y3kwSM0A/s1600-h/KruskalAlgorithmExtractsMST-FinnishRoadways-RouteMap-Stages910.jpg"><img style="cursor: pointer; width: 308px; height: 320px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi-4bNW1r1gHPUiWUGiTy9WMbhWNC1VKAbMwN9Oh1p1K9KohnMir28vjUW0HritGVNp7aYkDbIsPqdVmi4IJGK_jtoTmNAe5x0aslrqjjb4KSF0strfoM5NHZI01XvcGHLoJO_y3kwSM0A/s320/KruskalAlgorithmExtractsMST-FinnishRoadways-RouteMap-Stages910.jpg" alt="" id="BLOGGER_PHOTO_ID_5320468327165813506" border="0" /></a><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgKapugASXlDFRIUG1QsSGOJd1PKFJ_ozrs64GIoROJaMisHtlja3zlfrEyk0_cjDTm16fcQZKa2Re5HA5_4aV0GdY0bojTRMarjjGN8fvlL4Rmd9kVlolcxmFhSNguD1pPOybVDGoGXL8/s1600-h/KruskalAlgorithmExtractsMST-FinnishRoadways-RouteMap-Stage11.jpg.png"><img style="cursor: pointer; width: 146px; height: 320px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgKapugASXlDFRIUG1QsSGOJd1PKFJ_ozrs64GIoROJaMisHtlja3zlfrEyk0_cjDTm16fcQZKa2Re5HA5_4aV0GdY0bojTRMarjjGN8fvlL4Rmd9kVlolcxmFhSNguD1pPOybVDGoGXL8/s320/KruskalAlgorithmExtractsMST-FinnishRoadways-RouteMap-Stage11.jpg.png" alt="" id="BLOGGER_PHOTO_ID_5320468319122147778" border="0" /></a>Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-80933560657595001902009-03-30T08:04:00.000-07:002009-04-03T06:56:27.635-07:00Spanning Tree & Minimum Spanning Tree (MST)<span style="font-weight: bold;">Spanning Tr</span><span style="font-weight: bold;">ee </span>- A tree that contains every vertex of a connected graph G is referred to as a spanning tree. The below figure depicts the Finnish intercity roadways route as a sapnning tree.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhADIbO213qdtI7ncwz1yujCOTx6U7iGdL2yTILEKXK5w6xkDLYy-aigwE8Uqm_6fFl9RcZHidFxauXfUsZRWmoqq_U-g4XmT9-y5qmixZfoYO8CeEb3w2JGXV9jDmQRaA8NWh9IETs6l0/s1600-h/SpanningTree-FinnishRoadways-RouteMap.jpg"><img style="cursor: pointer; width: 155px; height: 320px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhADIbO213qdtI7ncwz1yujCOTx6U7iGdL2yTILEKXK5w6xkDLYy-aigwE8Uqm_6fFl9RcZHidFxauXfUsZRWmoqq_U-g4XmT9-y5qmixZfoYO8CeEb3w2JGXV9jDmQRaA8NWh9IETs6l0/s320/SpanningTree-FinnishRoadways-RouteMap.jpg" alt="" id="BLOGGER_PHOTO_ID_5320438993873332866" border="0" /></a><br /><br /><span style="font-weight: bold;">Minimum Spanning Tree (MST) </span>- the problem of computing a spanning tree with the smallest total weight is known as the Minimum Spanning Tree problem. The below figure depicts the MST that houses a collection of smallest weighted routes between the Finnish cities. Routes not taken into the MST are: 177,381,409.<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgY7EBdp5TlnZSlZMMvPH_Zopj_IQq-r7hOxHQ5g7RlX29eDFFh3r-2uibtrGLd-OG9pB2hAJV0WuBstbPo2Wv6J1YhJKilHg7HdG4-SOVzJXLsJeYZOTgjuD882VVSeYXFntKICbbq7L8/s1600-h/MST-FinnishRoadways-RouteMap.jpg"><img style="cursor: pointer; width: 150px; height: 320px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgY7EBdp5TlnZSlZMMvPH_Zopj_IQq-r7hOxHQ5g7RlX29eDFFh3r-2uibtrGLd-OG9pB2hAJV0WuBstbPo2Wv6J1YhJKilHg7HdG4-SOVzJXLsJeYZOTgjuD882VVSeYXFntKICbbq7L8/s320/MST-FinnishRoadways-RouteMap.jpg" alt="" id="BLOGGER_PHOTO_ID_5320463220369893810" border="0" /></a><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://3.bp.blogspot.com/_nx3c2uD12Vc/SdXNzkx1AII/AAAAAAAAA9w/qSTuAfVd8lE/s1600-h/MST-PoriToIvalo-FinnishRoadways-RouteMap.jpg"><br /></a>Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-42987892420707789452009-03-27T10:38:00.000-07:002009-03-27T10:43:09.570-07:00Application of a Binary TreeThe binary tree are applicable in the below mentioned fields:<br />- Used in the compilers of high-level programming languages for intermediate representation<br />- Used as a <span class="blsp-spelling-corrected" id="SPELLING_ERROR_0">searching</span> technique<br />- Used in databases for storing data<br />- To solve arithmetic expressionsNashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-64800111452664555632009-03-27T10:30:00.000-07:002009-03-27T10:34:31.910-07:00Exercise-Binary Tree ConstructionGiven data items: 17, 6, 3, 9 ,12, 15, 1, 18, 22<br />The resulting binary tree is:<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEinGVGjCnRDY-jojZ6IwUfnQGJrj7YEuqdX4AvMenzD8LS3A3a5-LXevXnMePXNNtM1xG_D6KsVWTZRlLdx15UPGiOsju9csCg4H5FJ6r9CoUWgPSE7-RwKHow1LfCRgzHtRxYeCEQxTbA/s1600-h/BinaryTree-Exercise.JPG"><img style="cursor: pointer; width: 320px; height: 176px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEinGVGjCnRDY-jojZ6IwUfnQGJrj7YEuqdX4AvMenzD8LS3A3a5-LXevXnMePXNNtM1xG_D6KsVWTZRlLdx15UPGiOsju9csCg4H5FJ6r9CoUWgPSE7-RwKHow1LfCRgzHtRxYeCEQxTbA/s320/BinaryTree-Exercise.JPG" alt="" id="BLOGGER_PHOTO_ID_5317922146657125074" border="0" /></a>Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-89667997278210266572009-03-27T10:04:00.000-07:002009-03-27T10:42:08.013-07:00What is a Binary Tree?A binary tree embodies a finite set of data items that is either empty or partitioned into three disjoint subsets. The first part contains a single data item referred to as the root of the binary tree, other two data items are left and right <span class="blsp-spelling-error" id="SPELLING_ERROR_0"><span class="blsp-spelling-error" id="SPELLING_ERROR_0">subtrees</span></span>. These data items is referred to as nodes of the binary tree.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhVt8F4RI9j1-5eCWzkN9NcGo4ORyxgvQaThUBLneqD-6iZX7QEPnIeYrPNzXCbgpxVpLM73m-x9JKuBRsCsbriBWKOgumD-7cg3RoyaC3e2FrgRaXBQf0K52KFI5EW_4JvXzodaLgGFmc/s1600-h/BinaryTree.JPG"><img style="margin: 0pt 10px 10px 0pt; float: left; cursor: pointer; width: 201px; height: 118px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhVt8F4RI9j1-5eCWzkN9NcGo4ORyxgvQaThUBLneqD-6iZX7QEPnIeYrPNzXCbgpxVpLM73m-x9JKuBRsCsbriBWKOgumD-7cg3RoyaC3e2FrgRaXBQf0K52KFI5EW_4JvXzodaLgGFmc/s320/BinaryTree.JPG" alt="" id="BLOGGER_PHOTO_ID_5317920235562310018" border="0" /></a>From this figure we can <span class="blsp-spelling-corrected" id="SPELLING_ERROR_1">portray</span> the <span class="blsp-spelling-corrected" id="SPELLING_ERROR_2">following</span>:<br />A - Root node of the binary tree<br />A - Parent node of the nodes B & C<br />B & C - <span class="blsp-spelling-corrected" id="SPELLING_ERROR_3">Children</span> nodes of A and these nodes are in a level one more than the root node A<br />C - Right child node of A<br />B - Left child node of A<br />D & E - These node are without a child, so they are referred to as leafs or external nodes<br />B & C - These nodes have a child each, so they are referred to as internal nodes<br /><br /><span style="font-weight: bold;">Depth </span>of this binary tree - The longest path from the root node A to any leaf node, for example D node. Therefore, the depth of this binary tree is two.<br /><span style="font-weight: bold;" class="blsp-spelling-error" id="SPELLING_ERROR_4"><span class="blsp-spelling-error" id="SPELLING_ERROR_1">Indegree</span></span><span style="font-weight: bold;"> </span>of a node - The number of edges merging into a node. For example, <span class="blsp-spelling-error" id="SPELLING_ERROR_5"><span class="blsp-spelling-error" id="SPELLING_ERROR_2">indegree</span></span> of the node B is one i.e. one edge merges.<br /><span style="font-weight: bold;" class="blsp-spelling-error" id="SPELLING_ERROR_6"><span class="blsp-spelling-error" id="SPELLING_ERROR_3">Outdegree</span></span><span style="font-weight: bold;"> </span>of a node - The number of edges coming out from a node. For example, <span class="blsp-spelling-error" id="SPELLING_ERROR_7"><span class="blsp-spelling-error" id="SPELLING_ERROR_4">outdegree</span></span> of the node A is two i.e. two edges comes out of this root node.<br /><br /><span class="blsp-spelling-corrected" id="SPELLING_ERROR_5">Concerning</span> the binary trees, do refer to the following blog entries:<br />- <a href="http://datastructuresnotes.blogspot.com/2009/03/exercise-binary-tree-construction.html">Exercise-Binary Tree Construction</a><br />- <a href="http://datastructuresnotes.blogspot.com/2009/03/application-of-binary-tree.html">Application of a Binary Tree</a>Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com2tag:blogger.com,1999:blog-1384839596521188467.post-24707483049256219072009-03-27T08:14:00.000-07:002009-03-27T09:38:50.355-07:00What is a Complete Binary Tree?A strictly binary tree of depth 'd' in which all the leaves are at level 'd' i.e. there is non empty left or right subtrees and leaves are populated at the same level.<br />In a complete binary tree all the internal nodes have equal degree, which means that one node at the root level, two nodes at level 2, four nodes at level 3, eight nodes at level 4, etc, which the below figure represents:<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjWSLvTSc1BJJJmGUvnjqJkyIuPI3zJYglynCTYN-7niNPGT_DKU_qNalqxKeWDfmPqyxP3VOhyX9RI8Wp4TrVhNOZHB259eIc81H-3RBB-5zLxGCA_4vclfDJ2GsTX1jU5TOPb8lnNnBs/s1600-h/CompleterBinaryTree.JPG"><img style="cursor: pointer; width: 353px; height: 158px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjWSLvTSc1BJJJmGUvnjqJkyIuPI3zJYglynCTYN-7niNPGT_DKU_qNalqxKeWDfmPqyxP3VOhyX9RI8Wp4TrVhNOZHB259eIc81H-3RBB-5zLxGCA_4vclfDJ2GsTX1jU5TOPb8lnNnBs/s320/CompleterBinaryTree.JPG" alt="" id="BLOGGER_PHOTO_ID_5317906994992281186" border="0" /></a>Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com1tag:blogger.com,1999:blog-1384839596521188467.post-17547939509008695612009-03-26T04:06:00.000-07:002009-03-29T02:52:17.072-07:00Hashing, Hash Data Structure and Hash Table<span style="font-weight: bold;">Hashing</span><span> is the process of mapping large amount of data item to a smaller table with the help of a <span style="font-weight: bold;">hashing function</span>. The essence of hashing is to facilitate the </span>next level searching method when compared with the linear or binary search. The advantage of this searching method is its efficiency to hand vast amount of data items in a given collection (i.e. collection size).<br /><span><br />Due to this hashing process, the result i</span><span>s </span><span>a </span><span style="font-weight: bold;">Hash data structure</span> that<span> can store </span><span>or </span><span>retrieve</span> data items in <span>an average time disregard to the collection size</span>.<br /><br /><span style="font-weight: bold;">Hash Table</span> is the result of storing the hash data structure in a smaller table which incorporates the <span>hash function</span><span> within itself. The <span style="font-weight: bold;">Hash Function </span>primarily is responsible</span> to map between the original data item and the smaller table itself. Here the mapping takes place with the help of <span style="font-weight: bold;">an output integer in a consistent range </span>produced when a given data item (any data type) is provided for storage<span style="font-weight: bold;"> </span>and this <span style="font-weight: bold;">output integer range</span> determines the location in the smaller table for the data item. In terms of implementation, the hash table is constructed with the help of an array and the <span>indices </span>of this array are associated to the output integer range.<br /><br />Hash Table Example :<br />Here, we construct a hash table for storing and retrieving data related to the citizens of a county and the social-security number of citizens are used as the indices of the array implementation (i.e. <span style="font-weight: bold;">key</span>). Let's assume that the table size is 12, therefore the hash function would be <span style="font-weight: bold;">Value modulus of 12</span>.<br /><br />Hence, the Hash Function would equate to:<br /><span style="font-weight: bold;">(sum of numeric values of the characters in the data item) %12 </span><br />Note! % is the modulus operator<br /><br />Let us consider the following social-security numbers and produce a hashcode:<br />120388113D => 1+2+0+3+8+8+1+1+3+13=40<br />Hence, (40)%12 => Hashcode=4<br /><br />310181312E => 3+1+0+1+8+1+3+1+2+14=34<br />Hence, (34)%12 => Hashcode=10<br /><br />041176438A => 0+4+1+1+7+6+4+3+8+10=44<br />Hence, (44)%12 => <span class="blsp-spelling-error" id="SPELLING_ERROR_0">Hashcode</span>=8<br /><br />Therefore, the <span class="blsp-spelling-error" id="SPELLING_ERROR_1">Hashtable</span> content would be as follows:<br />-----------------------------------------------------<br />0:empty<br />1:empty<br />2:empty<br />3:empty<br />4:occupied Name:Drew Smith <span class="blsp-spelling-error" id="SPELLING_ERROR_2">SSN</span>:120388113D<br />5:empty<br />6:empty<br />7:empty<br />8:occupied Name:Andy Conn <span class="blsp-spelling-error" id="SPELLING_ERROR_3">SSN</span>:041176438A<br />9:empty<br />10:occupied Name:Igor <span class="blsp-spelling-corrected" id="SPELLING_ERROR_4">Barton</span> <span class="blsp-spelling-error" id="SPELLING_ERROR_5">SSN</span>:310181312E<br />11:empty<br />-----------------------------------------------------Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com1tag:blogger.com,1999:blog-1384839596521188467.post-15079938034084905362009-03-24T05:18:00.000-07:002009-03-24T05:29:31.861-07:00Find shortest path using Dijkstra's AlgorithmThe Dijkstra's algorithm entails the following procedure:<br />- The breath-first approach is used to traversal the network, however the difference here is instead of a <span style="font-weight: bold;">queue data structure</span> to store the traversed vertex this algorithm uses a <span style="font-weight: bold;">priority queue</span>. The priority queue helps to <span style="font-weight: bold;">remove the items in order of values</span> rather than in order of being added to the queue.<br />- Have an account of <span style="font-weight: bold;">lowest total path weight</span> (i.e. weightsum), from the start vertex to the target vertex<br />- Have an account of<span style="font-weight: bold;"> immediate predecessor</span> in a given path for each vertex<br />- Have an account of the <span style="font-weight: bold;">items in the priority queue</span><br /><br /><span style="font-weight: bold;">Exercise</span>- Find the shortest path from <span>Pori </span>to <span>Kuopio</span><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg1Ocesq0zL-83NVCzuXLVTuC8Rn9_CbVgPPEESepxCdmRjwmOF0SIQd-1JJa2cKB7BCxqWhLOtwvTZuDa4diKWR-bxr-S14FiGcGgLx2VJ_f1cSOS6HPINXtAXDtE6kgk5x5Vsj2mQryI/s1600-h/NetworkofFinnishCities.jpg"><img style="cursor: pointer; width: 297px; height: 470px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg1Ocesq0zL-83NVCzuXLVTuC8Rn9_CbVgPPEESepxCdmRjwmOF0SIQd-1JJa2cKB7BCxqWhLOtwvTZuDa4diKWR-bxr-S14FiGcGgLx2VJ_f1cSOS6HPINXtAXDtE6kgk5x5Vsj2mQryI/s320/NetworkofFinnishCities.jpg" alt="" id="BLOGGER_PHOTO_ID_5316729150451978690" border="0" /></a><br /><br /><span style="font-weight: bold;">1</span><br />----------------------------------------------------<br />Vertex - Weightsum - Predecessor<br />----------------------------------------------------<br />Helsinki - nul - null<br />Ivalo - null - null<br />Kouvola - null - null<br />Kuopio - 409 - Pori<br />Oulu - null - null<br />Pori - 0 - Pori<br />Tampere - 110 - Pori<br />Turku - 141 - Pori<br />----------------------------------------------------<br />Visited: Pori<br />Priority Queue: (Tampere,110), (Turku,141), (Kuopio,409)<br /><br /><span style="font-weight: bold;">2</span><br />----------------------------------------------------<br />Vertex - Weightsum - Predecessor<br />----------------------------------------------------<br />Helsinki - 287 - Tampere<br />Ivalo - null - null<br />Kouvola - null - null<br />Kuopio - 404 - Tampere<br />Oulu - null - null<br />Pori - 0 - Pori<br />Tampere - 110 - Pori<br />Turku - 141 - Pori<br />----------------------------------------------------<br />Visited: Pori,(Tampere,110)<br />Priority Queue: (Turku,141),(Helsinki,287),(Kuopio,404),(Kuopio,409)<br /><br /><span style="font-weight: bold;">3</span><br />----------------------------------------------------<br />Vertex - Weightsum - Predecessor<br />----------------------------------------------------<br />Helsinki - 287 - Tampere<br />Ivalo - null - null<br />Kouvola - null - null<br />Kuopio - 404 - Tampere<br />Oulu - null - null<br />Pori - 0 - Pori<br />Tampere - 110 - Pori<br />Turku - 141 - Pori<br />----------------------------------------------------<br />Visited: Pori,(Tampere,110),(Turku,141)<br />Priority Queue: (Helsinki,287),(Kuopio,404),(Kuopio,409)<br /><br /><span style="font-weight: bold;">4</span><br />----------------------------------------------------<br />Vertex - Weightsum - Predecessor<br />----------------------------------------------------<br />Helsinki - 287 - Tampere<br />Ivalo - null - null<br />Kouvola - 364 - Helsinki<br />Kuopio - 404 - Tampere<br />Oulu - null - null<br />Pori - 0 - Pori<br />Tampere - 110 - Pori<br />Turku - 141 - Pori<br />----------------------------------------------------<br />Visited: Pori,(Tampere,110),(Turku,141),(Helsinki,287)<br />Priority Queue: (Kouvola,364),(Kuopio,404),(Kuopio,409)<br /><br /><span style="font-weight: bold;">5</span><br />----------------------------------------------------<br />Vertex - Weightsum - Predecessor<br />----------------------------------------------------<br />Helsinki - 287 - Tampere<br />Ivalo - null - null<br />Kouvola - 364 - Helsinki<br />Kuopio - 404 - Tampere<br />Oulu - 898 - Kouvola<br />Pori - 0 - Pori<br />Tampere - 110 - Pori<br />Turku - 141 - Pori<br />----------------------------------------------------<br />Visited: Pori,(Tampere,110),(Turku,141),(Helsinki,287),(Kouvola,364)<br />Priority Queue: (Kuopio,404),(Kuopio,409),(Oulu,898)<br /><br /><span style="font-weight: bold;">6</span><br />----------------------------------------------------<br />Vertex - Weightsum - Predecessor<br />----------------------------------------------------<br />Helsinki - 287 - Tampere<br />Ivalo - null - null<br />Kouvola - 364 - Helsinki<br />Kuopio - 404 - Tampere<br />Oulu - 898 - Kouvola<br />Pori - 0 - Pori<br />Tampere - 110 - Pori<br />Turku - 141 - Pori<br />----------------------------------------------------<br />Visited: Pori,(Tampere,110),(Turku,141),(Helsinki,287),(Kouvola,364),(Kuopio,404)<br />Priority Queue: (Kuopio,409),(Oulu,898)<br /><br />Therefore the shortest path from Pori to Kuopio is <span>Pori,(Tampere,110),(Kuopio,404)</span>Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-88498267659031199472009-03-20T10:44:00.000-07:002009-03-23T08:55:09.126-07:00What is a Network in the context of Graph?Network refers to a graph in which the edges are bound with weights. Here weights can be numbers assigned to a the edges. Hence, a graph of this nature is referred to as weighted graph or a network.Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-142083510000061662009-03-19T04:40:00.000-07:002009-03-23T08:50:11.021-07:00Graph Traversal MethodsThere are two possible traversal methods for a graph:<br />i. Breadth-First Traversal<br />ii. Depth-First Traversal<br /><br />i. <span style="font-weight: bold;">Breadth-First Traversal</span>: Traverse all the <span class="blsp-spelling-error" id="SPELLING_ERROR_0">vertices</span> starting from a given '<span style="font-weight: bold;">start vertex</span>'. Hence, such a traversal follows the '<span class="blsp-spelling-corrected" id="SPELLING_ERROR_6">neighbour</span>-first' principle by considering the following:<br />- No vertex is visited more than once<br />- Only those <span class="blsp-spelling-error" id="SPELLING_ERROR_2">vertices</span> that can be reached are visited<br /><br />Importantly here, we make use of the <span style="font-weight: bold;">Queue data structure</span>. In effect, we house the <span class="blsp-spelling-error" id="SPELLING_ERROR_3">vertices</span> in the queue that are to be visited soon in the order which they are added to this queue i.e. first-in first-out.<br /><br />Visiting a vertex involves returning the data item in the vertex and adding its <span class="blsp-spelling-corrected" id="SPELLING_ERROR_4">neighbour</span> <span class="blsp-spelling-error" id="SPELLING_ERROR_5">vertices</span> to the queue. However, we don't carryout any action under following conditions:<br />- if the <span class="blsp-spelling-corrected" id="SPELLING_ERROR_6">neighbour</span> is already present in the queue or if the <span class="blsp-spelling-corrected" id="SPELLING_ERROR_6">neighbour</span> has been already visited<br /><br />As an example of the breadth-first traversal, we traverse the major cities of Finland with by the <span>start vertex as</span> <span>'<span class="blsp-spelling-error" id="SPELLING_ERROR_7">Pori</span></span><span> </span>. Note! the <span class="blsp-spelling-corrected" id="SPELLING_ERROR_8">neighbour</span>(s) of a given vertex are added to the queue in alphabetical order.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhH_FRCmy_7FpO0z7BfLfBfCi_qkwVbq5mHXtiy_6leBlI0l_Km7FxxTOL-qauya-VMH6mzk53D43xL3ES23ZbVlnfAVrf6pL_toWNo1GnOv7TQv3haxjqfKGxD42O_5X5rG_6loOOUzP8/s1600-h/FinlandCityGraph-BreathFirstTraversal.jpg"><img style="cursor: pointer; width: 308px; height: 489px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhH_FRCmy_7FpO0z7BfLfBfCi_qkwVbq5mHXtiy_6leBlI0l_Km7FxxTOL-qauya-VMH6mzk53D43xL3ES23ZbVlnfAVrf6pL_toWNo1GnOv7TQv3haxjqfKGxD42O_5X5rG_6loOOUzP8/s320/FinlandCityGraph-BreathFirstTraversal.jpg" alt="" id="BLOGGER_PHOTO_ID_5314864815209825442" border="0" /></a><br /><br /><span style="font-weight: bold;">1</span><br />Visited: <span class="blsp-spelling-error" id="SPELLING_ERROR_9">Pori</span><br />Queue: <span class="blsp-spelling-error" id="SPELLING_ERROR_10">Tampere</span>, <span class="blsp-spelling-error" id="SPELLING_ERROR_11">Turku</span><br /><br /><span style="font-weight: bold;">2</span><br />Visited: <span class="blsp-spelling-error" id="SPELLING_ERROR_12">Pori</span>, <span class="blsp-spelling-error" id="SPELLING_ERROR_13">Tampere</span><br />Queue: <span class="blsp-spelling-error" id="SPELLING_ERROR_14">Turku</span>, Helsinki, <span class="blsp-spelling-error" id="SPELLING_ERROR_15">Kuopio</span><br /><br /><span style="font-weight: bold;">3</span><br />Visited: <span class="blsp-spelling-error" id="SPELLING_ERROR_16">Pori</span>, <span class="blsp-spelling-error" id="SPELLING_ERROR_17">Tampere</span>, <span class="blsp-spelling-error" id="SPELLING_ERROR_18">Turku</span><br />Queue: Helsinki, <span class="blsp-spelling-error" id="SPELLING_ERROR_19">Kuopio</span><br /><br /><span style="font-weight: bold;">4</span><br />Visited: <span class="blsp-spelling-error" id="SPELLING_ERROR_20">Pori</span>, <span class="blsp-spelling-error" id="SPELLING_ERROR_21">Tampere</span>, <span class="blsp-spelling-error" id="SPELLING_ERROR_22">Turku</span>, Helsinki<br />Queue: <span class="blsp-spelling-error" id="SPELLING_ERROR_23">Kuopio</span>, <span class="blsp-spelling-error" id="SPELLING_ERROR_24">Kouvola</span><br /><br /><span style="font-weight: bold;">5</span><br />Visited: <span class="blsp-spelling-error" id="SPELLING_ERROR_25">Pori</span>, <span class="blsp-spelling-error" id="SPELLING_ERROR_26">Tampere</span>, <span class="blsp-spelling-error" id="SPELLING_ERROR_27">Turku</span>, Helsinki, <span class="blsp-spelling-error" id="SPELLING_ERROR_28">Kuopio</span><br />Queue: <span class="blsp-spelling-error" id="SPELLING_ERROR_29">Kouvola</span><br /><br /><span style="font-weight: bold;">6</span><br />Visited: <span class="blsp-spelling-error" id="SPELLING_ERROR_30">Pori</span>, <span class="blsp-spelling-error" id="SPELLING_ERROR_31">Tampere</span>, <span class="blsp-spelling-error" id="SPELLING_ERROR_32">Turku</span>, Helsinki, <span class="blsp-spelling-error" id="SPELLING_ERROR_33">Kuopio</span>, <span class="blsp-spelling-error" id="SPELLING_ERROR_34">Kouvola</span><br />Queue: <span class="blsp-spelling-error" id="SPELLING_ERROR_35">Oulu</span><br /><br /><span style="font-weight: bold;">7</span><br />Visited: <span class="blsp-spelling-error" id="SPELLING_ERROR_36">Pori</span>, <span class="blsp-spelling-error" id="SPELLING_ERROR_37">Tampere</span>, <span class="blsp-spelling-error" id="SPELLING_ERROR_38">Turku</span>, Helsinki, <span class="blsp-spelling-error" id="SPELLING_ERROR_39">Kuopio</span>, <span class="blsp-spelling-error" id="SPELLING_ERROR_40">Kouvola</span>, <span class="blsp-spelling-error" id="SPELLING_ERROR_41">Oulu</span><br />Queue: empty<br /><br />Therefore, the route <span class="blsp-spelling-corrected" id="SPELLING_ERROR_42">yield</span>ed by the Breadth-First traversal:<br /><span class="blsp-spelling-error" id="SPELLING_ERROR_43">Pori</span>, <span class="blsp-spelling-error" id="SPELLING_ERROR_44">Tampere</span>, <span class="blsp-spelling-error" id="SPELLING_ERROR_45">Turku</span>, Helsinki, <span class="blsp-spelling-error" id="SPELLING_ERROR_46">Kuopio</span>, <span class="blsp-spelling-error" id="SPELLING_ERROR_47">Kouvola</span>, <span class="blsp-spelling-error" id="SPELLING_ERROR_48">Oulu<br /><br /><br />ii. <span style="font-weight: bold;">Depth-First Traversal</span>: Traverse all the vertices starting from a given '<span style="font-weight: bold;">start vertex</span>'. </span>Hence, such a traversal follows the '<span class="blsp-spelling-corrected" id="SPELLING_ERROR_6">neighbour</span>-first' principle by considering the following:<br /><span class="blsp-spelling-error" id="SPELLING_ERROR_48">- No vertex is visited more than once<br />- Only those vertices that can be reached are visited<br /><br />Importantly here, we make use of the <span style="font-weight: bold;">Stack data structure</span>. In effect, we stack the vertices so that vertices to be visited soon are in order in which they are popped from the stack i.e. last-in, first-out.<br /><br />Visiting a vertex involves returning the data item in the vertex and adding its neighbour vertices to the stack. However, </span><span class="blsp-spelling-error" id="SPELLING_ERROR_48">we don't carryout any action</span><span class="blsp-spelling-error" id="SPELLING_ERROR_48"> if the following occurs:<br />- neighbour is already present in the stack or if the neighbour has already been visited<br /><br /><br /></span>As an example of the depth-first traversal, we traverse the major cities of Finland with by the <span>start vertex as</span> <span>'<span class="blsp-spelling-error" id="SPELLING_ERROR_7">Pori</span>'</span>. Note! the <span class="blsp-spelling-corrected" id="SPELLING_ERROR_8">neighbour(s)</span> of a given vertex are pushed to the stack in alphabetical order.<br /><br /><span class="blsp-spelling-error" id="SPELLING_ERROR_48"><span style="font-weight: bold;">1</span><br />Visited: Pori<br />Stack:<br />-------<br />Turku<br />-------<br />Tampere<br />-------<br /><br /><span style="font-weight: bold;">2</span><br />Visited: Pori, Turku<br />Stack:<br />-------<br />Helsinki<br />-------<br />Tampere<br />-------<br /><br /><span style="font-weight: bold;">3</span><br />Visited: Pori, Turku, Helsinki<br />Stack:<br />-------<br />Kuopio<br />-------<br />Kouvola<br />-------<br />Tampere<br />-------<br /><br /><span style="font-weight: bold;">4</span><br />Visited: Pori, Turku, Helsinki, Kuopio<br />Stack:<br />-------<br />Kouvola<br />-------<br />Tampere<br />-------<br /><br /><span style="font-weight: bold;">5</span><br />Visited: Pori, Turku, Helsinki, Kuopio, Kouvola<br />Stack:<br />-------<br />Oulu<br />-------<br />Tampere<br />-------<br /><br /><span style="font-weight: bold;">6</span><br />Visited: Pori, Turku, Helsinki, Kuopio, Kouvola, Oulu<br />Stack:<br />-------<br />Tampere<br />-------<br /><br /><span style="font-weight: bold;">7</span><br />Visited: Pori, Turku, Helsinki, Kuopio, Kouvola, Oulu, Tampere<br />Stack:<br />-------<br />Empty<br />-------<br /><br /></span>Therefore, the route <span class="blsp-spelling-corrected" id="SPELLING_ERROR_42">yield</span>ed by the Depth-First traversal:<br /><span class="blsp-spelling-error" id="SPELLING_ERROR_48">Pori, Turku, Helsinki, Kuopio, Kouvola, Oulu, Tampere</span>Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-82360503031540294972009-03-19T03:26:00.000-07:002009-03-19T03:29:36.555-07:00Types of GraphsThere two types of graphs:<br />i. Undirected Graphs<br />ii. Directed Graphs<br /><br /><span style="font-weight: bold;">Undirected Graph</span>: A graph that entail edges with ordered pair of vertices, however it does not have direction define. Example of such a graph is the '<a href="http://en.wikipedia.org/wiki/Family_tree_of_the_Greek_gods">Family tree of the Greek gods</a>'<br /><br /><span style="font-weight: bold;">Directed Graph</span>: A graph that entail edges with ordered pair of vertices and has direction indicated with an arrow. Example of such a graph is the '<a href="http://www.ai-junkie.com/architecture/state_driven/tut_state1_files/image002.jpg">A finite-state machine of a light switch</a>'Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-69368073957847527852009-03-17T09:51:00.000-07:002009-03-19T03:29:20.072-07:00What is a Graph data structure?Graph is an Abstract Data Type (<span class="blsp-spelling-error" id="SPELLING_ERROR_0">ADT</span>) which is of a non-linear structure entailing sets of nodes and connectors. Here, the connectors helps to establish relationship between nodes. However, from the graph <span class="blsp-spelling-error" id="SPELLING_ERROR_1">ADT</span> literature point-of-view the nodes are referred to as <span style="font-style: italic; font-weight: bold;" class="blsp-spelling-error" id="SPELLING_ERROR_3">Vertices</span> and connectors are <span class="blsp-spelling-corrected" id="SPELLING_ERROR_4">referred</span> to as <span style="font-style: italic; font-weight: bold;">Edges</span>.<br /><span class="blsp-spelling-corrected" id="SPELLING_ERROR_5">Mathematically</span>, a graph <span style="font-weight: bold;">G</span> entails <span style="font-style: italic;" class="blsp-spelling-error" id="SPELLING_ERROR_6">vertices</span><span style="font-style: italic;"> </span><span style="font-weight: bold;">V</span>, which are connected by edges <span style="font-weight: bold;">E</span>. Hence, a graph is defined as an ordered pair <span style="font-weight: bold;">G=(V,E)</span>, where <span style="font-weight: bold;">V</span> is a finite set and <span style="font-weight: bold;">E</span> is a set consisting of two element subsets of <span style="font-weight: bold;">V</span>.Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-23967288923977805202009-03-11T10:49:00.000-07:002009-03-11T10:51:34.147-07:00What is Bucket Sort?Bucket Sort (alternatively know as bin sort) is an algorithm that sorts numbers and comes under the category of distribution sort.<br />This sorting algorithm doesn't compare the numbers but distributes them, it works as follows:<br />1. Partition a given array into a number of buckets<br />2. One-by-one the numbers in the array are placed in the designated bucket<br />3. Now, only sort the bucket that bare numbers by recursively applying this Bucket Sorting algorithm<br />4. Now, visiting the buckets in order, the numbers should be sortedNashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-21526763434763990112009-03-11T01:17:00.000-07:002009-03-11T01:23:44.197-07:00What is Radix Sort?Radix Sort is an algorithm that sorts a list of numbers and comes under the category of distribution sort.<br />This sorting algorithm doesn't compare the numbers but distributes them, it works as follows:<br />1. Sorting takes place by distributing the list of number into a bucket by passing through the individual digits of a given number one-by-one beginning with the least significant part. Here, the number of buckets are a total of ten, which bare key values starting from 0 to 9.<br />2. After each pass, the numbers are collected from the buckets, keeping the numbers in order<br />3. Now, recursively redistribute the numbers as in the above step '1' but with a following reconsideration: take into account next most significant part of the number, which is then followed by above step '2'.<br /><br />For an illustration concerning this sorting algorithm check the <a href="http://datastructuresnotes.blogspot.com/2009/02/exercise-radix-sorting.html">Radix Sorting exercise</a>Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-61647111496906605632009-03-10T01:59:00.000-07:002009-03-11T05:49:04.546-07:00What is Heap Sort?Heap Sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of comparison-based sorting and a family member of the selection sort. As the name suggests, this sorting algorithm use the concept of a heap structure that is based on the binary tree, which works as follows:<br />1. Using an array and the given data items, build a heap i.e. either a min heap or max heap as per requested sorting order<br />2. From the heap, remove the root node's data items and insert it to an separate array<br />3. Wait until the heap orders is restored, which will produces a new root node. Now, recursively repeat the above procedure '2' until there is no data items left in the heap.<br /><br />Click the link -> <a href="http://datastructuresnotes.blogspot.com/2009/02/sorting-algorithm-heapsort-heapify.html">Heap Sort</a> for the pseudocodeNashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-55828764431256615732009-03-09T03:39:00.000-07:002012-12-02T07:24:46.782-08:00What is Quick Sort?<div dir="ltr" style="text-align: left;" trbidi="on">
Quick Sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of comparison-based sorting.<br />
This algorithm works as follows:<br />
1. Reorder by spiting the sequence into left and right halves with a <span style="font-style: italic;">pivot </span>data item in between. Here, <span style="font-style: italic;">pivot </span>data item is identified by comparison i.e. a data item must be greater than or equal to every data item in the left half & less than or equal to every data item in the right half.<br />
2. Now, recursively sort the two half's separately.</div>
Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-17805200432068635312009-03-09T03:23:00.000-07:002009-03-09T10:57:01.726-07:00What is Merge Sort?Merge sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of comparison-based sorting.<br />Here we apply the divide-and-conquer strategy to sort a given sequence of data items, which can be described as follows:<br />1. Recursively split the sequence into two <span class="blsp-spelling-corrected" id="SPELLING_ERROR_0">halves</span> (i.e. <span class="blsp-spelling-error" id="SPELLING_ERROR_1">subsequences</span>) until the <span class="blsp-spelling-error" id="SPELLING_ERROR_2">subsequence</span> contains only a single data item (i.e. singleton <span class="blsp-spelling-error" id="SPELLING_ERROR_3">subsequence</span>)<br />2. Now, recursively merge these <span class="blsp-spelling-error" id="SPELLING_ERROR_5">subsequences</span> back together preserving their required order (i.e. ascending or descending order)Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-11666583207125338852009-03-06T23:42:00.000-08:002009-03-09T03:39:02.234-07:00What is Selection Sort?Selection Sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the <span class="blsp-spelling-corrected" id="SPELLING_ERROR_0">category</span> of in-place comparison sort.<br />Sorting takes place by stepping through all the data items one-by-one while looking for either largest or smallest data item and making only one swap after finding either largest or smallest data item. Hence, this sorting algorithm is <span class="blsp-spelling-corrected" id="SPELLING_ERROR_1">referred</span> to as the <span class="blsp-spelling-corrected" id="SPELLING_ERROR_2">selection</span> sort because on each pass this algorithm selects either largest or smallest of the remaining unsorted data items and places them in the right order.<br /><br />click the link -> <a href="http://datastructuresnotes.blogspot.com/2009/02/selection-sorting-array.html">Selection Sort</a> for the pseudocodeNashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-38553320415487721072009-03-06T00:35:00.000-08:002009-03-09T03:39:29.860-07:00What is Bubble Sort?Bubble sort is a sorting algorithm that sorts data items. These data items are presumed to be arranged in a sequential order (i.e. like an array). Sorting takes place by stepping through all the data items one-by-one in pairs and comparing adjacent data items and swapping each pair that is out of order. Idea of swapping operation is to gradually moves either larger or smaller data items to the right or left. This swapping operation is repeated on the data items (i.e. array) until no swaps are required, indicating that the data items is in ascending or <span class="blsp-spelling-corrected" id="SPELLING_ERROR_0">descending</span> order.<br /><br />click the link -> <a href="http://datastructuresnotes.blogspot.com/2009/02/bubble-sorting-array.html">Bubble Sort</a> for the pseudocode.Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-38093156649158269642009-03-05T00:32:00.001-08:002014-01-13T13:13:11.732-08:00What is a non-linear datastructure?<div dir="ltr" style="text-align: left;" trbidi="on">
A non-linear data structure is a data structure in which a data item is connected to several other data items. So that a given data item has the possibility to reach one-or-more data items.<br />
<br />
<span style="font-weight: bold;">Pros</span><br />
<ul>
<li>Uses memory efficiently that the free contiguous memory in not an requirement for allocating data items</li>
<li>The length of the data items is not necessary to be known prior to allocation</li>
</ul>
<span style="font-weight: bold;">Cons</span><br />
<ul>
<li>Overhead of the link to the next data item</li>
</ul>
Examples of non-linear data-structures are <a href="http://datastructuresnotes.blogspot.fi/2009/03/what-is-graph-data-structure.html">Graphs</a> and <a href="http://datastructuresnotes.blogspot.fi/2009/03/what-is-binary-tree.html">Trees</a>. However <a href="http://datastructuresnotes.blogspot.fi/2009/03/what-is-linked-list.html">Linked List</a> and Arrays are linear data structures.</div>
Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-28788407802017523792009-03-05T00:02:00.000-08:002009-03-05T00:15:00.541-08:00What is a linear datastructure?Linear datastructure is one in which the data items are placed in the memory contiguously i.e. one after the other.<br /><span style="font-weight: bold;">Pros</span><br /><ul><li>If we search the first data item, then it is very easy to find the next data items<br /></li></ul><span style="font-weight: bold;">Cons</span><br /><ul><li>Size of the array must be know prior to allocation</li><li>Requires contiguous memory, however if a free memory space is disjoint then this free memory space is not utilized for memory allocation</li></ul>Example of linear datastructure is an array.Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-29937894667108899952009-03-04T22:36:00.000-08:002009-03-04T22:47:09.774-08:00What is a sorting algorithm?A sorting algorithm is an algorithm that sorts the data into ascending or <span class="blsp-spelling-corrected" id="SPELLING_ERROR_0">descending</span> order.<br /><br />Examples of such sorting algorithms are:<br /><ul><li><a href="http://datastructuresnotes.blogspot.com/2009/02/exercise-radix-sorting.html">Radix sorting</a></li><li><a href="http://datastructuresnotes.blogspot.com/2009/02/sorting-algorithm-heapsort-heapify.html">Heap sorting</a></li><li><a href="http://datastructuresnotes.blogspot.com/2009/02/selection-sorting-array.html">Selection sorting</a></li><li><a href="http://datastructuresnotes.blogspot.com/2009/02/bubble-sorting-array.html">Bubble sorting</a></li></ul>Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-61354917390408719932009-03-03T23:23:00.000-08:002009-03-04T01:18:37.220-08:00What is a Search Tree?Search Tree is based on the Binary Search Tree (BST) in which each node has a left and right child. All the childern to the left of the node with key values have smaller than the root node, all the childern to the right of the node have values greater than the root node.<br /><br />For example, a sequence of numbers like 34, 54, 66, 12, 43, 28, 83 in a Search Tree is represented as follows:<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgErWCZoBRHr4XYY-LJCQgAhszxNXRiLuw8S8lapLJ00-3NURDnwhG0dt2SIpzVnse55VVfZKPGcMDKqR6GnaIyvCxvdca8EzyO_05eKNxx7eL7z9EkSX8-Ykx2fuQEfzWC1gze0VWzbEI/s1600-h/SearchTree01.GIF"><img style="margin: 0pt 10px 10px 0pt; float: left; cursor: pointer; width: 186px; height: 157px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgErWCZoBRHr4XYY-LJCQgAhszxNXRiLuw8S8lapLJ00-3NURDnwhG0dt2SIpzVnse55VVfZKPGcMDKqR6GnaIyvCxvdca8EzyO_05eKNxx7eL7z9EkSX8-Ykx2fuQEfzWC1gze0VWzbEI/s320/SearchTree01.GIF" alt="" id="BLOGGER_PHOTO_ID_5309252283422651058" border="0" /></a>Now, in order to search a given value i.e. 43 in this constructed tree. Start at the root node to search 43, this is done by making comparsion with the node value. When the value compared with the search value results to be greater, then move to the right node or vice versa. In this case, we move right because 43 is greater than 34.<br /><br />From, now on just repeat the comparison procedure until you find a matching value or end the comparing procedure at a leaf node.<br /><br />Continuing our search, we now compare 54 with 43, we notice 43 is less than 54, hence we move left and compare the leaf nodes value i.e. 43 with the search value i.e. 43, therefore 43 equals to 43... match found!<br /><br />Advantages of such a search tree: Insertion, Removal, Search are performed efficiently. In <span class="blsp-spelling-corrected" id="SPELLING_ERROR_0">particularly</span>, when considering the searching iteration we reduce the number of elements to search by one-half.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiapY7jyyiC_gFpn6E37DBQbc5Sxwf_XPa3kD6p2IAYl1xkfXyv53purKY1FjDpmIlnNBIQTIGKfxePmQvjgTGtsGFnfpu3dSM0HGjyOymnR7gtfwyBG6n10j-bPmtZly8uDoeUT5myAHI/s1600-h/SearchTree01.GIF"><br /></a>Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0tag:blogger.com,1999:blog-1384839596521188467.post-73866917268988861652009-03-02T01:52:00.000-08:002009-03-23T09:09:29.150-07:00What is Priority Queue?A data structure for maintaining items or elements in a queue of priorities, which is usually implemented using an array. A queue of this nature helps to insert every item with an assigned priority and these inserted items could be deleted if required.Nashhttp://www.blogger.com/profile/14500504650922098360noreply@blogger.com0