题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。
七、图的常见操作
图的基本操作，包括：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; //链表图结构的指针
};
template<class vType, intsize>
graphType<vType,size>::graphType()
{
maxSize = size;
gSize = 0;
graph = new linkedListGraph<vType>[maxSize]; //构造结点数组链表...
}
template<class vType, intsize>
graphType<vType,size>::~graphType()
{
clearGraph(); //调用销毁操作
delete[] graph;
}
1.图判断空
template<class vType, intsize>
boolgraphType<vType,size>::isEmpty()
{
return (gSize == 0); //根据当前节点数是否为0判断是否空
}
2.创建图
//第一行代表图中结点个数;
//第二行代表对于每一个顶点的邻接点;
template<class vType, intsize>
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. 销毁操作，逐个节点调用对应的链表。
template<class vType, intsize>
voidgraphType<vType,size>::clearGraph()
{
int index;
for(index = 0; index < gSize; index++)
{
graph[index].destroyList(); //销毁链表...
}
gSize = 0;
}
4.打印图
template<class vType, intsize>
voidgraphType<vType,size>::printGraph() const
{
cout << "The Graph is shown as below: "<< endl;
int index;
for(index = 0; index < gSize; index++)
{
cout << index << "\t";
graph[index].print(); //打印每组链表
}
cout << endl;
}
5.图的深度优先遍历
区别于二叉树的特点，图中即可能存在环路，又可能无法从一个结点遍历整个图。
核心思路：1.从图中一个结点（自定义）开始访问，如果尚未访问，则访问它；2.然后对于邻接结点，用1同样的方法进行遍历。直到所有的结点都被遍历到。考虑：可以用递归实现。
以下是深度优先递归函数dft &深度优先遍历函数depthFirstTraversal的实现。
template<class vType, intsize>
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); //对邻接点进行递归操作
}
}
}
template<class vType, intsize>
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;
}
for(int index = 0; index < gSize; index++)
{
if(!visited[index])
{
dft(index,visited);
}
}
cout << endl;
delete []visited;
}
6. 图的广度优先遍历
核心思想：对于所有的结点，对每一个结点及其该结点的所有邻接结点遍历完以后；再遍历下一个尚未遍历的结点。
其遍历类似二叉树的层次遍历。由于对于每一个结点都要在遍历完一个结点后，再去遍历其所有的邻接节点。考虑用队列完成操作，先进先出。在进队的时候访问，如果队列非空，则完成出队，同时将其所有的邻接点依次进队。进队时访问，依次类推。
template<class vType, intsize>
voidgraphType<vType,size>::breadthFirstTraversal()
{
cout << "BreathFirstTraversal result is as below:";
bool *visited;
visited = new bool[gSize]; //定义结点访问标记数组,true已访问,false未访问。
vType *adjacencyList = new vType[gSize]; //用于存储邻接点
int nLength = 0; //out函数里会有值
linkedQueueType<vType> queue; //用于结点入队操作.
vType w; //弹出结点
//初始化标记数组
for(int index = 0; index < gSize; index++)
{
visited[index] = false;
}
for(int index = 0; index < gSize; index++)
{
if(!visited[index])
{
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
}
}
cout << endl;
delete []visited;
}
#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;
}
}
