Problem

2/6

BFS: البداية (بايثون)

Theory Click to read/hide

BFS (بحث العرض أولاً) هو طريقة مسح للرسم البياني ، وغالبًا ما تستخدم في كل من الخوارزميات البسيطة والمتقدمة. يعمل بحث Breadth-First عن طريق التنقل خلال المستويات الفردية للرسم البياني ، بدءًا من العقدة المصدر والانتقال تدريجياً بعيدًا عنها. يظهر هذا بوضوح في الرسوم المتحركة.

لكتابة BFS بسيط ، يجب أن تكون قادرًا على العمل مع قائمة انتظار ، وهيكل بيانات يسمح لك بأخذها من البداية & nbsp ؛ ووضعها في النهاية ، وأيضًا أن تكون قادرًا على تخزين رسم بياني في النموذج من قائمة مجاورة.
نبسب ؛
وصف رسمي للخوارزمية
1) ضع رقم الرأس الذي يبدأ منه البحث في قائمة الانتظار الفارغة في البداية.
2) استخرج قمة الرأس U من بداية قائمة الانتظار وقم بتمييزها على أنها مستخدمة في مصفوفة منفصلة.
3) في نهاية قائمة الانتظار ، أضف جميع النقاط التي يمكننا الوصول إليها باستخدام الحافة من الرأس U والتي لم يتم تمييزها بعد.
4) إذا كانت قائمة الانتظار فارغة ، فهذا يعني أنه تم فحص جميع عقد الرسم البياني المتصل ، وإلا فارجع إلى الخطوة 2.
نبسب ؛
صعوبة العمل
نظرًا لأن الخوارزمية ، في أسوأ الحالات ، تزور جميع عقد الرسم البياني ، عند تخزين الرسم البياني في شكل قوائم مجاورة ، يكون التعقيد الزمني للخوارزمية هو O (| V | + | E |) ، حيث V هي المجموعة من رؤوس الرسم البياني ، و E هي مجموعة الحواف. & nbsp ؛ ؛
بمعنى آخر ، تعمل الخوارزمية في أسوأ الحالات بالنسبة لعدد الأضلاع + عدد الرؤوس.
نبسب ؛

Problem

ترتبط بعض القرى ببعضها البعض بواسطة طرق يمكن تمثيلها كرسم بياني & nbsp؛ غير موجه. رؤوس هذا الرسم البياني عبارة عن قرى ، والحواف عبارة عن طرق بين القرى (قد يحتوي الرسم البياني على دورات). & nbsp؛ من المعروف أنه في القرية & nbsp؛ S an artel Pedlars . & nbsp؛ كل صباح ، لبيع الخردوات الصغيرة الخاصة بهم ، يذهب الباعة المتجولون إلى القرى التي & nbsp ؛ لم تزرها بعد ، وهناك طريق من الطريق الحالي. دائمًا ما يتم تقسيم أرتل الباعة المتجولين إلى مجموعات حتى يتمكنوا من التجول في جميع القرى التي توجد بها طرق من القرية الحالية في يوم واحد.
كم يوما سيزور الباعة المتجولون كل القرى؟ اكتب دالة \ (bfs () \) والتي ستعيد الإجابة على المشكلة.


إدخال
يحتوي السطر الأول على 3 أعداد صحيحة n ، m ، s & nbsp؛ ( \ (1 & lt؛ = n & lt؛ = 10 ^ 5 \) ، \ (0 & lt؛ = m & lt؛ = 10 ^ 5 \) ، \ (1 & lt؛ = s & lt؛ = n \) ) - عدد القرى وعدد الطرق بينها وعدد القرية التي تتمركز فيها عصابة الباعة المتجولين. & nbsp ؛ في السطور التالية m تحتوي على رقمين لكل منهما u ، v ( \ (1 & lt؛ = u، v & lt؛ = n \) ) - عدد قريتين يوجد بينهما طريق. تتم فهرسة القرى بـ 1 .

بصمة
اطبع رقمًا واحدًا - كم عدد الأيام التي سيستغرقها الباعة المتجولون لزيارة جميع القرى.
& nbsp؛
نبسب ؛
أمثلة <الجسم>
# إدخال الإخراج
1 6 7 1
1 2
15
23
5 4
34
36
4 6 		4

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
Python
Write the program below 
def bfs():            
n, m, s = map(int, input().split())
s -= 1
used = [False] * n  # True, если были в вершине i
tm = [0] * n    # tm[i] - день, когда в деревню i пришла артель коробейников
g = []     # список смежности
for i in range(n):
    g.append([])


for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

print(bfs())

     

Program check result

To check the solution of the problem, you need to register or log in!