كيفية البحث عن عقدة معينة في بنية الرسم البياني في لغة C؟

Question

لا يعني ذلك أن لدي الوقت لمناقشة هذا الأمر بشكل صحيح للوصول إلى نتيجة وتعديل الكود الخاص بي لأن المرحلة الأولى (من الثلاثة) من مشروع المدرسة تستغرق 24 ساعة، ولكن على الأقل أحتاج إلى معرفة ما إذا كنت قد اتخذت القرار الصحيح.

أنا أستخدم القوائم المرتبطة وإليك بنياتي:

typedef struct sCity {
    int cityID;
    char *cityName;

    struct sCityLink *links;
    struct sCity *next;
} nCity, *City;

typedef struct sCityLink {
    City cityLinkParent;
    City cityLinkTo;

    struct sCityLink *next;

} nCityLink, *CityLink;

في الأساس، لدي الكثير من المدن وهذه المدن مرتبطة ببعضها البعض، مثل الرسم البياني.على سبيل المثال، A وB وC وD وE يتم إدراجها بهذا الترتيب في الهيكل مدينة.بعد ذلك، أقوم بتوصيل A إلى B وC وD وB إلى C وD وE وC إلى D وE وD إلى E.

الآن، لنفترض أنني بحاجة للذهاب إلى المدينة E.هذا هو الأخير في القائمة المرتبطة ويستغرق وقتًا لاجتياز القائمة المرتبطة بالكامل.ربما ليس في هذا المثال مع 5 مدن ولكن في التطبيق الحقيقي من المفترض أن أدعم ما يقرب من 10000 مدينة على الأقل.لكن أقصر طريق هو من A (وهي نقطة البداية) من C إلى E (أو يمكن أن يكون A-D-E أو A-B-E، لا يهم).

هل تسمح لي بنياتي بالعثور على أقصر طريق من A إلى E دون اجتياز القائمة المرتبطة بأكملها واحدًا تلو الآخر؟إذا لم يكن الأمر كذلك، ما الذي أفعله الخطأ؟

إذا كانت الإجابة بنعم، كيف يمكنني أن أفعل ذلك؟لا أعلم كيف أجد مثل هذا الطريق..

Answer 1

هناك مشكلتان منفصلتان - الأولى، ربما تريد العثور على مؤشر مدينة لمعرف المدينة (على سبيل المثال."ه").لا يمكنك القيام بذلك في أقل من الوقت الخطي مع الهياكل الخاصة بك؛إذا كنت في حاجة إليها بشكل أسرع، فاستخدم شجرة بحث ثنائية أو قابلة للتجزئة.

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

Answer 2

يمكنك استخدام خوارزمية تسمى اتساع البحث الأول (بفس).تحتاج إلى تطبيق علامة "لون" على كل عقدة لاستخدامها.لاحظ أن هذه الخوارزمية تعمل فقط إذا كانت حوافك كذلك غير مرجح - إذا كانت هناك مدينتان متصلتان فإنهما متساويتان في المسافة.إذا كان للحواف وزن (وهذا لا يبدو كذلك)، فأنت بحاجة إلى شيء من هذا القبيل خوارزمية ديكسترا أو أ*.