var Component=(()=>{var g=Object.create;var r=Object.defineProperty;var f=Object.getOwnPropertyDescriptor;var y=Object.getOwnPropertyNames;var v=Object.getPrototypeOf,b=Object.prototype.hasOwnProperty;var q=(n,e)=>()=>(e||n((e={exports:{}}).exports,e),e.exports),w=(n,e)=>{for(var o in e)r(n,o,{get:e[o],enumerable:!0})},a=(n,e,o,h)=>{if(e&&typeof e=="object"||typeof e=="function")for(let i of y(e))!b.call(n,i)&&i!==o&&r(n,i,{get:()=>e[i],enumerable:!(h=f(e,i))||h.enumerable});return n};var T=(n,e,o)=>(o=n!=null?g(v(n)):{},a(e||!n||!n.__esModule?r(o,"default",{value:n,enumerable:!0}):o,n)),_=n=>a(r({},"__esModule",{value:!0}),n);var s=q((H,u)=>{u.exports=_jsx_runtime});var j={};w(j,{default:()=>p,frontmatter:()=>E});var t=T(s());var d=MDXCodeBlock;var l=`/** * @param {Object} graph Node to array of neighboring nodes. * @return {Array} A topological traversal of nodes. */ export default function topologicalSort(graph) { // Initialize a Map object to store each node's incoming and outgoing edges, // an array to store the output topological sort order, // and a Queue object to store nodes to be processed const nodes = new Map(); const queue = new Queue(); const order = []; // Iterating over all the keys in the input graph object // add each key to the "nodes" Map object // with properties "in" with value 0 // and "out" with the value of set of neighboring nodes. Object.keys(graph).forEach((node) => { nodes.set(node, { in: 0, out: new Set(graph[node]) }); }); // Set the Map with the correct \`in\` values. // Iterating over all the keys in the input graph object, // for each node increase the \`in\` property of its neighbor node by 1. Object.keys(graph).forEach((node) => { graph[node].forEach((neighbor) => { nodes.get(neighbor).in += 1; }); }); // Iterate over the nodes and add all the nodes with \`in: 0\` to the queue. nodes.forEach((value, node) => { if (value.in === 0) { queue.enqueue(node); } }); // While queue is not empty. while (queue.length()) { // Dequeue a node from the front of the queue. const node = queue.dequeue(); // For each neighbor of this dequeued node decrease its \`in\` property by 1, // if the \`in\` becomes 0, enqueue the neighbor node. nodes.get(node).out.forEach((neighbor) => { nodes.get(neighbor).in -= 1; if (nodes.get(neighbor).in === 0) { queue.enqueue(neighbor); } }); // Add the dequeued node to the output array. order.push(node); } // Return topological-ordered array if it has the same length as // the number of keys in the graph, otherwise there is a cycle // and we return an empty array. return order.length === Object.keys(graph).length ? order : []; } class Node { constructor(value) { this.value = value; this.next = null; this.prev = null; } } class Queue { constructor() { this._dummyHead = new Node(); this._dummyTail = new Node(); this._dummyHead.prev = this._dummyTail; this._dummyTail.next = this._dummyHead; this._length = 0; } /** * Adds an item to the back of the queue. * @param {*} item The item to be pushed onto the queue. * @return {number} The new length of the queue. */ enqueue(item) { const node = new Node(item); const prevLast = this._dummyTail.next; prevLast.prev = node; node.next = prevLast; node.prev = this._dummyTail; this._dummyTail.next = node; this._length++; return this._length; } /** * Remove an item from the front of the queue. * @return {*} The item at the front of the queue if it is not empty, \`undefined\` otherwise. */ dequeue() { if (this.isEmpty()) { return undefined; } const node = this._dummyHead.prev; const newFirst = node.prev; this._dummyHead.prev = newFirst; newFirst.next = this._dummyHead; // Unlink the node to be dequeued. node.prev = null; node.next = null; this._length--; return node.value; } /** * Determines if the queue is empty. * @return {boolean} \`true\` if the queue has no items, \`false\` otherwise. */ isEmpty() { return this._length === 0; } /** * Returns the item at the front of the queue without removing it from the queue. * @return {*} The item at the front of the queue if it is not empty, \`undefined\` otherwise. */ front() { if (this.isEmpty()) { return undefined; } return this._dummyHead.prev.value; } /** * Returns the item at the back of the queue without removing it from the queue it. * @return {*} The item at the back of the queue if it is not empty, \`undefined\` otherwise. */ back() { if (this.isEmpty()) { return undefined; } return this._dummyTail.next.value; } /** * Returns the number of items in the queue. * @return {number} The number of items in the queue. */ length() { return this._length; } } `;var c=`export default function topologicalSort( graph: Record>, ): Array { // Initialize a Map object to store each node's incoming and outgoing edges, // an array to store the output topological sort order, // and a Queue object to store nodes to be processed const nodes = new Map }>(); const queue = new Queue(); const order = []; // Iterating over all the keys in the input graph object // add each key to the "nodes" Map object // with properties "in" with value 0 // and "out" with the value of set of neighboring nodes. Object.keys(graph).forEach((node) => { nodes.set(node, { in: 0, out: new Set(graph[node]) }); }); // Set the Map with the correct \`in\` values. // Iterating over all the keys in the input graph object, // for each node increase the \`in\` property of its neighbor node by 1. Object.keys(graph).forEach((node) => { graph[node].forEach((neighbor) => { nodes.get(neighbor)!.in += 1; }); }); // Iterate over the nodes and add all the nodes with \`in: 0\` to the queue. nodes.forEach((value, node) => { if (value.in === 0) { queue.enqueue(node); } }); // While queue is not empty. while (queue.length()) { // Dequeue a node from the front of the queue. const node = queue.dequeue()!; // For each neighbor of this dequeued node decrease its \`in\` property by 1, // if the \`in\` becomes 0, enqueue the neighbor node. nodes.get(node)?.out.forEach((neighbor) => { nodes.get(neighbor)!.in -= 1; if (nodes.get(neighbor)!.in === 0) { queue.enqueue(neighbor); } }); // Add the dequeued node to the output array. order.push(node); } // Return topological-ordered array if it has the same length as // the number of keys in the graph, otherwise there is a cycle // and we return an empty array. return order.length === Object.keys(graph).length ? order : []; } class Node { value: T | undefined; next: Node | null; prev: Node | null; constructor(value?: T) { this.value = value; this.next = null; this.prev = null; } } class Queue { _dummyHead: Node; _dummyTail: Node; _length: number; constructor() { this._dummyHead = new Node(); this._dummyTail = new Node(); this._dummyHead.prev = this._dummyTail; this._dummyTail.next = this._dummyHead; this._length = 0; } /** * Adds an item to the back of the queue. */ enqueue(item: T) { const node = new Node(item); const prevLast = this._dummyTail.next; prevLast!.prev = node; node.next = prevLast; node.prev = this._dummyTail; this._dummyTail.next = node; this._length++; return this._length; } /** * Remove an item from the front of the queue. */ dequeue(): T | undefined { if (this.isEmpty()) { return undefined; } const node = this._dummyHead.prev; const newFirst = node!.prev; this._dummyHead.prev = newFirst; newFirst!.next = this._dummyHead; // Unlink the node to be dequeued. node!.prev = null; node!.next = null; this._length--; return node!.value; } /** * Determines if the queue is empty. */ isEmpty(): boolean { return this._length === 0; } /** * Returns the item at the front of the queue without removing it from the queue. */ front(): T | undefined { if (this.isEmpty()) { return undefined; } return this._dummyHead.prev!.value; } /** * Returns the item at the back of the queue without removing it from the queue it. */ back(): T | undefined { if (this.isEmpty()) { return undefined; } return this._dummyTail.next!.value; } /** * Returns the number of items in the queue. * @return {number} The number of items in the queue. */ length(): number { return this._length; } } `;var E=void 0;function m(n){let e={code:"code",h2:"h2",h3:"h3",li:"li",p:"p",ul:"ul",...n.components};return(0,t.jsxs)(t.Fragment,{children:[(0,t.jsx)(e.p,{children:"Topological sort is an algorithm that produces a linear ordering of the vertices of a Directed Acyclic Graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v in the ordering. Topological sort implemented with Kahn's algorithm has linear time complexity, which makes it relatively efficient for large graphs."}),` `,(0,t.jsx)(e.h2,{children:"Clarification questions"}),` `,(0,t.jsx)(e.p,{children:"If unspecified:"}),` `,(0,t.jsxs)(e.ul,{children:[` `,(0,t.jsxs)(e.li,{children:["Input and output format:",` `,(0,t.jsxs)(e.ul,{children:[` `,(0,t.jsx)(e.li,{children:"Should the input graph be represented as an adjacency matrix, adjacency list, or some other data structure?"}),` `,(0,t.jsx)(e.li,{children:"Should the output be a list of nodes in topological order or an array of integers representing the topological order of the nodes?"}),` `]}),` `]}),` `]}),` `,(0,t.jsx)(e.h2,{children:"Solution"}),` `,(0,t.jsx)(d,{languages:{jsx:l,tsx:c}}),` `,(0,t.jsx)(e.h2,{children:"Edge cases"}),` `,(0,t.jsxs)(e.ul,{children:[` `,(0,t.jsx)(e.li,{children:"Empty graph: Return an empty array. If the graph has vertices but no edges, return every vertex in the prompt's discovery order because all of them have zero incoming edges."}),` `,(0,t.jsx)(e.li,{children:"Graph with cycles: Return an empty array rather than a partial ordering."}),` `]}),` `,(0,t.jsx)(e.h2,{children:"Big-O analysis"}),` `,(0,t.jsx)(e.p,{children:"Let's analyze the algorithm's time and space complexity."}),` `,(0,t.jsx)(e.h3,{children:"Time complexity"}),` `,(0,t.jsx)(e.p,{children:"Topological sort implemented with Kahn's algorithm always runs with O(V + E) time complexity, where V is the number of vertices (or nodes) in the graph, and E is the number of edges in the graph."}),` `,(0,t.jsxs)(e.ul,{children:[` `,(0,t.jsxs)(e.li,{children:["The loop that initializes the ",(0,t.jsx)(e.code,{children:"Map"})," visits every vertex and copies every outgoing edge into a ",(0,t.jsx)(e.code,{children:"Set"}),", so it takes O(V + E) time."]}),` `,(0,t.jsxs)(e.li,{children:["The loop that iterates over all the keys in the input graph and for each node increases the ",(0,t.jsx)(e.code,{children:"in"})," property of its neighbor node by 1, has a time complexity of O(E), since it's visiting all the edges of the graph once."]}),` `,(0,t.jsxs)(e.li,{children:["The loop that iterates over the nodes, adding all the nodes with ",(0,t.jsx)(e.code,{children:"in: 0"})," to the queue, has a time complexity of O(V) as well, since it's visiting all the vertices of the graph once."]}),` `,(0,t.jsx)(e.li,{children:"The while loop that iterates until the queue is not empty, has a maximum time complexity of O(V + E) as it is processing all the vertices and edges of the graph."}),` `]}),` `,(0,t.jsx)(e.p,{children:"Overall, the time complexity of the implementation of Kahn's algorithm is O(V + E)."}),` `,(0,t.jsx)(e.h3,{children:"Space complexity"}),` `,(0,t.jsxs)(e.p,{children:["This implementation uses O(V + E) auxiliary space because it copies the graph's outgoing edges into the ",(0,t.jsx)(e.code,{children:"nodes"})," map."]}),` `,(0,t.jsxs)(e.ul,{children:[` `,(0,t.jsxs)(e.li,{children:["The ",(0,t.jsx)(e.code,{children:"nodes"})," map stores O(V) incoming counts and O(E) copied outgoing-edge entries."]}),` `,(0,t.jsx)(e.li,{children:'The output array "order" takes O(V) space as it stores the topological order of all the nodes.'}),` `,(0,t.jsx)(e.li,{children:'The Queue data structure "queue" stores nodes with in-degree equals 0 which requires space linear to the input data and hence takes O(V) space.'}),` `]}),` `,(0,t.jsx)(e.p,{children:"The space complexity of the shown implementation is therefore O(V + E)."})]})}function p(n={}){let{wrapper:e}=n.components||{};return e?(0,t.jsx)(e,{...n,children:(0,t.jsx)(m,{...n})}):m(n)}return _(j);})(); ;return Component;