C++でグラフを表現する方法

Question

MSTを作成するプリムとダイクストラのアルゴリズムを書きたいと思います。しかし、私はグラフをC++で表現する最良の方法は何か分かりません。

私は2つのintのペアでエッジを表すことができます。たとえば、ベクトル0〜1はペア（0,1）です。

typedef pair<int, int> Edge; 

そして、プリム関数は、エッジとその重みからなるペアのVectorをとることになります。

void prims(vector<pair<Edge, int>>); 

私はこの方法が最善の方法ではないと考えています。グラフを表現するにはどのような方法が良いと思いますか？

Answer 1

私はバイナリイメージでパスを見つけるために、ある時間前にDijkstraを実装しています。私は、のベクトルを含む構造体GraphNodesのベクトルとしてグラフを表しました。このベクトルは、ノードの他のノードへのすべての接続を含んでいました。各接続には、エッジの重みであるdistance属性があります。ここで私が使用される二つの構造体は、以下のとおりです。

//forward declaration 
struct GraphNode; 
struct Connection { 
    Connection() : distance(1) { }; 
    Connection(GraphNode* ptr, double distance) : ptr(ptr), distance(distance) { }; 
    bool operator==(const Connection &other) const; 
    GraphNode* ptr; 
    double distance; 
}; 

struct GraphNode { 
    GraphNode() : connections(8), predecessor(NULL), distance(-1) { }; 
    cv::Point point; 
    double distance; 
    GraphNode* predecessor; 
    std::vector<Connection> connections; 
}; 

bool Connection::operator==(const Connection &other) const { 
    return ptr == other.ptr && distance == other.distance; 
} 

GraphNodeの距離属性は、それが現在ダイクストラアルゴリズムであり、距離なので、開始ノードまでの最短現在知られている距離の距離。最初は-1で初期化されています。

私は、このようにダイクストラアルゴリズムを実装：あなたは、これまで使用していないすべてのノードを含むセットunusedNodesがある見たよう

std::vector<cv::Point> findShortestPathDijkstra(std::vector<GraphNode>& graph, int startNodeIndex, int destNodeIndex) const { 
    GraphDistanceSorter sorter(graph); 
    std::set<GraphNode*, GraphDistanceSorter> unusedNodes(sorter); 
    for (int i = 0; i < graph.size(); ++i) { 
     unusedNodes.insert(&graph[i]); 
    } 

    while (unusedNodes.size() > 0) { 

     GraphNode* currentNode = *unusedNodes.begin(); 
     if (currentNode->distance == -1) { 
      return std::vector<cv::Point>(); 
     } 
     if (currentNode == &graph[destNodeIndex]) break; 
     unusedNodes.erase(currentNode); 
     //update distances of connected nodes 
     for (Connection const& con : currentNode->connections) { 
      /*here we could check if the element is really in unusedNodes (search, O(log n)), but this would 
      actually take longer than calculating the new distance (O(1)), which will in this case always be greater 
      than the old one, so the distance is never updated for nodes not in unusedNodes()*/ 
      double newDistance = currentNode->distance + con.distance; 
      if (newDistance < con.ptr->distance || con.ptr->distance == -1) { 
       unusedNodes.erase(con.ptr); 
       con.ptr->distance = newDistance; 
       con.ptr->predecessor = currentNode; 
       unusedNodes.insert(con.ptr); 
      } 
     } 
    } 

    //now trace back the path as a list of points 
    std::vector<cv::Point> points; 
    GraphNode* current = &graph[destNodeIndex]; 
    points.push_back(current->point); 
    while (current != &graph[startNodeIndex]) { 
     if (current->predecessor == NULL) return std::vector<cv::Point>(); 
     current = current->predecessor; 
     points.push_back(current->point); 
    } 

    return points; 

} 

。 graphNodes上のポインタのみを含んでいます。実際のグラフ表示はベクトル内にあります。セットを持つ利点は、それが常に特定の基準に従ってソートされることです。私は自分のソーターGraphDistanceSorterを実装して、Dijkstraアルゴリズムの距離基準に従ってGraphNodesをソートしました。私はちょうどセットから最初のノードを選択し、それが最小の距離を持つ一つだということを知っている必要があり、この方法：

