環境為一個Sensor Network，共有4000個nodes。
struct Node_Attribute //node information
{
int Node_ID; // Node id
int coordinate_x; // Node x 座標
int coordinate_y; // Node y 座標
int root_ID; // Network 的 root
bool isRoot; // 目前的Node是否為root
int min_hop_count_to_root; // 最後到達root最小的hop count
int local_min_hop_count_to_root; // 目前所記錄到達root最小的hop count
struct Node_Attribute *Neighbor; // Node i 的 neighbor
int Neighbor_Number; // Node i 的 neighbor 數目
};
所有的node都是random產生。假設我取最左上角的node為root，即 x、y 座標最小者。
現在我想從root開始傳送訊息(Flooding)，直到所有的node都收到自root傳來的訊息，藉此計算每個node到達root所需的距離(hop count)。
原理是，root傳送訊息給他的neighbor，再由neighbor傳送給他的neighbor如此傳送下去。
但是我不知道怎麼寫比較好，一開始的想法是用for loop，但是這樣只能考慮root往下傳的那一層。再繼續下去還要再寫一個for loop。
主要是因為我傳送下去並不是按照node產生的順序，而是他的neighbor，因此從for loop還要額外定義一個
類似
int *root_neighbor_id;
root_neighbor_id=new int[Node[Root_ID].Neighbor_Number];

