圖是一種： ? 數據元素間存在多對多關系的數據結構 ? 加上一組基本操作構成的抽象數據類型。
圖 (Graph) 是一種復雜的非線性數據結構，由頂點集合及頂點間的關系（也稱弧或邊）集合組成。可以表示為： G＝(V, VR) ?
其中 V 是頂點的有窮非空集合；
VR 是頂點之間 ? 關系的有窮集合，也叫做弧或邊集合。
弧是頂點的有序對，邊是頂點的無序對。
?
特點：（相對于線性結構）
頂點之間的關系是任意的?
圖中任意兩個頂點之間都可能相關
頂點的前驅和后繼個數無限制
?
相關概念：
?
頂點(Vertex)：圖中的數據元素。線性表中我們把數據元素叫元素，樹中將數據元素叫結點。
邊：頂點之間的邏輯關系用邊來表示，邊集可以是空的。
?
無向邊(Edge)：若頂點V1到V2之間的邊沒有方向，則稱這條邊為無向邊。
無向圖(Undirected graphs)：圖中任意兩個頂點之間的邊都是無向邊。（A,D）=（D,A）
無向圖中邊的取值范圍：0≤e≤n(n-1)/2
有向邊：若從頂點V1到V2的邊有方向，則稱這條邊為有向邊，也稱弧(Arc)。用<V1,V2>表示，V1為狐尾(Tail)，V2為弧頭(Head)。（V1，V2）≠（V2，V1）。
有向圖(Directed graphs)：圖中任意兩個頂點之間的邊都是有向邊。
有向圖中弧的取值范圍：0≤e≤n(n-1)
???注意：無向邊用“（）”，而有向邊用“< >”表示。
?
簡單圖：圖中不存在頂點到其自身的邊，且同一條邊不重復出現。
無向完全圖：無向圖中，任意兩個頂點之間都存在邊。
有向完全圖：有向圖中，任意兩個頂點之間都存在方向互為相反的兩條弧。
稀疏圖：有很少條邊。
稠密圖：有很多條邊。
?
鄰接點：若 (v, v′) 是一條邊，則稱頂點 v 和 v′互為 鄰接點，或稱 v 和 v′相鄰接；稱邊 (v, v′) 依附于頂點 v 和 v′，或稱 (v, v′) 與頂點 v 和 v′ 相關聯。
?
權（Weight）：與圖的邊或弧相關的數。
網（Network）：帶權的圖。
子圖（Subgraph）：假設G=（V,{E}）和G‘=（V',{E'}），如果V'包含于V且E'包含于E，則稱G'為G的子圖。
?
?入度：有向圖中以頂點 v 為頭的弧的數目稱為 v 的入度，記為：ID(v)。 ?
出度：有向圖中以頂點 v 為尾的弧的數目稱為 v 的出度，記為：OD(v)。
度（Degree）：無向圖中，與頂點V相關聯的邊的數目。有向圖中，入度表示指向自己的邊的數目，出度表示指向其他邊的數目，該頂點的度等于入度與出度的和。
?
回路（環）：第一個頂點和最后一個頂點相同的路徑。
簡單路徑：序列中頂點（兩端點除外）不重復出現的路徑。?
簡單回路（簡單環）：前后兩端點相同的簡單路徑。
路徑的長度：一條路徑上邊或弧的數量。
?
連通：從頂點 v 到 v′ 有路徑，則說 v ?和 v′ 是連通的。
連通圖：圖中任意兩個頂點都是連通的。
連通分量：無向圖的極大連通子圖（不存在包含它的 更大的連通子圖）；
任何連通圖的連通分量只有一個，即其本身；非連通圖有多個連通分量（非連通圖的每一個連通部分）。
強連通圖： 任意兩個頂點都連通的有向圖。?
強連通分量：有向圖的極大強連通子圖；任何強連通 圖的強連通分量只有一個，即其本身；非強連通圖有多個 強連通分量。
?
生成樹：所有頂點均由邊連接在一起但不存在回路的圖。（n個頂點n-1條邊）
?
?
?