struct GraphDistanceSorter { 
    bool operator() (const GraphNode* lhs, const GraphNode* rhs) const; 
}; 

bool GraphDistanceSorter::operator() (const GraphNode* lhs, const GraphNode* rhs) const { 
    if (lhs->distance == rhs->distance) { 
     return lhs < rhs; 
    } else { 
     if (lhs->distance != -1 && rhs->distance != -1) { 
      if (lhs->distance != rhs->distance) { 
       return lhs->distance < rhs->distance; 
      } 
     } else if (lhs->distance != -1 && rhs->distance == -1) { 
      return true; 
     } 
     return false; 
    } 
} 

Answer 2

グラフを表す2つの主な方法は、理論計算機科学で学んだがadjacency matrixとadjacency listsです。

隣接行列は、n * n行列であり、[i] [j]はノードiとノードjの間の辺を表します。したがって、重み付きグラフの場合、a重み付けされていないグラフのブール値。一方

adjacency matrix (photo source: google)

は、隣接リストは、リンクされたリスト（正確にはNセット）、i番目のセットは私が接続されている正確ノードを持つのセットです。あなたは

class Edge 
{ 
    int destination, length; 
    Edge* next = 0; 
} 

を次のように独自のクラスのエッジを構築し、あなたのリンクリストのためにそれを使用することができ、たとえばエッジまでの距離を保存するためのいくつかの追加の方法が必要になります。この場合、 。ペアのリストを定義するためにstd::vector<std::pair<int, int>> a[N]に慣れていて、a[i][j].firstはnod iのj番目のネイバーとなり、a[i][j].secondはそれらの間のエッジの長さになります。 無向グラフの場合は、iをj近隣に追加することもできます。 したがって、グラフを柔軟に表現することもできます。

adjacency lists (image source: google photos)

だから今、私はできるだけ単純にそれを維持しようとします、の複雑さをお話しましょう：

私たちは、n個のリストをhabe、それぞれが＃を持っている（エッジがノードiの出入り） ので、総数はこの数の総和であり、エッジの総数です。 これは、隣接行列のO（N^2）と比較して、場所の複雑さがO（E）であり、スパースグラフでは最大5 * 。 （それを表現するためにEの線形因子が必要です）。 ここで、ノードxのすべての隣接ノードを訪問することを考えてみましょう。隣接行列では 、x行全体に行き、0でない場合はO（N）のエッジがあります。 隣接リストでは、O（N）に達する可能性のあるxの隣人の数と同じです。 しかし、もし私たちがすべてのノード（Di配列を更新するときにDijkstraの場合）のすべての隣人を訪れていれば、隣接関係の中でもO（N^2）時間の複雑さでもあるn個の要素をn回訪問する必要がありますそれはちょうど隣人の数の合計です - 再びE.これはすべての縁のすべての隣人を訪問するO（E）を必要とすることを意味します。 そして、すべての辺は通常O（E）が計算時間として渡されますが、O（N^2）は例えばN < = 10^6という制約では複雑になります。

#include<iostream> 
#include<vector> 
int main(){ 
    const int N = 5; 
    int n, e; 
    std::vector<std::pair<int, int>> graph[N], inverse[N]; 
    std::vector<int> unweighted[N], undirectedUnweighted[N]; 
    std::cin >> n >> e; 
    for(int i = 0; i < e; i++) 
    { 
     int x, y, z;//z is length of edge 
     std::cin >> x >> y >> z; 
     //substitute 1 from x, y if they starts from 1 
     graph[x].push_back(std::make_pair(y, z)); 
     inverse[y].push_back(std::make_pair(x, z)); 
     unweighted[x].push_back(y); 
     undirectedUnweighted[x].push_back(y); 
     undirectedUnweighted[y].push_back(x); 
    } 
    return 0; 
}