חיפוש

עזרה

הרשמה

התחברות

עדכונים

מדעי המחשב
UnderWarrior Forums : מדעי המחשב

נושא: BFS

כותב

הודעה

<< נושא קודם | נושא הבא >>

קאפונג
משתמש מתחיל

הצטרף / הצטרפה: 20 April 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 3

נשלח בתאריך: 20 April 2007 בשעה 10:51

| IP רשוּם

שאלה בנוגע לאלגוריתם BFS :

עליי לממש את האלגוריתם ,הבנתי שעליי "לסמן" את הקודקודים שכבר הגעתי אליהם.

אך בצורה כזאת ,לאחר שמצאתי את המסלול המתאים עליי לעבור על כל הצמתים מחדש ולאפס את הסימון.

האם זאת צורת המימוש ?

חזרה לתחילת העמוד

shoshan
מנהל האתר

הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637

נשלח בתאריך: 20 April 2007 בשעה 11:56

| IP רשוּם

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

__________________
עד מתי רשעים יעלוזו?

עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.

חזרה לתחילת העמוד

קאפונג
משתמש מתחיל

הצטרף / הצטרפה: 20 April 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 3

נשלח בתאריך: 20 April 2007 בשעה 14:11

| IP רשוּם

אבל אם הוצאתי קודקודים מהתור (והכנסתי את הבנים שלהם וכו') איך אני יודעת מה ה"דרך" אל הקודקוד הרצוי?ברגע שאני מוציאה קודקודים מהתור,"איבדתי" את המידע על הדרך אל הקודקוד הרצוי.

חזרה לתחילת העמוד

shoshan
מנהל האתר

הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637

נשלח בתאריך: 20 April 2007 בשעה 14:55

| IP רשוּם

קוד:

    Suppose we have a struct:

struct Vertex {
        ...
        std::vector<int> out;
        ...
};

    and an array of vertices: (the algorithm will use the indexes of this array, to handle the vertices)

std::vector<Vertex> graph(vertices);

    the algorithm starts from start and returns true if there is a directed path from start to end:

bool BFS(const std::vector<Vertex>& graph, int start, int end) {
  std::queue<int> next;
  std::vector<int> parent(graph.size(), 0); // 0 means filled with zeros.
  parent[start] = -1;
  next.push(start);
  while (!next.empty()) {
    int u = next.front();
    next.pop();
    // Here is the point where you can examine the u th vertex of graph
    // For example:
    if (u == end) return true;
    for (std::vector<int>::const_iterator j = graph[u].out.begin(); j != graph[u].out.end(); ++j) {
      // Look through neighbors.
      int v = *j;
      if (parent[v] == 0) {
        // If v is unvisited.
        parent[v] = u;
        next.push(v);
      }
    }
  }
  return false;
}

    it also stores the parents of each node, from which you can get the path.

__________________
עד מתי רשעים יעלוזו?

עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.

חזרה לתחילת העמוד

Philonoist
משתמש מתחיל

הצטרף / הצטרפה: 22 April 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4

נשלח בתאריך: 22 April 2007 בשעה 21:38

| IP רשוּם

הקוד מפחיד... אני מניח שכתבת ברור, אבל פשוט אין לי כח לקרוא.
בכל מקרה, לשאלה של הבחור, אתה לא מאבד את המידע הזה, אם אתה שומר אותו. אה? רעיון מגניב, אה? כשאתה מכניב צומת לתור, תשמור את צומת האב של אותה צומת(במערך, או במבנה של הצומת).

__________________
Mess with the best
Die like the rest

חזרה לתחילת העמוד

אם ברצונך להגיב לנושא זה עליך קודם להתחבר
אם אינך רשום/ה כבר עליך להרשם

גרסת הדפסה

אינך יכול/ה לשלוח נושאים חדשים בפורום זה
אינך יכול/ה להגיב לנושאים בפורום זה
אינך יכול/ה למחוק את הודעותיך ותגוביך בפורום זה
אינך יכול/ה לערוך את הודעותיך ותגובותיך בפורום זה
אינך יכול/ה לצור סקרים בפורום זה
אינך יכול/ה להצביע בסקרים בפורום זה