題注：《面試寶典》有相關習題，但思路相對不清晰，排版有錯誤，作者對此參考相關書籍和自己觀點進行了重寫，供大家參考。
七、圖的常見操作
圖的基本操作，包括：1.建立一個圖，2.判斷圖是否為空，3.圖的列印，4.圖的周遊…..
其中對于1，建立一個圖，需要考慮圖的存儲結構，存儲結構分為：鄰接矩陣存儲（數組），鄰接表存儲（數組連結清單）。而對于四，也是圖的核心操作，主要分為：圖的深度優先周遊（逐個結點遞歸），圖的廣度優先周遊（類似層次周遊）。
此外，圖的擴充操作：求最小生成樹（Prim算法，kruskal算法），求最短路徑的（Dijstra算法，kruskal算法）等下一節會詳細介紹。
//下面執行個體中圖采用鄰接表的存儲結構.
template<class vType, intsize>
class graphType : publiclinkedListGraph<vType>
{
public:
graphType();
~graphType();
bool isEmpty();
void createGraph();
void clearGraph();
void printGraph() const;
void depthFirstTraversal(); //深度優先周遊
void dft(vType v, bool *visited); //深度優先遞歸函數
void breadthFirstTraversal(); //廣度優先周遊
protected:
int maxSize; //最大結點數
int gSize; //目前結點數[輸入後便知道]
linkedListGraph<vType>* graph; //連結清單圖結構的指針
};
graphType<vType,size>::graphType()
maxSize = size;
gSize = 0;
graph = new linkedListGraph<vType>[maxSize]; //構造結點數組連結清單...
}
graphType<vType,size>::~graphType()
clearGraph(); //調用銷毀操作
delete[] graph;
1.圖判斷空
boolgraphType<vType,size>::isEmpty()
return (gSize == 0); //根據目前節點數是否為0判斷是否空
2.建立圖
//第一行代表圖中結點個數;
//第二行代表對于每一個頂點的鄰接點;
voidgraphType<vType,size>::createGraph()
cout << "Input the nums of Vertex: ";
cin >> gSize;
cout << endl;
vType adjacentVertex;
cout << "Input the adjacent Vertex of every Vertex:(-999 End)" << endl;
for( int index=0; index < gSize; ++index)
{
cout << "Input line " << index<< ": ";
while(cin >> adjacentVertex, adjacentVertex !=-999) //-999作為結束符
{
graph[index].insertLast(adjacentVertex);
}//end while
}//end for
3. 銷毀操作，逐個節點調用對應的連結清單。
voidgraphType<vType,size>::clearGraph()
int index;
for(index = 0; index < gSize; index++)
graph[index].destroyList(); //銷毀連結清單...
}
4.列印圖
voidgraphType<vType,size>::printGraph() const
cout << "The Graph is shown as below: "<< endl;
cout << index << "\t";
graph[index].print(); //列印每組連結清單
5.圖的深度優先周遊
差別于二叉樹的特點，圖中即可能存在環路，又可能無法從一個結點周遊整個圖。
核心思路：1.從圖中一個結點（自定義）開始通路，如果尚未通路，則通路它；2.然後對于鄰接結點，用1同樣的方法進行周遊。直到所有的結點都被周遊到。考慮：可以用遞歸實作。
以下是深度優先遞歸函數dft &深度優先周遊函數depthFirstTraversal的實作。
void graphType<vType,size>::dft(vType v,bool *visited)
visited[v] = true;
cout << v << "\t";
vType *adjacencyList = new vType[gSize]; //用于存儲鄰接點
int nLength = 0; //out函數裡會有值
//找v結點的鄰接點.
graph[v].getAdjacentVertices(adjacencyList,nLength);
//判斷鄰接點是否已經周遊
for(int i = 0; i < nLength; i++)
if(!visited[adjacencyList[i]])
dft(adjacencyList[i],visited); //對鄰接點進行遞歸操作
}
void graphType<vType,size>::depthFirstTraversal()
cout << "DepthFirstTraversal result is as below:";
bool *visited;
visited = new bool[gSize]; //定義結點通路标記數組,true已通路,false未通路。
//初始化标記數組
for(int index = 0; index < gSize; index++)
visited[index] = false;
if(!visited[index])
dft(index,visited);
delete []visited;
6. 圖的廣度優先周遊
核心思想：對于所有的結點，對每一個結點及其該結點的所有鄰接結點周遊完以後；再周遊下一個尚未周遊的結點。
其周遊類似二叉樹的層次周遊。由于對于每一個結點都要在周遊完一個結點後，再去周遊其所有的鄰接節點。考慮用隊列完成操作，先進先出。在進隊的時候通路，如果隊列非空，則完成出隊，同時将其所有的鄰接點依次進隊。進隊時通路，依次類推。
voidgraphType<vType,size>::breadthFirstTraversal()
cout << "BreathFirstTraversal result is as below:";
linkedQueueType<vType> queue; //用于結點入隊操作.
vType w; //彈出結點
queue.addQueue(index);
visited[index] = true;
cout << index << "\t"; //通路
//找v結點的鄰接點.
while(!queue.isEmptyQueue())
{
queue.dequeue(w);
graph[w].getAdjacentVertices(adjacencyList,nLength);
//判斷鄰接點是否已經周遊
for(int i = 0; i < nLength; i++)
{
if(!visited[adjacencyList[i]])
{
queue.addQueue(adjacencyList[i]); //!此處注意，易落下。
visited[adjacencyList[i]] =true;
cout <<adjacencyList[i] << "\t";
}//end if
}//end for
}//end while
#endif
7. 擷取鄰接結點，并将結點放入數組中。
//length記錄數組長度。LinkedListGraph 派生自 LinkedList（連結清單部分已講）。
template<class vType>
voidlinkedListGraph<vType>::getAdjacentVertices(vType adjacencyList[],int& length)
nodeType<vType> *current;
length = 0;
current = first;
while(current != NULL)
adjacencyList[length++] = current->info; //将連結清單的元素存入數組.
current = current->link;
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)