如何在C++中表示圖形

Question

我想編寫創建MST的prim和dijkstra算法。但我不知道用C++表示圖表的最佳方式是什麼。

我可以通過一對兩個整數表示一個邊，例如向量0到1應該是pair（0,1）;

typedef pair<int, int> Edge; 

然後，prim函數將包含由邊和它的權重組成的對的Vector。

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

我認爲這種方式不是最好的，有誰能告訴我什麼方法可以最好地表示圖嗎？

Answer 1

我前段時間一直在實現Dijkstra以查找二進制映像中的路徑。我將一張圖表示爲結構爲GraphNodes的矢量，其中包含一個包含節點到其他節點的所有連接的Connections向量。每個連接都有其距離屬性，這是邊緣的權重。下面是我用了兩個結構：

//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的距離屬性是它目前在Dijkstra算法的距離，所以要開始節點的最短目前已知距離的遠近。在開始時，這是用-1初始化的。

我然後執行Dijkstra算法是這樣的：

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; 

} 

正如你看到有一個包含所有未使用的節點到目前爲止一套unusedNodes。它只包含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

的兩種主要的方式來表示圖表在理論計算機科學學會是adjacency matrix和adjacency lists。

鄰接矩陣如下圖所示是n * n矩陣，[i] [j]表示節點i和節點j之間的邊，所以如果它是加權圖，則它可以是整數而不是布爾值的未加權圖。

adjacency matrix (photo source: google)

在另一方面，鄰接表是一組中鏈表（正設置爲是精確的），第i個組具有正好i被連接到所述節點。 在這種情況下，你會需要一些額外的方法來保存邊緣的距離，例如，你可以建立自己的班級邊緣如下

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

，並用它爲你的鏈接列表。我曾經習慣於std::vector<std::pair<int, int>> a[N]來定義一個對列表，a[i][j].first將是第一個點的第i個鄰居和他們之間邊緣的長度。 對於無向圖，您可以將i添加到j鄰居。 所以它也是一種表示圖形的靈活方式。

adjacency lists (image source: google photos)

所以，現在讓我們來談談複雜，我會盡量保持儘可能簡單：

我們HABEñ列表，每個具有＃（邊走出節點i）的 所以總數是這個數的總和，這是邊的總數E. 這意味着地點複雜度是O（E），其在稀疏圖中至多5 * n與鄰接矩陣中的O（N^2）相比。 （我們需要E的線性因子來表示它）。 現在讓我們考慮訪問所有在鄰接矩陣中的鄰接點x： ，我們將遍歷整個第x行，如果它不是0，那麼存在O（N）的邊。 在鄰接列表中，它又是正好是x的鄰居的數量，它可以達到O（N）。但是如果我們正在訪問所有節點的所有鄰居（這是Dijkstra在更新dis陣列時的情況），則需要在鄰接列表中訪問n個元素n次，這在鄰接列表中也是O（N^2）時間複雜度列出它恰好是鄰居數的總和 - 再次E.這意味着我們還需要O（E）來訪問所有邊的所有鄰居。 並且信號的所有邊通常在輸入O（E）中作爲計算時間通過，但是O（N^2）對於例如N的約束是高複雜度的。 最後我將離開你我通常的實現使用鄰接表（矢量作爲列表）圖形diffreent變種：

#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; 
}