リンクリストを使用したC++での隣接リストの実装

Question

私は隣接リストの多くの実装を見てきました。ここでは、私はC++を使って実装しようとしています。あなたは私のC++の構造からわかるように、私はC++の初心者です。ここで私は自分のコードを実行しようとして苦労しています。私の現在の問題は、グラフ全体を通らないということです。セグメンテーション違反が発生します。 結果：

頂点：0

1->

頂点：1

2-> 3->

頂点：2

頂点：3

頂点：4

セグメント違反

これを実行するには何か助けが必要です。私はDFSアルゴリズムを実装したい。すべてのヒントは素晴らしいだろう！ここで

はヘッダーです：

#ifndef DFS_H 
#define DFS_H 

class DFS{ 
private: 
    struct vertex{ 
     int data; 
     bool visited; 
     struct vertex* next; 
    }; 
    int V; 
    struct vertex* G[20]; 
public: 
    DFS(int vertices); 
    vertex* addVertex(int data); 
    void addEdge(int index, int data); 
    void dfs(int vertex); 
    void printGraph(); 
}; 

#endif 

のcppファイル：

#include "DFS.h" 
#include <iostream> 
#include <cstdlib> 
using namespace std; 
DFS:: DFS(int vertices){ 
    this->V=vertices; 
    for(int i=0; i<V; i++){ 
     G[i]= NULL; 
    } 
} 
DFS::vertex* DFS::addVertex(int data){ 
    struct vertex* newNode= new vertex; 
    newNode->data= data; 
    newNode->next= NULL; 
    newNode->visited=false; 
    return newNode; 
} 
void DFS:: addEdge(int index, int data){ 
    struct vertex* cursor; 
    struct vertex* newVertex= addVertex(data); 

    if(G[index]==NULL) 
     G[index]=newVertex; 
    else{ 
     cursor=G[index]; 
     while(cursor->next!=NULL) 
      cursor=cursor->next; 
     cursor->next= newVertex; 
    } 
} 
void DFS::printGraph(){ 
    for(int i=0; i<V; i++){ 
     struct vertex* cursor= G[i]; 
     cout<<"vertex: "<<i<<endl; 
     while(cursor->next!=NULL){ 
      cout<<cursor->data<<"->"; 
      cursor=cursor->next;  
     } 
     cout<<endl; 
    } 
} 
void DFS:: dfs(int vertex){ 
} 
int main(){ 
    DFS dfs(5); 
    dfs.addEdge(0,1); 
    dfs.addEdge(0,4); 
    dfs.addEdge(1,2); 
    dfs.addEdge(1,3); 
    dfs.addEdge(1,4); 
    dfs.addEdge(2,3); 
    dfs.addEdge(3,4); 

    dfs.printGraph(); 
    return 0; 
} 

*あなたの助けStackOverflowのコミュニティのための

ありがとう！

Answer 1

segfaultは、すべてVの頂点が存在すると仮定したprintGraphから来ていますが、これはあなたのケースでは当てはまりません。 5番目の頂点を初期化するdfs.addEdge(4, ...)がないことに注意してください。

長さが後で設定される要素の数と一致しなければならないという一般的なアプローチでは、問題を尋ねていますが、私はこのコードをvectorを使って記憶にリファクタリングします。 addEdge(1,2)とaddEdge(1,3)はエッジ1であなたを残します：

もう一つの問題は、addEdgeは常に3

もう一つは、頂点の異なるインスタンスを指しますdfs.addEdge(1,3)とdfs.addEdge(2,3)頂点1と2の後に意味の新しいvertexをインスタンス化することです2-> 3。私はその結果が端でなければならないと仮定する。1-> 2と1-> 3。

から裸のnew edポインタを返すことは、メモリリークを要求していることは言うまでもありません。 auto_ptr（C++ 11の場合はunique_ptr）を使用することをお勧めします。

さらに、std::forward_listが利用可能な場合、フォワードリンクリストを再実装しています。

これはちょうどあなたのコードを見ればわかります。正直言って、それはかなり悪い（犯行ではない、私たちはすべて初心者であった）ので、より多くがあると確信しています。@Betaは、一度に1つのことを学び実践することを提案しています（頂点リストを作成し、エッジを表現する方法に慣れてから、それをトラバースしようとする、単純なアルゴリズムを構築するなど）。