0

プログラムの深さ優先検索の作成に問題があります。これまでのところ、エッジのクラスとリージョンのクラスがあります。接続されているすべてのエッジをリージョンの 1 つのノード内に格納したいと考えています。既に実装した getKey() 関数によって何かが接続されているかどうかがわかります。2 つのエッジが同じキーを持つ場合、それらは接続されています。次のリージョンでは、そのリージョン内に接続されたエッジの別のセットを保存したいなどです。ただし、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
 }
4

2 に答える 2

0

n がエッジの総数であると仮定すると、k は領域の最終的な数です。必要な DFS の隣接リストを作成すると、O(n^2) のコストがかかりすぎる可能性があります (k=1 の場合、つまりすべてのエッジが同じリージョンに属している場合)。したがって、dfs は O(V+E)、つまり O(n^2) のコストがかかります最悪の場合。

それ以外の場合、問題は次のように O(n * log(k)) で簡単に解決できます。

  1. すべてのエッジをトラバースして、それらを対応する領域の先頭に追加します (バランスの取れた bst を使用します。たとえば、stl-map) [これにもハッシュを使用できます]
  2. すべての領域を横断し、必要な直線的な方法でそれらを接続します

私が推測する問題に対して、保証された O(n) ソリューションは存在しません。

于 2012-11-26T14:00:05.587 に答える
0

隣接リスト作成機能を実装してみました。adj_list struct の next ポインタは隣接リストを下に移動し (next で接続された 2 つのノード間に関係はありません)、リスト ポインタは隣接リストです。ノードには、隣接リストを持つ 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;
}
于 2013-06-08T22:55:38.387 に答える