सरल ग्राफ़ ट्रैवर्सल: गहराई और चौड़ाई-पहली खोज उदाहरण के रूप में जावास्क्रिप्ट का उपयोग करते हुए

ग्राफ़ ट्रैवर्सल क्या है?

गहराई खोज

//  ,       
// , : adj = {A: [B,C], B:[D,F], ... }
function dfs(adj, v, t) {
	// adj -  
	// v -   ()
	// t -  

	//   
	//    ,    
	if(v === t) return true
	if(v.visited) return false

	//    
	v.visited = true
	//    (  ) v
	for(let neighbor of adj[v]) {
		//    
		if(!neighbor.visited) {
			//     ,      
			let reached = dfs(adj, neighbor, t)
			//  true,  
			if(reached) return true
		}
	}
	//   v  t  
	return false
}

डीएफएस विश्लेषण

व्यापक खोज

//  ,       
// , : adj = {A:[B,C,D], B:[E,F], ... }
function bfs(adj, s, t) {
	// adj -  
	// s -  
	// t -  

	//  
	let queue = []
	//  s  
	queue.push(s)
	//  s         
	s.visited = true
	while(queue.length > 0) {
		//   ()   
		let v = queue.shift()
		// abj[v] -  v
		for(let neighbor of adj[v]) {
			//    
			if(!neighbor.visited) {
				//    
				queue.push(neighbor)
				//    
				neighbor.visited = true
				//     ,  
				if(neighbor === t) return true
			}
		} 
	}
	//  t  ,     
	return false
}

BFS विश्लेषण

वास्तविक जीवन सादृश्य

जाँच - परिणाम

• गहराई और चौड़ाई खोजों का उपयोग ग्राफ को पार करने के लिए किया जाता है।
• डीएफएस किनारों के साथ आगे-पीछे होता है, और बीएफएस एक लक्ष्य की तलाश में पड़ोसियों में फैलता है।
• डीएफएस स्टैक का उपयोग करता है, और बीएफएस कतार।
• दोनों का क्रम O (V + E) है, और स्थानिक जटिलता O (V) है।
• इन एल्गोरिदम का एक अलग दर्शन है, लेकिन ग्राफ़ के साथ काम करने के लिए समान रूप से महत्वपूर्ण हैं।