轉載自：http://blog.csdn.net/gamer_gyt/article/details/51498546
一：圖的分類
1：無向圖
即兩個頂點之間沒有明确的指向關系，隻有一條邊相連，例如，A頂點和B頂點之間可以表示為 <A, B> 也可以表示為<B, A>，如下所示
2：有向圖
頂點之間是有方向性的，例如A和B頂點之間，A指向了B，B也指向了A，兩者是不同的，如果給邊賦予權重，那麼這種異同便更加顯著了
=================================================================================================
在次基礎上，根據圖的連通關系可以分為
無向完全圖：在無向圖的基礎上，每兩個頂點之間都存在一條邊，一個包含N個頂點的無向完全圖，其總邊數為N（N-1）/2
有向完全圖：在有向圖的基礎上，每兩個頂點之間都存在一條邊，一個包含N個頂點的有向完全圖，其總邊數為N（N-1）
連通圖：針對無向圖而言的，如果任意兩個頂點之間是連通的，則該無向圖稱為連通圖
非連通圖：無向圖中，存在兩個頂點之間是不連通的，則該無向圖稱為非連通圖
強連通圖：針對有向圖而言的，如果有向圖中任意兩個頂點之間是連通的（注意方向問題，A—>B，成立，但B—>A不一定成立），則該有向圖稱為強連通圖
非強連通圖：如果有向圖中存在兩個頂點之間是不連通的，則該有向圖稱為非強連通圖
二：圖的存儲結構
1：鄰接矩陣
使用二維數組來存儲圖的邊的資訊和權重，如下圖所示的4個頂點的無向圖
從上面可以看出，無向圖的邊數組是一個對稱矩陣。所謂對稱矩陣就是n階矩陣的元滿足aij = aji。即從矩陣的左上角到右下角的主對角線為軸，右上角的元和左下角相對應的元全都是相等的。
如果換成有向圖，則如圖所示的五個頂點的有向圖的鄰接矩陣表示如下
2：鄰接表
鄰接矩陣是一種不錯的圖存儲結構，但是對于邊數相對較少的圖，這種結構存在空間上的極大浪費，是以找到一種數組與連結清單相結合的存儲方法稱為鄰接表。
鄰接表的處理方法是這樣的：
（1）圖中頂點用一個一維數組存儲，當然，頂點也可以用單連結清單來存儲，不過，數組可以較容易的讀取頂點的資訊，更加友善。
（2）圖中每個頂點vi的所有鄰接點構成一個線性表，由于鄰接點的個數不定，是以，用單連結清單存儲，無向圖稱為頂點vi的邊表，有向圖則稱為頂點vi作為弧尾的出邊表
如下為無向圖的鄰接表表示：
從圖中可以看出，頂點表的各個結點由data和firstedge兩個域表示，data是資料域，存儲頂點的資訊，firstedge是指針域，指向邊表的第一個結點，即此頂點的第一個鄰接點。邊表結點由adjvex和next兩個域組成。adjvex是鄰接點域，存儲某頂點的鄰接點在頂點表中的下标，next則存儲指向邊表中下一個結點的指針。
有向圖的鄰接表表示：
3：十字連結清單
對于鄰接表來說，計算頂點的入度是不友善的，那麼有沒有一種存儲方式能夠輕松的計算頂點的入度和出度呢，答案是肯定的
在十字連結清單中重新定義了節點的結構：
firstin表示入邊表頭指針，指向該頂點的入邊表中第一個結點，firstout表示出邊表頭指針，指向該頂點的出邊表中的第一個結點
重新定義的邊表結構為：
其中，tailvex是指弧起點在頂點表的下表，headvex是指弧終點在頂點表的下标，headlink是指入邊表指針域，指向終點相同的下一條邊，taillink是指邊表指針域，指向起點相同的下一條邊。如果是網，還可以增加一個weight域來存儲權值。
比如下圖，頂點依然是存入一個一維數組，實線箭頭指針的圖示完全與鄰接表相同。就以頂點v0來說，firstout指向的是出邊表中的第一個結點v3。是以，v0邊表結點hearvex = 3，而tailvex其實就是目前頂點v0的下标0，由于v0隻有一個出邊頂點，所有headlink和taillink都是空的。
重點需要解釋虛線箭頭的含義。它其實就是此圖的逆鄰接表的表示。對于v0來說，它有兩個頂點v1和v2的入邊。是以的firstin指向頂點v1的邊表結點中headvex為0的結點，如上圖圓圈1。接着由入邊結點的headlink指向下一個入邊頂點v2，如上圖圓圈2。對于頂點v1，它有一個入邊頂點v2，是以它的firstin指向頂點v2的邊表結點中headvex為1的結點，如上圖圓圈3。
十字連結清單的好處就是因為把鄰接表和逆鄰接表整合在一起，這樣既容易找到以v為尾的弧，也容易找到以v為頭的弧，因而比較容易求得頂點的出度和入度。
而且除了結構複雜一點外，其實建立圖算法的時間複雜度是和鄰接表相同的，是以，在有向圖應用中，十字連結清單是非常好的資料結構模型。
這裡就介紹以上三種存儲結構，除了第三種存儲結構外，其他的兩種存儲結構比較簡單
三：圖的周遊
1：深度優先周遊（DFS）
它從圖中某個結點v出發，通路此頂點，然後從v的未被通路的鄰接點出發深度優先周遊圖，直至圖中所有和v有路徑相通的頂點都被通路到。若圖中尚有頂點未被通路，則另選圖中一個未曾被通路的頂點作起始點，重複上述過程，直至圖中的所有頂點都被通路到為止。
基本實作思想：
（1）通路頂點v；
（2）從v的未被通路的鄰接點中選取一個頂點w，從w出發進行深度優先周遊；
（3）重複上述兩步，直至圖中所有和v有路徑相通的頂點都被通路到。
遞歸實作
（1）通路頂點v；visited[v]=1；//算法執行前visited[n]=0
（2）w=頂點v的第一個鄰接點；
（3）while（w存在）
if（w未被通路）
從頂點w出發遞歸執行該算法；
w=頂點v的下一個鄰接點；
非遞歸實作
（1）棧S初始化；visited[n]=0；
（2）通路頂點v；visited[v]=1；頂點v入棧S
（3）while(棧S非空)
x=棧S的頂元素(不出棧)；
if(存在并找到未被通路的x的鄰接點w)
通路w；visited[w]=1；
w進棧;
else
x出棧；
2：廣度優先周遊（BFS）
它是一個分層搜尋的過程和二叉樹的層次周遊十分相似，它也需要一個隊列以保持周遊過的頂點順序，以便按出隊的順序再去通路這些頂點的鄰接頂點。
基本實作思想：
（1）頂點v入隊列。
（2）當隊列非空時則繼續執行，否則算法結束。
（3）出隊列取得隊頭頂點v；通路頂點v并标記頂點v已被通路。
（4）查找頂點v的第一個鄰接頂點col。
（5）若v的鄰接頂點col未被通路過的，則col入隊列。
（6）繼續查找頂點v的另一個新的鄰接頂點col，轉到步驟（5）。
直到頂點v的所有未被通路過的鄰接點處理完。轉到步驟（2）。
廣度優先周遊圖是以頂點v為起始點，由近至遠，依次通路和v有路徑相通而且路徑長度為1，2，……的頂點。為了使“先被通路頂點的鄰接點”先于“後被通路頂點的鄰接點”被通路，需設定隊列存儲通路的頂點。
僞代碼
（1）初始化隊列Q；visited[n]=0；
（2）通路頂點v；visited[v]=1；頂點v入隊列Q；
（3） while（隊列Q非空）
v=隊列Q的對頭元素出隊；
w=頂點v的第一個鄰接點；
while（w存在）
如果w未通路，則通路頂點w；
visited[w]=1；
頂點w入隊列Q；
w=頂點v的下一個鄰接點。
四：舉例說明
package com.hbut.test;
import java.util.Scanner;
/**
* Created by HP on 2017/6/4.
*/
/*
* 定義圖的結構
*/
class Graph {
static final int MaxNum=20; //最大節點數目
static final int MaxValue=65535;
char[] Vertex = new char[MaxNum]; //定義數組，儲存頂點資訊
int GType; //圖的類型0：無向圖 1：有向圖
int VertxNum; //頂點的數量
int EdgeNum; //邊的數量
int[][] EdgeWeight = new int[MaxNum][MaxNum]; //定義矩陣儲存頂點邊的資訊
int[] isTrav = new int[MaxNum]; //周遊标志
}
public class GraphTest {
/**
* @param args
* Author：thinkgamer
*/
static Scanner scan = new Scanner(System.in);
//建立鄰接矩陣圖
static void createGraph(Graph g){
int i , j , k;
int weight; //權
char EstartV, EndV; //邊的起始頂點
System.out.println("輸入圖中各頂點的資訊");
for(i=0; i < g.VertxNum; i ++)
{
System.out.println("第" + (i+1) + "個頂點");
g.Vertex[i] = (scan.next().toCharArray() )[0];
}
System.out.println("輸入構成各個邊的頂點和權值");
for(k=0;k<g.EdgeNum;k++)
{
System.out.println("第" + (k+1) + "條邊：");
EstartV = scan.next().charAt(0); //起始點
EndV = scan.next().charAt(0); //終點
weight = scan.nextInt(); //權值
for(i=0; EstartV!=g.Vertex[i] ; i++); //在已有頂點中查找開始節點
for(j=0; EndV != g.Vertex[j]; j++); //在已有節點上查找終結點
g.EdgeWeight[i][j] = weight; //對應位置儲存權重，表示有一條邊
if(g.GType == 0) //如果是無向圖，在對角位置儲存權重
g.EdgeWeight[j][i] = weight;
}
}
//清空圖
static void clearGraph(Graph g){
int i,j;
for(i=0; i< g.VertxNum; i++)
for(j =0; j<g.VertxNum; j++)
g.EdgeWeight[i][j] = Graph.MaxValue; //設定矩陣中各元素的值為MaxValue
}
//輸出鄰接矩陣
static void OutGraph(Graph g){
int i,j;
System.out.print("圖的頂點資訊：");
for(j = 0; j < g.VertxNum;j ++)
System.out.print("\t" + g.Vertex[j]); //在第一行輸入頂點資訊
System.out.println();
for(i =0 ;i <g.VertxNum; i ++)
{
System.out.print( g.Vertex[i]);
for(j = 0;j < g.VertxNum; j++)
{
if(g.EdgeWeight[i][j] == Graph.MaxValue) //若權值為最大值
System.out.print("\tZ"); //Z 表示無窮大
else
System.out.print("\t" + g.EdgeWeight[i][j]); //輸出邊的權重
}
System.out.println();
}
}
//周遊圖
static void DeepTraOne(Graph g,int n){//從第n個節點開始周遊
int i;
g.isTrav[n] = 1; //标記為1表示該頂點已經被處理過
System.out.println("—>" + g.Vertex[n]); //輸出節點資料
//周遊鄰接矩陣中第n個節點的直接連通關系
for(i = 0; i< g.VertxNum; i++)
{
if(g.EdgeWeight[n][i] != g.MaxValue && g.isTrav[i] == 0)//目标節點與目前節點連通，并且該節點沒有被通路過
{
DeepTraOne(g, i); //遞歸進行周遊
}
}
}
//深度優先周遊
static void DeepTraGraph(Graph g){
int i;
for(i = 0; i< g.VertxNum; i++)
{
g.isTrav[i]= 0;
}
System.out.println("深度優先周遊：");
// 從沒有被周遊的節點開始深度周遊
for(i = 0; i< g.VertxNum ; i++)
{
if(g.isTrav[i] == 0)
DeepTraOne(g,i);// 若是連通圖，隻會執行一次
}
System.out.println();
}
public static void main(String[] args) {
Graph g = new Graph();
System.out.println("輸出生成圖的類型：");
g.GType = scan.nextInt(); //圖的種類
System.out.println("輸入圖的頂點數量：");
g.VertxNum = scan.nextInt();
System.out.println("輸入圖的邊數量：");
g.EdgeNum = scan.nextInt();
clearGraph(g); //清空圖
createGraph(g); //生成鄰接表結構的圖
System.out.println("該圖的鄰接矩陣資料如下：");
OutGraph(g); //輸出圖
DeepTraGraph(g); //深度優先周遊圖
}
} 運作測試結果：
有向圖測試結果（無向圖類似，隻是在輸入生成圖類型時輸入0）