一、廣度優先搜索(BFS)
①找到與一個頂點相鄰的所有頂點
②標記哪些頂點被訪問過
③需要一個輔助隊列
#define MaxVertexNum 100
bool visited[MaxVertexNum]; //訪問標記數組
void BFSTraverse(Graph G){ //對圖進行廣度優先遍歷，處理非連通圖的函數 for(int i=0;i<G.vexnum;i++)// 遍歷一下所有的 頂點visited[i] = false; // 將所有的頂點都 設為 未訪問標志。InitQueue(Q); //初始化輔助隊列Q for(int i=0;i<G.vexnum;i++)// 從0號頂點開始遍歷if(!visited[i]) // 對每個連通分量調用一次BFS() BFS(G,i);
}
void BFS(Graph G,int v){visit(v);visited[V]=true; //對v做已訪問標記 EnQueue(Q,v); //頂點v入隊 while(isEmpty(Q)){Dequeue(Q,v); //隊首頂點v出隊 //for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))for(p=G.vertices[v].firstarc;p;p=p->nextarc){ //檢測v的所有鄰接點 w=p->adjvex;if(visited[w]==false){visit(w); //w為v尚未訪問的鄰接點，訪問w visited[w]=true; // 對w做已訪問標記 EnQueue(Q,w); // 頂點w入隊 } }}
}
無論是鄰接矩陣還是鄰接表的存儲方式，BFS算法都需要借助一個輔助隊列Q，
n個頂點均需要入隊一次，在最壞的情況下，空間復雜度為O(|V|)
BFS遍歷圖的實質就是對每個頂點查找其鄰接點的過程，耗費時取決于存儲結構。
1、采用鄰接表存儲，每個頂點均需搜索（或入隊）一次，時間復雜度為O(|V|),在搜索每個頂點的鄰接點時
每條邊至少被訪問一次，時間復雜度為O(|E|),總的時間復雜度為 O(|V|+|E|)
2、采用鄰接矩陣存儲，查找每個頂點的鄰接點所需要的時間為O(|V|),總的時間復雜度為O(|V|2)?
同一個圖的鄰接矩陣存儲是唯一的，所以其廣度優先生成樹也是唯一的。
但因為鄰接表存儲表示不唯一，所以其廣度優先生成樹也是不唯一。?
廣度優先搜索的應用——只可以檢測無向圖是否有環，有向圖無法檢測
二、深度優先搜索(DFS)
DFS算法是一個遞歸算法，需要借助一個遞歸工作棧，最好的空間復雜度是O(1),最差的空間復雜度是O(|V|)
DFS遍歷圖的實質就是對每個頂點查找其鄰接點的過程，耗費時取決于存儲結構。
1、采用鄰接表存儲，每個頂點均需搜索（或入隊）一次，時間復雜度為O(|V|),在搜索每個頂點的鄰接點時
每條邊至少被訪問一次，時間復雜度為O(|E|),總的時間復雜度為 O(|V|+|E|)
2、采用鄰接矩陣存儲，查找每個頂點的鄰接點所需要的時間為O(|V|),總的時間復雜度為O(|V|2) ?
#define MAX_VERTEX_NUM 100
bool visited[MAX_VERTEX_NUM]; //訪問標記數組
void DFSTraverse(Graph G) //對圖進行深度優先遍歷
{for(v=0;v<G.vexnum;i++)visited[v]=false; //初始化已訪問標記數組 for(v=0;v<G.vexnum;i++) //本代碼是從v0開始遍歷 if(!visited[v]) //對尚未訪問的頂點調用DFS() DFS(G,v);
}//用鄰接表實現深度優先搜索算法
void DFS(ALGraph G,int v)
{visit(v); visited[v]=true;for(p=G.vertices[v].firstarc;p;p=p->nextarc){ //檢測v的所有鄰接點 j=p->adjvex;if(!visited[w])DFS(G,w); //j為v的尚未訪問鄰接點，遞歸訪問v }}//用鄰接矩陣實現深度優先搜索算法
void DFS(MLGraph G,int v)
{visit(v); visited[v]=true;for(j=0;j<G.vexnum;j++){ //檢測v的所有鄰接點 if(visited[j]==false && G.edge[i][j]==1)DFS(G,j); //j為v的尚未訪問鄰接點，遞歸訪問v }}
深度優先搜索應用——檢測是否有向圖/無向圖是否有環
比如，無向圖，先訪問結點1，再訪問結點2，再訪問結點5，再訪問結點3，此時結點3有兩個鄰接點，在先訪問結點2的情況下，發現結點2已經被訪問過，并且不是結點3的父節點，結點3的父節點是它的來時路——結點5。則此時，圖里存在環。
?三、圖的遍歷與連通性
1、對于無向圖來說，若無向圖是連通的，則從任意一個結點出發，僅需一次遍歷就能訪問圖中所有頂點；若無向圖是非連通的，則從某一個頂點出發，一次性只能訪問到該頂點所在連通分量的所有頂點?
2、對于無向圖，BFSTraverse、 DFSTraverse這兩個函數調用BFS、DFS的次數等于該圖的連通分量?
3、對于有向圖來說，若從初始頂點到圖中的每個頂點都有路徑，則能夠訪問到圖中的所有頂點，否則不能訪問到所有頂點。（即與是否為強連通圖無關）
4、對于有向圖，非強連通分量一次調用不一定能訪問到該子圖的所有頂點。?
)
)
)
