Re: [問題] 有關於BFS的結束判定

[bleed1979 (十三)]

判定方式兩者都對，要看怎麼實作。
queue為空也是所有node都走過。
關鍵在是否需要回溯經過的node。


圖
1------2
|
|
|
3------4  假設有10000個點

struct Point
{
  Point(int i1, int i2) : value(i1), parent(i2) {}
  int value;
  int parent;
};

bool visited[10000];  //如您所願10000點，初值要設為false;


方式一：所有node都走過的

vector<Point> queue;  // 儲存所有node資訊。

Point newPoint(1, -1);  // 如果從1開始, 父節點-1
visired[1] = true;      // 已經訪問
queue.push_back(newPoint);

int left = 0, right = 1;  // 左指向目前運作元素，右指向queue的size
int last = 0;             // 印出結果回溯用的

while(left != right)
{
  for(; left != right; ++left)
  {
    Point this_point = queue[left];

    if(this_point == 要找的點)
    {
      last = left;
      goto SEARCH_END;
    }

    for找出和this_point相連的點。
    {
      if(!visited[相連的點])
      {
        visited[相連點] = true;
        Point newPoint(相連點, left);
        queue.push_back(newPoint);
      }
    }

  }
  right = queue.size();
}

SEARCH_END:

  while(last != -1)  // 回溯，輸出順序是反著的。
  {
    輸出queue[last].value;
    last = queue[last].parent;
  }


方式二：queue為空的方式，也走過所有node

deque<Point> queue;

Point newPoint(1, -1);
visited[1] = true;
queue.push_back(newPoint);

int right = 1;

while(queue.size() > 0)
{
  while(right--)
  {
    Point this_point = queue[0];  // 總是抓首元素

    if(this_point == 要找的點)
    {
      goto SEARCH_END;
    }

    for找出和this_point相連的點。
    {
      if(!visited[相連的點])
      {
        visited[相連點] = true;
        Point newPoint(相連點, left);
        queue.push_back(newPoint);
      }
    }
    queue.pop_front();  // 重要，把首元素pop掉
  }
  right = queue.size();
}

SEARCH_END:
  因為queue有做pop，所以無法回溯。


有問題可以一起討論。



Bleed


※ 引述《linkone (小豆豆)》之銘言：
: 請問一下 BFS怎麼判定已結束?
: 在網路看人家是說佇列以空 是這樣嗎?
: 也有人說當所有元素都走過一次就結束了
: 在實做方面如果有一萬個元素 難道每次都要去檢查
: 一萬個裡面還有沒有沒走過的嗎?
: 現在這邊搞不太清楚
: 再請問一下 如果要算路徑數量要用哪種方法呢?

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.43.119.139
→ bleed1979:抱歉，queue為空的方式就不用parent，我用複製貼上的。