為什麼大多數編程語言的內建抽象數據類型沒有圖？

01-03

像C++，Java，C#的標準庫都有容器類，提供了棧、隊列、鏈表等等讓人直接使用，但是圖往往還是要自己去實現。我想知道這方面的取捨主要是取決於什麼？

1. 一般內建的容器庫，其內部表達方式都很有限，例如「表」不外乎數組，鏈表，哈希。而鏈表，隊列，棧，環表，哈希之類的數據結構都是架構在這些有限的表述方式上。只要把內部表達實現好，根據一些具體慣用法封裝API就好了。而圖的種類很多，內部表達方式也不相同（每個結點作為一個獨立數據結構持有相鄰結點的引用這種方式只不過是圖的其中一種表達方案，而且效率往往不高，結點之間的路徑往往也需要複雜的數據結構去表達），選用哪種表達方式往往會影響到執行效率甚至演算法設計。要通用的話，就需要實現所有常用的表達方式，並設計一種方案讓這些表達方式與常用演算法組合起來，複雜度很可觀。

2. 很大一部分涉及圖或樹的實際問題，有效率的解決方式不是建好圖或樹後再根據現有的數據結構求解，而是邊構造邊求解（演算法的重點在於如何從現有結點擴展出新的結點）。因此針對固定圖或樹去設計的演算法庫應用範圍不如想像中大。

3. 考慮到用戶的知識結構，對於一般的集合容器，用戶能很直觀地理解其用法，把具體問題對應到容器API上，而實現過程則顯得重複繁瑣：一個入門級的程序員知道該使用表來儲存並進行排序，但一時不知道如何實現qsort是常見情況。而對於圖，如果用戶的知識結構足以根據具體問題對應到圖論演算法，並選用合適的表述方式來構造好這個圖，自己動手實現一些對圖的經典操作相對來說沒有難度，還能更貼合具體場景。

綜上，實現一個圖的通用演算法庫既複雜又沒有太大的現實意義，要做庫，還不如結合到某類具體場景做一個專用的庫（底層用圖來實現）。

一般來說你用到圖就說明接下來你要做一些對於庫模板來說很dirty的操作了。

有向還是無向？

是否允許重邊和/或自環？

邊和頂點的id是int還是string？是否可以是自定義類型？是否要求該類型能用作tree map和/或hash map的key？

邊和頂點的權重是int還是double？是否允許負值？是否也可以是自定義類型？是否還允許不設權重以節省內存？

邊和頂點是否還可以關聯其他數據（比如顏色）？這些數據的類型是否可自定義？

提供哪些遍歷演算法？如何設計介面？迭代器還是回調？

還需要提供哪些操作？dijkstra/floyd/kruskal/prim/等等？

用鄰接矩陣還是鄰接表實現？

鄰接表的node要不要用pool來分配？

是否支持文件輸入輸出？支持哪些格式？

圖是否大到一台機器裝不下？要不要支持圖的壓縮表示？

做標準庫的人如何取捨以上功能？功能做少了沒人用，做多了又介面複雜學習成本高一樣沒人用。

首先是很少人用到。然後由於圖的用途變化較多，設計一套通用的介面然後作為語言標準庫，這樣估計會是很重的一個庫。所以說，原因就是這沒必要作為"語言內建」的東西。有需求的人自然會去用第三方的庫。

boost graph庫實現了

===============

原因陳碩聚聚說的很好了

@陳碩的回答感覺沒說到點上， @趙劼則是完全沒說清楚

我的理解是，數據結構課里學的那些數據結構，都是抽象的數據結構，是為了研究數據結構本身的性質而構建的概念。這些概念本身就不是讓你直接在工程實踐中用的，課本上的演算法（比如鏈表的插入、圖的遍歷），那是為了講解原理不得不引入的東西，並不是數據結構本身。

而具體的編程語言，是為了解決具體問題的，之所以要「實現」數據結構，是因為數據結構對具體問題的解決有幫助。事實上，編程語言並沒有「實現」數據結構，他們只是根據數據結構的原理，設計了自己的語法和庫函數而已。

比如，C語言為了解決不同的問題，可以使用連續內存的數組，也可以使用結構+指針為基礎的鏈表，這些都是線性表這種抽象數據結構的一種應用。

總之，編程語言的設計就是針對具體問題的取捨，有些問題非常典型通用，以至於為他設計了語法；有些問題典型性差了一點，就為他設計了庫函數；還有些問題典型性又差了一些，就把它交給用戶或者第三方。而在解決這些問題是，用到了抽象數據結構中的一些原理，比如線性表，樹，等等。

不知道說的清不清楚，要不 @pansz也來說說？

什麼叫做圖？你想怎麼表現這個數據結構？你想用它來幹什麼？你看，我看到你這個問題，都不知道這個「圖」具體是要做什麼的，那麼對於類庫提供者來說，他該怎麼給你一個合適的容器類？

項目利用了BGL，boost graph library. 如果需要並行還有PBGL

apache Amino 這個項目就實現了Graph 這個結構，包括有向和無向, 而且是lockfree哦~！

文檔連接： http://amino-cbbs.sourceforge.net/java_apidocs/index.html

上學期數據結構課上強制要求學習labview ,結構圖像化,導入.c文件可直觀觀察功能