البحث في Graph

اذا كانت لدينا و graph مصفوفته هي

mat[1.1]=1,mat[1.2]=1,mat[1.3]=1,mat[1.4]=-1,mat[1.5]=-1

mat[2.1]=-1,mat[2.2]=1,mat[2.3]=1,mat[2.4]=-1,mat[2.5]=-1

mat[3.1]=-1,mat[3.2]=-1,mat[3.3]=1,mat[3.4]=1,mat[3.5]=1

mat[4.1]=-1,mat[4.2]=1,mat[4.3]=-1,mat[4.4]=1,mat[4.5]=-1

mat[5.1]=-1,mat[5.2]=1,mat[5.3]=-1,mat[5.4]=-1,mat[5.5]=1

ذا اردنا ان نعرف كل المسارات التي تؤدي من 1 الى الحالة 2 نظريا نرى

المسار1 : 1->2

المسار2 :1->3->4->2

المسار3: 1->3->5->2

هذا من الملاحظة

لكن خوارزميا مشكلة

function recherche_path(first,last,arrivel) begin

if last=arrivel then print (first-path) else

for all neoud E(succ(last) & noeud<> first_path

recherche(first_path+noeud,last,arrivel) end

بحيث

first_path هو مسار

first بداية المسار

arrivel النقطة التي مود الوصول اليها

last اخر noeud موجود في first_path

لقد اعطتني نتيجة لكنني لم افلح في احويلها الى كود بلغة

C

انها معقدة قليلا

مثلا mat[i,j]=1 هذا يعني انه يوجد مسار من i نحو j

mat[i,j]=-1 هذا يعني انه لا يوجد مسار من i نحو j

2- فمثلا في المثال السابق اردت ايجاد جميع المسارات التي بين node 1 و node 2 ( في البرنامج وهذه النقطة كتبتها من قبل يجب ان يدخل المستعمل node البداية و node النهاية اي الذين نريد معرفة المسارات التي بينهم

في المثال السابق وجدنا انه يوجد 3 مسارات بين node 1 و node 2

------------------------------------------

كيفية ايجاد المسارات

نبدا من node 1 في حالتنا هذه

نبحث عن كل node j بحيث mat[1,j]=1 نجد 2 و 3

ناخذ node 2 نجد انه هو النهاية التي نبحث عنها و منه 1->2 اول مسار

ثم ناخذ node 3 نبحث عن كل node j بحيث mat[3,j]=1 نجد 4 و 5

ناخذ node 4 نبحث عن كل node j بحيث mat[4,j]=1 نجد 2

2 هو node الذي نبحث عنه لذا المسار الثاني هو

1->3->4->2

ناخذ node 5 (الذي تحصلنا عليه من قبل ) نبحث عن كل node j بحيث mat[5,j]=1 نجد 2

2 هو node الذي نبحث عنه لذا المسار الثالث هو

1->3->5->2

هذا هو اساس الخوارزمية