有向圖實現

我需要在C++中實現一個有向圖（Directed graph）作爲家庭作業的一部分，我在如何表示頂點和邊數據類型時遇到了一些問題。
任何人都可以請我指向一個例子或一個簡單的C++類，實現這個，所以我可以研究它，並從那裏延伸？有向圖實現

我已經搜索了一下，但我只找到關於使用Boost或其他庫的結果，我只需要一些簡單的，不依賴於任何庫的結果。

謝謝。

來源

2010-01-28 daniels

digraph是標準圖論的命名法。 – 2010-01-28 18:37:05

@Neil：見http://en.wiktionary.org/wiki/digraph – 2010-01-28 18:40:06

@Greg見http://en.wikipedia.org/wiki/Digraphs_and_trigraphs - 但我會刪除我的評論。 – 2010-01-28 18:42:09

有代表與數據結構有向圖的兩個主要方面：

節點爲中心。此方法將每個節點表示爲程序中的一個對象，並且每個節點都包含有關其鏈接到的其他節點的信息。其他節點可以像在當前節點和目標節點之間存在有向邊的節點列表一樣簡單。

以邊緣爲中心。此方法將每個邊緣表示爲程序中的對象，並且每個邊都包含有關它連接的節點的信息。在有向圖中，每條邊都只有一個「源」和「目標」節點（如果您考慮自行循環，則可能是同一個節點）。這種方法實質上是一個有序對的列表。

根據你正在解決的問題，這兩種基本形式中的一種最終會變得最合適。更具體的算法可能需要向上述基本結構添加更多信息，例如從當前節點可到達的所有節點的列表。

來源

2010-01-28 18:43:40

這是一個非常好的答案。 – 2010-01-28 18:48:01

這個university paper可能會幫助你。

這不是最完整的，但它也許給你一個想法。我發現它非常有用，它也用於演講，所以不存在複製任何不應該的東西的風險。

來源

2010-01-28 18:35:02 Skurmedel

鬆散，有表示圖表2點直截了當的方式：

接續矩陣解釋的
列表。

根據不同的應用，每種方法都有優點/缺點。

＃2會涉及很多指針擺弄。

在進行圖形轉換時，＃1通常更易於使用。

不管是哪一種，你將有這樣的事情：

template<typename T> 
class node 
{ 
    public: 
    T data; 
};

和矩陣和列表清單類的將指向動態分配node的。

含義是你將有一個類和node類。

來源

2010-01-28 18:41:22

連接矩陣只適用於密集圖，密集圖較少見。你真的需要指定這個。通常，密集和稀疏表示的使用是相互排斥的，並且存在各種各樣的稀疏表示，它們不像列表的列表。 – Potatoswatter 2010-01-28 20:02:19

嘗試vector<NodeType>與multimap< NodeType *, EdgeType>。

multimap不支持下標[ x ]因此您需要使用edges.lower_bound()代替。

或者，map< pair< NodeType *, NodeType * >, EdgeType >可以幫助查找給定兩個節點的邊。我在一個相當繁重的項目中使用了這一點。

這裏的第一個建議一個例子：

struct NodeType { 
    int distance; 
    NodeType(int d) { distance = d; } 
}; 
struct EdgeType { 
    int weight; 
    NodeType *link; 
    EdgeType(int w, NodeType *l) { weight = w; link = l } 
}; 

vector<NodeType> nodes; 
nodes.reserve(3); 
nodes.push_back(NodeType(0)); 
nodes.push_back(NodeType(0)); 
nodes.push_back(NodeType(0)); 

multimap< NodeType *, EdgeType > edges; 
edges.insert(make_pair(&nodes[0], EdgeType(4, &nodes[2]))); 
edges.insert(make_pair(&nodes[0], EdgeType(1, &nodes[1]))); 
edges.insert(make_pair(&nodes[2], EdgeType(2, &nodes[0]))); 

for (multimap< NodeType *, EdgeType >::iterator iter = edges.lower_bound(&nodes[1]), 
    end = edges.upper_bound(&nodes[1]); iter != end; ++ iter) { 
    cerr << "1 connects to " << iter->second.link - nodes.begin() << endl; 
}

來源

2010-01-28 18:46:08 Potatoswatter

template<class T> 
class node 
{ 
public: 
    T data; 
    vector<node<T>*> edges; 
}

你很可能也想存儲的所有節點的list<node<dataType>*>。

來源

2010-01-28 18:48:46

回答

相關問題