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

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


七、图的常见操作


      图的基本操作,包括: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;

      }

}


上一篇:爱立信:5G将加速物联网发展


下一篇:grafana 开源图标系统 & InfluxDB 介绍。