数据结构面试之七——图的常见操作

题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。

七、图的常见操作

图的基本操作，包括：1.创建一个图，2.判断图是否为空，3.图的打印，4.图的遍历…..

其中对于1，创建一个图，需要考虑图的存储结构，存储结构分为：邻接矩阵存储（数组），邻接表存储（数组链表）。而对于四，也是图的核心操作，主要分为：图的深度优先遍历（逐个结点递归），图的广度优先遍历（类似层次遍历）。

此外，图的扩展操作：求最小生成树（Prim算法，kruskal算法），求最短路径的—ijstra算法，kruskal算法）等下一节会详细介绍。

//下面实例中图采用邻接表的存储结构.

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;       }}