search-algo

گراف کو دو بنیادی طریقوں سے represent کیا جا سکتا ہے- پہلا طریقہ adjacency matrix کہلاتا ہے جس می ایک matrix میں آپ ہر (i,j) کے لیے یہ بتاتے ہیں کہ کیا i اور j ایک دوسرے کے adjacent ہیں- اوپر والے گراف کو ہم یوں لکھ سکتے ہیں:

1 1 1 0

0 1 1 1

0 0 1 0

0 0 1 0

ایک اور طریقہ یہ ہے کو ہم ایک ڈکشنری میں ہر node کے لیے ایک لسٹ رکھیں جس میں اس nodeکے adjacent نوڈز کو اسٹور کریں گے- مثال کے طور پر ہم اوپر والے گراف کو اس طرح لکھ سکتے ہیں:

1: [2, 3]

2: [3, 4]

3: []

4: [3]

اس گراف کو ہم pythonمیں یوں لکھیں گے:

G={}

G[1]=[2,3]

G[2]=[3,4]

G[3]=[]

G[4]=[3]

Depth First Search

اس سرچ میں ہم کسی بھی نوڈ کے children کو پہلے explore کرتے ہیں اور پھر دوسرے siblings کو expand کرتے ہیں- مثال کے طور پر اوپر والے گراف کو ہم اگر 1 سے شروع کریں تو اس طرح سے explore کریں گے: 1، 2، 4 ،3

اگر ہم کمپیوٹر میں اس کو اپملیمینٹ کرنا چاہیں تو ہمیں ایک اسٹیک کی ضرورت پڑے گی- شروع میں ہم اسٹیک میں 1 ڈال دیں گے- ہم ایک ایک کر کے اسٹیک میں سے pop کریں گے اور اس نوڈ کو وزٹڈ مارک کر دیں گے- پھر ہم اس نوڈ کے تمام adjacent nodes کو اسٹیک میں ڈال دیں گے- منررجہ ذیل کوڈ اس لاجک کو امپلیمینٹ کررہا ہے:

stack=[1]

def push(e):

stack.insert(0,e)

def pop():

return stack.pop(0)

visited=[]

while len(stack)!=0:

e=pop()

if e in visited:

pass

else:

visited.append(e)

for k in G[e]:

push(k)

print(visited)

Breadth First Search

اس سرچ میں ہم کسی بھی نوڈ کے siblings کو پہلے وزٹ کرتے ہیں اور پھر children کو- مثال کے طور پر اوپر والے گراف کو ہم اگر 1 سے شروع کریں تو اس طرح سے explore کریں گے: 1، 2، 3 ،4- اس مقصد کے لیؑے ہم ایک Queue لیتے ہیں جس میں شروع میں 1 ڈالتے ہیں- ہم اس Queue سے ویلیو نکالتے ہیں اور اس کو وزٹڈ مارک کر دیتے ہیں- اس کے بعد ہم اس نوڈ کے تمام adjacent nodes کو Queue میں enqueue کر دیتے ہیں- یہ عمل جاری رہتا ہے جبتک queue خالی نہ ہو جاۓ- اس سرچ کو python میں اس طرح implement کریں گے-

queue=[1]

def enqueue(e):

queue.append(e)

def dequeue():

return queue.pop(0)

visited=[]

while len(queue)!=0:

e=dequeue()

if e in visited:

pass

else:

visited.append(e)

for k in G[e]:

enqueue(k)

print(visited)

قاریؑن- آج ہم نے سرچنگ کے دو ایلگارتھم کا مطالعہ کیا- اس کے علاوہ سرچنگ کے مختلف اور بھی ایلگو ہیں جنکو AI میں بہت زیادو استعمال کیا جاتا ہے- ان ایلگو کی تفصیل ہم کسی دوسرے آرٹیکل میں بیان کریں گے-