圖論(Graph Theory)是離散數學的一個分支，是一門研究圖(Graph)的學問。
圖是用來對對象之間的成對關系模組化的數學結構，由"節點"或"頂點"(Vertex）以及連接配接這些頂點的"邊"（Edge）組成。
值得注意的是，圖的頂點集合不能為空，但邊的集合可以為空。圖可能是無向的，這意味着圖中的邊在連接配接頂點時無需區分方向。否則，稱圖是有向的。下面左圖是一個典型的無向圖結構，右圖則屬于有向圖。本章節介紹的圖都是無向圖。
圖的分類：無權圖和有權圖，連接配接節點與節點的邊是否有數值與之對應，有的話就是有權圖，否則就是無權圖。
圖的連通性：在圖論中，連通圖基于連通的概念。在一個無向圖 G 中，若從頂點 i 到頂點 j 有路徑相連（當然從j到i也一定有路徑），則稱 i 和 j 是連通的。如果 G 是有向圖，那麼連接配接i和j的路徑中所有的邊都必須同向。如果圖中任意兩點都是連通的，那麼圖被稱作連通圖。如果此圖是有向圖，則稱為強連通圖（注意：需要雙向都有路徑）。圖的連通性是圖的基本性質。
完全圖：完全是一個簡單的無向圖，其中每對不同的頂點之間都恰連有一條邊相連。
自環邊：一條邊的起點終點是一個點。
平行邊：兩個頂點之間存在多條邊相連接配接。
圖可用于在實體、生物、社會和資訊系統中模組化許多類型的關系和過程，許多實際問題可以用圖來表示。是以，圖論成為運籌學、控制論、資訊論、網絡理論、博弈論、實體學、化學、生物學、社會科學、語言學、計算機科學等衆多學科強有力的數學工具。在強調其應用于現實世界的系統時，網絡有時被定義為一個圖，其中屬性(例如名稱)之間的關系以節點和或邊的形式關聯起來。
鄰接矩陣：1 表示相連接配接，0 表示不相連。
鄰接表：隻表達和頂點相連接配接的頂點資訊
鄰接表适合表示稀疏圖 (Sparse Graph)
鄰接矩陣适合表示稠密圖 (Dense Graph)
源碼包下載下傳：Download
(1) 鄰接矩陣
package runoob.graph;
/**
* 鄰接矩陣
*/
public class DenseGraph {
// 節點數
private int n;
// 邊數
private int m;
// 是否為有向圖
private boolean directed;
// 圖的具體資料
private boolean[][] g;
// 構造函數
public DenseGraph( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0;
this.directed = directed;
// g初始化為n*n的布爾矩陣, 每一個g[i][j]均為false, 表示沒有任和邊
// false為boolean型變量的預設值
g = new boolean[n][n];
}
// 傳回節點個數
public int V(){ return n;}
// 傳回邊的個數
public int E(){ return m;}
// 向圖中添加一個邊
public void addEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
if( hasEdge( v , w ) )
return;
g[v][w] = true;
if( !directed )
g[w][v] = true;
m ++;
// 驗證圖中是否有從v到w的邊
boolean hasEdge( int v , int w ){
return g[v][w];
}
（2）鄰接表
import java.util.Vector;
* 鄰接表
public class SparseGraph {
private Vector<Integer>[] g;
public SparseGraph( int n , boolean directed ){
this.m = 0;
// g初始化為n個空的vector, 表示每一個g[i]都為空, 即沒有任和邊
g = (Vector<Integer>[])new Vector[n];
for(int i = 0 ; i < n ; i ++)
g[i] = new Vector<Integer>();
public void addEdge( int v, int w ){
g[v].add(w);
if( v != w && !directed )
g[w].add(v);
for( int i = 0 ; i < g[v].size() ; i ++ )
if( g[v].elementAt(i) == w )
return true;
return false;