基本概念
一個圖（graph）G=（V，E）由頂點（vertex）的集V和邊（edge）的集E組成。每一條邊就是一副點對（v，w），其中v、w ϵ V。有時也把邊稱做弧（arc）。
有向（directed）：如果點對是有序的，那麼圖就是有向的。
有向圖（digraph）：有向的圖有時也叫有向圖。路徑u，v，u可以被認為是圈，因為（u，v）和（v，u）不是同一條邊。
無向圖：與有向圖相對，我們要求邊是互異的。這些要求的根據在於無向圖中的路徑u，v，u不應該被認為是圈，因為（u，v）和（v，u）是同一條邊。
鄰接（adjacent）：頂點w和v鄰接當且僅當（v，w）ϵ E。在一個具有邊（v，w）從而具有邊（w，v）的無向圖中，w和v鄰接且v也和w鄰接。
權（weight）或值（cost）：邊具有的第三種成分。
路徑（path）：圖中的路徑是一個頂點序列w1，w2，w3，…，wN使得（wi，wi+1）ϵ E，1 ≤ i < N。
路徑的長（length）：路徑上的邊數。從一個頂點到它自身可以看成是一條路徑，如果路徑不包含邊，那麼路徑的長為0。
環（loop）：如果圖含有一條從一個頂點到它自身的邊（v，v），那麼路徑v，v有時也叫做環。
簡單路徑：一條簡單路徑是這樣一條路徑，其上的所有頂點都是互異的，但第一個頂點和最後一個頂點可能相同。
圈（cycle）：有向圖中的圈是滿足w1=wN且長至少為1的一條路徑。
簡單圈：滿足圈的定義，並且如果該路徑是簡單路徑，那麼這個圈就是簡單圈。
無圈的（acyclic）：如果一個有向圖沒有圈，則稱其為無圈的。一個有向無圈圖有時也簡稱為DAG。
基礎圖（underlying graph）：圖中其弧去掉方向所形成的圖。
連通的（connected）：如果在一個無向圖中從每一個頂點到每個其它頂點都存在一條路徑，則稱該無向圖是連通的。
強連通的（strongly connected）：先是連通的，然後具有這樣性質的有向圖稱其為強連通的。
弱連通的（weakly connected）：如果一個有向圖不是強連通的，但是它的基礎圖，即其弧上去掉方向所形成的圖，是連通的，那麼該有向圖稱為是弱連通的。
完全圖（complete graph）：完全圖是其每一對頂點間都存在一條邊的圖。
圖的表示
一個有向圖：
圖中有7個頂點和12條邊。
表示圖的一種簡單的方法是使用一個二維數組，稱為鄰接矩陣（adjacent matrix）表示法。對於每條邊（u，v），置A[u][v]等於true；否則，數組的元素就是false。如果邊有一個權，那麼可以置A[u][v]等於該權，而使用一個很大或者很小的權作為標記表示不存在的邊。
雖然這樣表示的優點是非常簡單的，但是，它的空間需求則為θ(|V|2)，如果圖的邊不是很多，那麼這種表示的代價就太大了。若圖是稠密（dense）的：|E|=θ(|V|2)，則鄰接矩陣是合適的表示方法。
如果圖不是稠密的，換句話說，如果圖是稀疏的（sparse），則更好的解決方法是使用鄰接表（adjacency）表示。對每一個頂點，我們使用一個表存放所有鄰接的頂點。此時的空間需求為O(|E|+|V|),它相對於圖的大小而言是線性的。如果邊有權，那麼這個附加信息也可以存儲在鄰接表中。
圖的鄰接表表示法：
鄰接表是表示圖的標准方法。無向圖可以類似地表示，每條邊（u，v）出現在兩個表中，因此空間的使用基本上是雙倍的。在圖論算法中通常需要找出與某個給定頂點v鄰接的所有的頂點。而這可以通過簡單地掃描相應的鄰接表來完成，所用的時間與這些找到的頂點的個數成正比。
有幾種方法保留鄰接表。首先注意到，這些鄰接表本身可以被保存在任何種類的List，即ArrayList或LinkedList中。然而，對於非常稀疏的圖，當使用ArrayList時程序員可能需要從一個比默認容量更小的容量開始ArrayList。否則可能造成明顯的空間浪費。
因為關鍵在於能夠迅速得到與任一頂點鄰接的那些頂點的表，所以兩個基本的選擇是，或者使用一個映射，在這個映射下，關鍵字就是那些頂點而它們的值就是那些鄰接表，或者把每一個鄰接表作為Vetex類的數據成員保存起來。這第1個選擇論證要簡單，而第2個選擇可能會更快，因為它避免了在映射下的重復查找。
在第2種情形，如果頂點是一個String，那麼可以使用映射，在映射下，關鍵字是頂點名而關鍵字的值則是一個Vertex，並且每一個Vertex對象擁有一個鄰接頂點表，或許還有原始的String串名。
