算法：深度優先算法和廣度優先算法
1.寫在前面
圖的存儲結構有兩種：一種是基于二維數組的鄰接矩陣表示法。
另一種是基于鏈表的的鄰接表。
在鄰接矩陣中，可以如下表示頂點和邊連接關系：
說明：
將頂點對應為下標，根據橫縱坐標將矩陣中的某一位置值設為1，表示兩個頂點向聯接。
圖示表示的是 無向圖的鄰接矩陣 ，從中我們可以發現它們的 分布關于斜對角線對稱 。
我們在下面將要討論的是下圖的兩種遍歷方法（基于矩陣的）：
我們已經說明了我們要用到的是鄰接矩陣表示法，那么我首先要來構造圖：
矩陣圖的數據結構如下表示：
#define MaxVnum 50
typedef double AdjMatrix[MaxVnum][MaxVnum]; //表示一個矩陣，用來存儲頂點和邊連接關系
typedef struct {
int vexnum,arcnum; //頂點的個數，邊的個數
AdjMatrix arcs; //圖的鄰接矩陣
}Graph;
這樣我們可以首先來創建上述圖，為了方便，我們直接在代碼中書寫矩陣，而不用每次調試手動輸入了
void CreateGraph(Graph &G)
{
G.vexnum=8;
G.arcnum=9;
G.arcs[0][1]=1;
G.arcs[0][2]=1;
G.arcs[1][3]=1;
G.arcs[1][4]=1;
G.arcs[2][5]=1;
G.arcs[2][6]=1;
G.arcs[3][1]=1;
G.arcs[3][7]=1;
G.arcs[3][6]=1;
G.arcs[4][1]=1;
G.arcs[4][7]=1;
G.arcs[5][2]=1;
G.arcs[5][6]=1;
G.arcs[5][5]=1;
G.arcs[6][2]=1;
G.arcs[6][5]=1;
G.arcs[7][3]=1;
G.arcs[7][4]=1;
}
這樣我們就已經完成了準備工作，我們可以正式來學習我們的兩種遍歷方式了。
2.深度優先遍歷算法
分析深度優先遍歷
從圖的某個頂點出發， 訪問圖中的所有頂點 ， 且使每個頂點僅被訪問一次 。這一過程叫做圖的遍歷。
深度優先搜索的思想：
①訪問頂點v；
②依次從v的未被訪問的鄰接點出發，對圖進行深度優先遍歷；直至圖中和v有路徑相通的頂點都被訪問；
③若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發，重新進行深度優先遍歷，直到圖中所有頂點均被訪問過為止。
比如：
在這里為了區分已經訪問過的節點和沒有訪問過的節點，我們引入一個一維數組 bool visited[MaxVnum] 用來表示與下標對應的頂點是否被訪問過，
流程：
? 首先輸出 V1，標記V1的flag=true;
? 獲得V1的鄰接邊 [V2 V3],取出V2，標記V2的flag=true;
? 獲得V2的鄰接邊[V1 V4 V5],過濾掉已經flag的，取出V4，標記V4的flag=true;
? 獲得V4的鄰接邊[V2 V8],過濾掉已經flag的，取出V8，標記V8的flag=true;
? 獲得V8的鄰接邊[V4 V5],過濾掉已經flag的，取出V5，標記V5的flag=true;
? 此時發現V5的所有鄰接邊都已經被flag了，所以需要回溯。（左邊黑色虛線，回溯到V1，回溯就是下層遞歸結束往回返）
? 
? 回溯到V1，在前面取出的是V2，現在取出V3，標記V3的flag=true;
? 獲得V3的鄰接邊[V1 V6 V7]，過濾掉已經flag的,取出V6，標記V6的flag=true;
? 獲得V6的鄰接邊[V3 V7],過濾掉已經flag的,取出V7，標記V7的flag=true;
? 此時發現V7的所有鄰接邊都已經被flag了，所以需要回溯。（右邊黑色虛線，回溯到V1，回溯就是下層遞歸結束往回返）
深度優先搜索的代碼
bool visited[MaxVnum];
void DFS(Graph G,int v)
{
visited[v]= true; //從V開始訪問，flag它
printf("%d",v); //打印出V
for(int j=0;j<G.vexnum;j++)
if(G.arcs[v][j]==1&&visited[j]== false) //這里可以獲得V未訪問過的鄰接點
DFS(G,j); //遞歸調用，如果所有節點都被訪問過，就回溯，而不再調用這里的DFS
}
void DFSTraverse(Graph G) {
for (int v = 0; v < G.vexnum; v++)
visited[v] = false; //剛開始都沒有被訪問過
for (int v = 0; v < G.vexnum; ++v)
if (visited[v] == false) //從沒有訪問過的第一個元素來遍歷圖
DFS(G, v);
}
</code></pre>
3.廣度優先搜索算法
分析廣度優先遍歷
所謂廣度，就是 一層一層的，向下遍歷，層層堵截 ，還是這幅圖，我們如果要是廣度優先遍歷的話，我們的結果是V1 V2 V3 V4 V5 V6 V7 V8。
廣度優先搜索的思想：
① 訪問頂點vi ；
② 訪問vi 的所有未被訪問的鄰接點w1 ,w2 , …wk ；
③ 依次從這些鄰接點（在步驟②中訪問的頂點）出發，訪問它們的所有未被訪問的鄰接點; 依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；
說明：
為實現③，需要保存在步驟②中訪問的頂點，而且訪問這些頂點的鄰接點的順序為：先保存的頂點，其鄰接點先被訪問。 這里我們就想到了用標準模板庫中的queue隊列來實現這種先進現出的服務。
老規矩我們還是走一邊流程：
說明：
?將V1加入隊列，取出V1，并標記為true(即已經訪問)，將其鄰接點加進入隊列，則 <—[V2 V3]
?取出V2，并標記為true(即已經訪問)，將其未訪問過的鄰接點加進入隊列，則 <—[V3 V4 V5]
?取出V3，并標記為true(即已經訪問)，將其未訪問過的鄰接點加進入隊列，則 <—[V4 V5 V6 V7]
?取出V4，并標記為true(即已經訪問)，將其未訪問過的鄰接點加進入隊列，則 <—[V5 V6 V7 V8]
?取出V5，并標記為true(即已經訪問)，因為其鄰接點已經加入隊列，則 <—[V6 V7 V8]
?取出V6，并標記為true(即已經訪問)，將其未訪問過的鄰接點加進入隊列，則 <—[V7 V8]
?取出V7，并標記為true(即已經訪問)，將其未訪問過的鄰接點加進入隊列，則 <—[V8]
?取出V8，并標記為true(即已經訪問)，將其未訪問過的鄰接點加進入隊列，則 <—[]
廣度優先搜索的代碼
#include <queue>
using namespace std;
....
void BFSTraverse(Graph G)
{
for (int v=0;v<G.vexnum;v++) //先將其所有頂點都設為未訪問狀態
visited[v]=false;
queue<int> Q;
for(int v=0;v<G.vexnum;v++)
{
if(visited[v]==false) //若該點沒有訪問
{
Q.push(v); //將其加入到隊列中
visited[v]=true;
while (!Q.empty()) //只要隊列不空，遍歷就沒有結束
{
int t =Q.front(); //取出對頭元素
Q.pop();
printf(" %d ",t+1);
for(int j=0;j<G.vexnum;j++) //將其未訪問過的鄰接點加進入隊列
if(G.arcs[t][j]==1&&visited[j]== false)
{
Q.push(j);
visited[j]=true; //在這里要設置true，因為這里該頂點我們已經加入到了隊列，為了防止重復加入！
}
}
}
}
}
兩種算法的復雜度分析
深度優先
數組表示：查找所有頂點的所有鄰接點所需時間為O(n 2 )，n為頂點數，算法時間復雜度為O(n 2 )
廣度優先
數組表示：查找每個頂點的鄰接點所需時間為O(n 2 )，n為頂點數，算法的時間復雜度為O(n 2 )
來自：http://www.cnblogs.com/MrSaver/p/6241721.html