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

题注

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

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

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

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

//下面实例中图采用邻接表的存储结构.template<class vType, intsize>class graphType : public edListGraph<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;                  //当前结点数[输入后便知道]        edListGraph<vType>* graph; //链表图结构的指针}; template<class vType, intsize>graphType<vType,size>::graphType(){       maxSize = size;       gSize = 0;       graph = new  edListGraph<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 << "	";              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 << "	";        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函数里会有值         edQueueType<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 << "	";  //访问                      //找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] << "	";                                   }//end if                            }//end for                     }//end while                 }       }       cout << endl;       delete []visited;}#endif

7. 获取邻接结点，并将结点放入数组中。

//length记录数组长度。 edListGraph 派生自  edList（链表部分已讲）。template<class vType>void edListGraph<vType>::getAdjacentVertices(vType adjacencyList[],int& length){       nodeType<vType> *current;       length = 0;       current = first;        while(current != NULL)       {              adjacencyList[length++] = current->info; //将链表的元素存入数组.              current = current-> ;       }}

作者：铭毅天下
来源：CSDN
原文：https://blog.csdn.net/laoyang360/article/details/7897685
版权声明：本文为博主原创文章，转载请附上博文链接！