题注:《面试宝典》有相关习题,但思路相对不清晰,排版有错误,作者对此参考相关书籍和自己观点进行了重写,供大家参考。
七、图的常见操作
图的基本操作,包括: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;
}
}