然後
for(int i=0;i {
Node[Root_ID].Neighbor[i].min_hop_count_to_root=1;
root_neighbor_id[i]=Node[Root_ID].Neighbor[i].Node_ID;
Image1->Canvas->Font->Color=clRed;
Image1->Canvas->TextOutA(Node[Root_ID].Neighbor[i].coordinate_x,Node[Root_ID].Neighbor[i].coordinate_y,".");
}
for(int i=0;i {
for(int j=0;j {
Node[root_neighbor_id[i]].Neighbor[j].local_min_hop_count_to_root=Node[root_neighbor_id[i]].min_hop_count_to_root 1; //距離root的距離=前一個距離 1
Image1->Canvas->TextOutA(Node[Root_ID].Neighbor[i].coordinate_x,Node[Root_ID].Neighbor[i].coordinate_y,".");
}
}
接下來我就不知道該怎麼做才好了。
請問有什麼比較好的方法嗎？謝謝

Recursive Forest Travel?
單考慮一個Node，先Travel同一個方向，比如向左，利用Recursive function fTravel
先看最左邊，若最左的chile node不是leaf，那麼就把這個Node當成你的RootNode繼續看
//此時這個函式沒有結束，只是再一次呼叫自己
這個函式fTravel已經被呼叫到第n層時，發現最左邊為一個leaf//也就是它沒有child node
就處理這個leaf，然後這個函式會結束，也就是結束第n階的fTravel，
這時會回到n-1 fTravel，這個fTravel已經處理完child node，繼續看第二個node是否是leaf，
是就處理，不是就往下一層，直到有leaf出現並處理，直到n-1階的fTravel結束，會回到n-2階
不過recursive的問題是最大一千個階層，因為你有4000個node，處理這個要小心
改成迴圈不是很好寫

------
不論是否我發的文，在能力範圍皆很樂意為大家回答問題。
為了補我的能力不足之處，以及讓答案可以被重複的使用，希望大家能儘量以公開的方式問問題。
在引述到我的文時自然會儘量替各位想辦法，謝謝大家！

氣死人，打了老半天，結果不知道為什麼重整網頁，一切要重來
謝謝你的提醒，我之後有想到是否可以用遞迴的方式。
關於你的演算法我不是很清楚。我猜測是否要將node與neighbor的關係轉換成tree，但是照你的方法我想會有個問題，就是當p1是p2的neighbor，同時間p2也是p1的neighbor，這樣的tree好像會導致cycle，還有就是，因為事先不知道每個node的neighbor數，因此每個node的child數目也要動態產生，這樣的tree structure好像有點複雜，直觀來看，我不知道怎麼表示某一個node的所有child，本來像是binary可以用left & right，但是在這裡我就不知道要怎麼表示才好了。
我又想了一個偷懶的方法，我想了想應該可行：
例如，有10個node的network。如下圖，其中n8為root。(ps.相對的距離先不管，因為是用小畫家畫的，有點難畫)

接著根據neighbor建立成以下的tree structure：

然後從最上層開始往下trace。越上層表示hop count越小，因此只要把尚未加入到hop count table的node逐一加入，如紅色圈出來的部分。
若root n8的hop count=0
則
n7、n0、n6的hop count=1
n1、n2、n4、n9的hop count=2
n3、n5的hop count=3
如此就可以找出所有node的min hop count。


===================引 用 文 章===================
Recursive Forest Travel?
單考慮一個Node，先Travel同一個方向，比如向左，利用Recursive function fTravel
先看最左邊，若最左的chile node不是leaf，那麼就把這個Node當成你的RootNode繼續看
//此時這個函式沒有結束，只是再一次呼叫自己
這個函式fTravel已經被呼叫到第n層時，發現最左邊為一個leaf//也就是它沒有child node
就處理這個leaf，然後這個函式會結束，也就是結束第n階的fTravel，
這時會回到n-1 fTravel，這個fTravel已經處理完child node，繼續看第二個node是否是leaf，
是就處理，不是就往下一層，直到有leaf出現並處理，直到n-1階的fTravel結束，會回到n-2階
不過recursive的問題是最大一千個階層，因為你有4000個node，處理這個要小心
改成迴圈不是很好寫

跟你的很像，只不過你應該還記得Data Structure裡面對Tree的Travel吧？
所以Travel的順序會變成
8->7->0->4，這時候函式來到第四層，發現4為leaf，所以往上一層到0，因為左子樹已經結束，所以換右子樹，Travel 2 -> 5，5為leaf，處理完換2，又回到0，
這時候0的L, R都結束，回到0的上一層7，這時候7的L也結束了，換R -> 1以此類推
這樣函式就只要知道root跟它所有的child node就可以，不用立刻考慮child node是否是leaf
當然，狀況就跟你說的一樣，Path是不能有交錯的，否則會造成cycle，//不過也是有更偷懶的方法可以避免這個問題..:P
但如果會有這樣的問題，你可能就要考慮是否答案非唯一(會不會影響到你的目的)，如果要最短路徑，可能就要想一下尤拉，畢竟現在畫出來的只有10個node..:P

------
不論是否我發的文，在能力範圍皆很樂意為大家回答問題。
為了補我的能力不足之處，以及讓答案可以被重複的使用，希望大家能儘量以公開的方式問問題。
在引述到我的文時自然會儘量替各位想辦法，謝謝大家！

剛剛要開始寫成程式的時候，才發現....我上面提到的想法沒這麼簡單。
因為光要把node建立成tree就不知道該怎麼建立了。
原本是透過neighbor去建立child，但是這有個問題，就是當傳送到最後一個node之後他不知道他是最後一個，仍然繼續往他的neighbor傳，即往一開始的方向傳。
最後變成無限迴圈。

看你用什麼當key，在建Tree的時候加入table，並對將要拜訪的node查詢是否在table上，是就跳過，這樣你就可以在Travel的時候delete item，不在table上的就是travel過的，剛好一建一刪來確保你的node剛好全部都travel
除非你一定要求最短距離，不然Travel的方法可以仿照我說的方式就執行就可以

------
不論是否我發的文，在能力範圍皆很樂意為大家回答問題。
為了補我的能力不足之處，以及讓答案可以被重複的使用，希望大家能儘量以公開的方式問問題。
在引述到我的文時自然會儘量替各位想辦法，謝謝大家！

你好，其實我要做得有點類似shortest path，因為要找出min hop count，若node接收到兩個以上來自他的neighbor傳來的距離root的距離。
例如：(第一張圖)
收到n0會收到n8跟n7的訊息。其中n8送出的訊息會告訴n0距離root只有一步距離，但是n7告訴n0距離root有兩步距離，因此他就要判斷最短的是哪一個。
因此，(第二張圖中)才會有n0不只出現一次。我有考慮過用table去查詢，但是這樣無法保證收到的是最短的距離。
不好意思，一開始沒說明清楚。

===================引 用 文 章===================
看你用什麼當key，在建Tree的時候加入table，並對將要拜訪的node查詢是否在table上，是就跳過，這樣你就可以在Travel的時候delete item，不在table上的就是travel過的，剛好一建一刪來確保你的node剛好全部都travel
除非你一定要求最短距離，不然Travel的方法可以仿照我說的方式就執行就可以

我想到一個方法了，晚一點把流程po上來。
感謝你的討論，為了給你鼓勵先結案。
到時候我有問題記得跟我一起討論。

type TNode = class
NodeID : integer;
NodeStep : integer;
ParentNode : PNode;
function getChildNodes : array of PNode;//取得Node的所有child node
end;
type PNode = ^TNode;//就是一個TNode type的指標型態


funciton RTravel(PNode);
var
ChildeNodes : array of TNode;
ind : integer;
begin
ChildNodes := PNode^.getChildNodes;
PNode^.NodeStep:=PNode^.NodeSep 1;//預設nodestep為0，先加之後再減回來
if Length(ChildNodes)>0 then //判斷是否有child node
for ind:=0 to Length(ChildNodes)-1 do //依次拜訪child
begin
if (ChildNodes[ind].NodeStep=0) or (ChildNodes[ind].NodeStep>=PNode^.NodeStep) then
begin //如果child 未被拜訪過，或者是child的上一次演算路徑過長，就把child的parent改成自己
ChildNodes[ind]=PNode;
ChildNodes[ind].NodeStep=PNode^.NodeStep;
end;
RTravel(ChildNodes[ind]);
end;
PNode^.NodeStep:=PNode^.NodeStep-1;
end;

這樣的想法應該OK？不過先決條件應該是Network本身是單向的..
如果是雙向那麼就要另外加一個Table去列cycle path
這個Travel完之後，每個Node會決定自己的上一個Node是誰(才是最短的)
而NodeStep將會包含min count
如果需要實際路線，就再用另外一個recursive function去找childnode的parent是自己的往下走就可以了
我想你應該是用C 寫，不過我懶得想C 怎麼寫了，就把這個當虛擬碼吧XD

------
不論是否我發的文，在能力範圍皆很樂意為大家回答問題。
為了補我的能力不足之處，以及讓答案可以被重複的使用，希望大家能儘量以公開的方式問問題。
在引述到我的文時自然會儘量替各位想辦法，謝謝大家！

我最後用的方法是這樣：
void Flooding(int ParentID)
{
int parentHC=Node[ParentID].min_hop_count_to_root;
int childHC;
for(int i=0;i {
childHC=parentHC 1;
if(Node[Node[ParentID].Neighbor[i].Node_ID].min_hop_count_to_root <= childHC)
{
if(Node[Node[ParentID].Neighbor[i].Node_ID].min_hop_count_to_root != -1)
Node[ParentID].Neighbor[i].stop=true;
else
{
Node[Node[ParentID].Neighbor[i].Node_ID].min_hop_count_to_root=childHC;
Flooding(Node[ParentID].Neighbor[i].Node_ID);
}
}
if(Node[Node[ParentID].Neighbor[i].Node_ID].min_hop_count_to_root > childHC)
{
Node[Node[ParentID].Neighbor[i].Node_ID].min_hop_count_to_root=childHC;
Flooding(Node[ParentID].Neighbor[i].Node_ID);
}
}
}

上圖是我做出來的Shortest Path Tree。紅色的點是root
在建立之前，每個node如果可以互相通訊，我就把距離設定為1。
因此建立出來的Tree每段path的cost都是1
目前有一個問題，由上面的圖形可以大概看出，被藍色的線區分為幾個sub-tree，因為我是用遞迴的方式去travel，因此做出來的tree會有點像是Deep first search的樣子。
但是這樣做出來跟我想像的不太一樣，我希望他是root開始，有點像是同時broadcast，逐漸往外。
我所希望的是應該只有最右邊的藍線而不是出現右邊的那兩條藍線。
因為昨天開始熬夜寫這個，頭腦已經開始不太清楚了。如果我有觀念不對希望可以提醒我一下。
現在我有點懷疑我做出來的會不會不是shortest path tree。
我會這樣懷疑是因為，這是我實作一篇paper的程式，我要找出最右邊那條藍線的周圍node的最近的共同ancestor，
根據paper的說法是，在最右邊藍線周圍的node (在一開始的時候必須就是neighbor)，最近的共同ancestor應該很遠(有個threshold)，
而其他地方的node (在一開始的時候必須就是neighbor) 相對之下沒這麼遠，藉此找出藍色這個邊界。
但是，由圖中可以看出，右邊的tree像是細長型的，兩個sub-tree很接近，若在這兩個sub-tree各取一個node (在一開始的時候必須就是neighbor) ，
則他們的共同ancestor，仍然距離很遠，跟我想像的完全不一樣。

這個問題是我最後才發現的，昨天寫了一整天都以為是我在判斷最近的共同ancestor寫錯了，看來好像是我的shortest path tree建立就有問題了。
麻煩各位幫我看一下，我在猜是不是我想法錯了。謝謝

關於這個，我今天想了一下，我認為我自己的travel方式是DFS，而且從一開始就是DFS
這是為了簡單的確保所有node會被travel且朝容易解決cycle的方向描述的，
但是我想了一下，我的DFS因為會自己決定上一個node是誰才會離root比較近
所以travel完畢應該不會有不是shortest path的問題，

但是有一個可能性，就是原先的shortest path如果只是單單參照DFS的方式，
可能會忽略cycle path的shortest path的可能，這點我沒有很仔細的去驗證，所以先提出假設
我不知道你的會不會，但我想我上面寫的因為沒有考慮cycle path而不走，所以可以試著用那樣的方式去跑跑看
檢查是否經過這個node之前所用的root到這個node所經過的node時就停掉它就好了//因為最短路徑不可能是走了一圈之後再從root出發會比較快

------
不論是否我發的文，在能力範圍皆很樂意為大家回答問題。
為了補我的能力不足之處，以及讓答案可以被重複的使用，希望大家能儘量以公開的方式問問題。
在引述到我的文時自然會儘量替各位想辦法，謝謝大家！

我在求shortest path的做法是：
先從root broadcast，然後他的neighbor紀錄hop count=1，
如此傳下去，如果同一個點收到兩個以上的hop count，就取最小的那個，同時紀錄是由哪個點傳來的。
所以我建立shortest path tree的方式是，把所有點所紀錄造成最小hop count的點都連起來，就形成上述的圖形。我認為這樣好像就是shortest path tree。
我驗證過edge數目，沒有cycle的情形發生，且剛好符合tree的條件。
我是在想，因為點數很多，而且每個點的neighbor我算過大約是10 (藉由調整通訊範圍來調整degree ) ，因此shortest path tree應該不是唯一的。
只是這樣做出來的結果跟我想像的差距太大。星期二就要給老師看了，看來只好暫時用作弊的方法了。我還想好好跨年