מציאת מעגל בגרף לא מכוון (נפתר [לא בדיוק])

[MasterDK]

שלום יש לי בעיה נוראה מעצבנת! אני לא מבין איך אפשר לזהות אם יש מעגל בגרף לא מכוון אשר מייוצג על ידי מטריצת סימכויות.

אני לא יודע פשוט לא עולה לי ראש האלגוריתם.

תעזרו לי בבקשה

[עריכה]

צודק מי שאמר שמספיק לשאול שאלה והבעיה תפתר

הנא הלגוריתמם שלי, הייתה בעיה שעשיתי z < size במקום z <= k

int checkCircle(Graph *g, unsigned int i, unsigned int j){
    int len;

    if(j > i){
        unsigned int tmp = i;
        i = j;
        j = tmp;
    }

    len = graphAdjacent(g, i, j);

    //We have self cycle, get out
    if((i == j) && (len != 0))
        return 1;

    //We already been there, get out
    if(len < 0)
        return 1;

    //In any other case, mark edges as visited
    {
        Item it = MAKE_NULL_ITEM();
        it.length = -1;
        graphJoinWt(g, i, j, it);
        graphJoinWt(g, j, i, it);
    }

    //Find next edge
    {
        unsigned int k = j;
        unsigned int z;
        for(z = 0; z <= k; ++z){
            int len = graphAdjacent(g, k, z);
            if(len > 0){
                return checkCircle(g, k, z);
            }
        }
    }

    return 0;
}

[עריכה 2]

זה דפוק, פעם זה עובד פעם לא...

בכל מקרה אם מישהוא יכול לעזור לי או להפנות אותי לחומר בנושא אשמח!

תודה רבה מראש

[Zelig]

לינק מצויין עם המון פתרונות לבעיה:

http://tinyurl.com/aokxzc

[MasterDK]

ואתה חושב שלא חיפשתי? מה יעזור לי להתעיק אלגוריתם מוכן?

אני לא מבין את העקרון העבודה של האלגוריתם!

חוץ מזה שרוב המימושים הם על ידי קבוצות או יצוג גרף כגרף ולא כמטריצה של סימוכיות.

[Zelig]

ראשית, רוב האלגוריתמים על גרפים יעבדו ללא קשר לצורת יצוג הגרף.

אלגוריתם אחד לפתור את הבעיה: בצע DFS וסמן את הצמתים שביקרת. אם ביקרת באותה צומת פעמיים סימן שיש מעגל. אם יש צמתים שלא ביקרת, בחר אחת מהן וחזור על האלגוריתם עד שביקרת בכל הצמתים בדיוק פעם אחת (ואז אין מעגל) או שביקרת באותה צומת פעמיים (ואז יש מעגל).

הנה אלגוריתם אחר שהרגע חשבתי עליו שאולי יעבוד (אין לי כוח להוכיח), שאולי יעזור לך להבין:

הבה נניח שניתן להגיע מכל צומת בגרף לכל צומת אחרת (כלומר קיים מסלול מכל צומת לכל צומת - גרף קשיר).

אם אין מעגל בגרף כזה, הרי שהוא עץ.

כמות הקשתות בעץ היא כמות הצמתים פחות אחד (כלומר 1 - |V| = |E|).

כלומר אם מספר הקשתות בגרף קשיר הוא 1 - |V| אז הגרף הוא עץ ואין בו מעגלים. אם מספר הקשתות גדול יותר, אז יש לפחות מעגל אחד. בהתאם לשיטת היצוג - ספור את הקשתות.

http://he.wikipedia.org/wiki/%D7%92%D7%A8%D7%A3_%D7%A7%D7%A9%D7%99%D7%A8

http://he.wikipedia.org/wiki/%D7%A2%D7%A5_(%D7%AA%D7%95%D7%A8%D7%AA_%D7%94%D7%92%D7%A8%D7%A4%D7%99%D7%9D)

[MasterDK]

תודה רבה אני אנסה.