اجتياز الرسم البياني البسيط: البحث عن عمق وعمق باستخدام جافا سكريبت كمثال

ما هو اجتياز الرسم البياني؟

بحث العمق

//  ,       
// , : 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
}

تحليل DFS

بحث واسع

//  ,       
// , : 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

قياسات الحياة الحقيقية

الموجودات

• يتم استخدام عمليات البحث عن العمق والعرض لاجتياز الرسم البياني.
• يتحرك DFS على طول الحواف ذهابًا وإيابًا ، وينتشر BFS عبر الجيران بحثًا عن هدف.
• يستخدم DFS المكدس و BFS قائمة الانتظار.
• وقت التشغيل لكليهما هو O (V + E) ، والتعقيد المكاني هو O (V).
• هذه الخوارزميات لها فلسفة مختلفة ، ولكنها مهمة بنفس القدر للعمل مع الرسوم البيانية.