我正在為迷宮程式中的路徑查找實作圖形結構。在某些操作中，例如：遍歷圖，釋放圖（之前是 malloc-ed，或使用廣度優先搜索，... 需要檢查是否訪問了頂點。
這是vertex和edge結構：
typedef struct graph
{
// val just use to label the vertex
int val;
// since the maze just has 4 directions,
// I simplify vertex to just point to 4 other vertices
edge up;
edge down;
edge left;
edge right;
}vertex;
typedef struct Edge
{
int weight;
vertex *neighbour;
bool visited;
}edge;
我想過2個解決方案。第一個是 add bool visited;invertex或edgestruct 并將其初始化為false，但它只能使用 1 次，因為我不知道如何重新初始化visited. 第二種方法是創建一個鏈接串列，將訪問的頂點放入該串列中，并在需要時檢查該串列中的訪問頂點。但是當有數百個頂點時，它會花費很多作業。
那么檢查頂點是否被訪問的好機制是什么？實作這個問題的更好方法是什么？
任何幫助，將不勝感激。
uj5u.com熱心網友回復：
對于您的第一個解決方案，您可以將 bool 訪問添加到邊緣和頂點，并且每當您訪問某些內容時，您將其添加到鏈接串列中，因此當您完成并且想要將它們重新初始化為 false 時，您可以在鏈接串列上進行一次傳遞并更新它們的值，然后清除鏈表。
另一種解決方案是，當您訪問一個節點或一條邊時，您將它們放入一些平衡的二叉搜索樹（map、set ...或您自己實作的東西）中，這些允許您添加一個元素或檢查一個O(log(n)) 中存在一個元素，其中 n 是元素的總數。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/464186.html
上一篇：浮點文字中有效十進制數字的最小數量是多少，以盡可能正確地表示該值？
下一篇：如何將字串陣列傳遞給C中的函式