爲DFS創建鄰接列表

Question

我無法爲我的程序創建深度優先搜索。到目前爲止，我有一類邊緣和一類區域。我想將所有連接的邊存儲在我的區域的一個節點內。我可以通過我已經實現的getKey（）函數來判斷是否有連接。如果兩個邊緣具有相同的鍵，則它們連接。對於下一個區域，我想在該區域內存儲另一組連接的邊，等等。但是，我沒有完全理解DFS，並且在實現它時遇到了一些麻煩。我不知道何時/何地再次調用DFS。任何幫助，將不勝感激！

class edge 
{ 
    private: 
    int source, destination, length; 
    int key; 
    edge *next; 
    public: 
    getKey(){ return key; } 
} 

class region 
{ 
    edge *data; 
    edge *next; 
    region() { data = new edge(); next = NULL; } 

}; 

void runDFS(int i, edge **edge, int a) 
{ 
    region *head = new region(); 
    aa[i]->visited == true;//mark the first vertex as true 
    for(int v = 0; v < a; v++) 
    { 
    if(tem->edge[i].getKey() == tem->edge[v].getKey()) //if the edges of the vertex have the same root 
    { 
     if(head->data == NULL) 
     { 
      head->data = aa[i]; 
      head->data->next == NULL; 
     } //create an edge 
     if(head->data) 
     { 
      head->data->next = aa[i]; 
      head->data->next->next == NULL; 
     }//if there is already a node connected to ti 
    } 
    if(aa[v]->visited == false) 
     runDFS(v, edge, a); //call the DFS again 
    } //for loop 
} 

Answer 1

假設n是邊的總數，k是最終的區域數。 （n = 2）（如果k = 1，即所有邊都屬於同一個區域），因此dfs將花費你O（V + E），即O（n^2）在最壞的情況下。

否則問題是爲O容易解決（N *日誌（k））的如下：（。使用平衡BST例如STL-MAP）

1. 遍歷通過所有邊緣將它們添加到對應的區域的頭部[你可以使用散列這太]
2. 遍歷所有的地區，他們在必要的線性方式連接

不保證O（n）的解決方案存在我想這個問題..

Answer 2

我試圖實現一個鄰接列表創建函數。adj_list結構的下一個指針會將您拉下鄰接列表（下一個連接的兩個節點之間沒有關係），而列表指針是鄰接列表。該節點具有具有其鄰接列表的adj_list的地址。

struct node{ 
    int id; 
    adj_list* adj; 

}; 


struct adj_list{ 
    adj_list* next; 
    adj_list* list; 
    node* n; 
    adj_list(node& _n){ 
     n = &(_n); 
     next = NULL; 
     list = NULL; 
    } 
}; 

node* add_node(int id,std::queue<int> q , node* root) 
{ 
    node* n = new node(id); 
    adj_list* adj = new adj_list(*n); 
    n->adj = adj; 

    if(root == NULL){ 
     return n; 
    } 
    std::queue<adj_list*> q1; 

    while(1){ 
     adj_list* iter = root->adj; 
     if(q.empty())break; 
     int k = q.front(); 
     q.pop(); 
     while(iter){  
      if(iter->n->id == k){ 
       q1.push(iter); 
       adj_list* temp = iter->list; 
       iter->list = new adj_list(*n); 
       break; 
      } 
      iter = iter->next; 
     } 
    } 

    adj_list* iter = root->adj; 
    while(iter->next){ 
     iter = iter->next; 
    } 

    iter->next = adj; 

    while(!q1.empty()){ 
     adj_list* temp = q1.front(); 
     q1.pop(); 
     adj->list = temp; 
     adj = temp; 
    } 
    return root; 
}