blog/assets/js/ddc7679f.4b5bdacd.js

"use strict";(self.webpackChunkfi=self.webpackChunkfi||[]).push([[569],{64322:(e,t,n)=>{n.r(t),n.d(t,{assets:()=>c,contentTitle:()=>r,default:()=>m,frontMatter:()=>a,metadata:()=>o,toc:()=>h});var s=n(85893),i=n(11151);const a={id:"iterative-and-iterators",title:"Iterative algorithms via iterators",description:"Iterative DFS using iterators.\n",tags:["csharp","graphs","iterators","iterative"],last_update:{date:new Date("2021-05-18T00:00:00.000Z")}},r=void 0,o={id:"graphs/iterative-and-iterators",title:"Iterative algorithms via iterators",description:"Iterative DFS using iterators.\n",source:"@site/algorithms/10-graphs/2021-05-18-iterative-and-iterators.md",sourceDirName:"10-graphs",slug:"/graphs/iterative-and-iterators",permalink:"/algorithms/graphs/iterative-and-iterators",draft:!1,unlisted:!1,editUrl:"https://github.com/mfocko/blog/tree/main/algorithms/10-graphs/2021-05-18-iterative-and-iterators.md",tags:[{label:"csharp",permalink:"/algorithms/tags/csharp"},{label:"graphs",permalink:"/algorithms/tags/graphs"},{label:"iterators",permalink:"/algorithms/tags/iterators"},{label:"iterative",permalink:"/algorithms/tags/iterative"}],version:"current",lastUpdatedAt:1621296e3,formattedLastUpdatedAt:"May 18, 2021",frontMatter:{id:"iterative-and-iterators",title:"Iterative algorithms via iterators",description:"Iterative DFS using iterators.\n",tags:["csharp","graphs","iterators","iterative"],last_update:{date:"2021-05-18T00:00:00.000Z"}},sidebar:"autogeneratedBar",previous:{title:"Graphs",permalink:"/algorithms/category/graphs"},next:{title:"Distance boundaries from BFS tree on undirected graphs",permalink:"/algorithms/graphs/bfs-tree"}},c={},h=[{value:"Introduction",id:"introduction",level:2},{value:"Different implementations",id:"different-implementations",level:2},{value:"Recursive DFS implementation from exercises without colors",id:"recursive-dfs-implementation-from-exercises-without-colors",level:3},{value:"Iterative DFS from the exercises",id:"iterative-dfs-from-the-exercises",level:3},{value:"My iterative with path in stack",id:"my-iterative-with-path-in-stack",level:3},{value:"My iterative solution with iterators",id:"my-iterative-solution-with-iterators",level:3},{value:"Implementation",id:"implementation",level:2}];function l(e){const t={a:"a",annotation:"annotation",code:"code",em:"em",h2:"h2",h3:"h3",li:"li",math:"math",mi:"mi",mo:"mo",mrow:"mrow",p:"p",pre:"pre",semantics:"semantics",span:"span",ul:"ul",...(0,i.a)(),...e.components};return(0,s.jsxs)(s.Fragment,{children:[(0,s.jsx)(t.h2,{id:"introduction",children:"Introduction"}),"\n",(0,s.jsxs)(t.ul,{children:["\n",(0,s.jsx)(t.li,{children:(0,s.jsx)(t.a,{href:"pathname:///files/algorithms/graphs/iterative-and-iterators.tar.gz",children:"Source code used later on."})}),"\n"]}),"\n",(0,s.jsx)(t.p,{children:"As we have talked on the seminar, iterative approach to implementing DFS is not very intuitive and is a very easy way how to create an incorrect implementation."}),"\n",(0,s.jsx)(t.p,{children:"On the other hand, we have seen iterative implementation in the exercises and I have also prepared two from which one was similar to recursive implementation without colors from exercises and the other one used features of high-level languages."}),"\n",(0,s.jsx)(t.h2,{id:"different-implementations",children:"Different implementations"}),"\n",(0,s.jsx)(t.h3,{id:"recursive-dfs-implementation-from-exercises-without-colors",children:"Recursive DFS implementation from exercises without colors"}),"\n",(0,s.jsx)(t.pre,{children:(0,s.jsx)(t.code,{className:"language-ada",metastring:"showLineNumbers",children:"function VisitedDFS(u: Vertex, visited: VertexSet) return VertexSet is\n    v: Vertex;\nbegin\n    visited.Union(To_Set(u));\n\n    for v in u.successors loop\n        if not Contains(visited, v) then\n            visited := visitedDFS(v, Visited);\n        end if;\n    end loop;\n\n    return visited;\nend VisitedDFS;\n"})}),"\n",(0,s.jsxs)(t.p,{children:["This implementation is correct, does the DFS traversal as it should, however it has one \u201csmallish\u201d downside