无向图的深度优先生成树

《无向图的深度优先生成树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、用邻接表存储的无向图的深度优先生成树，树结点用孩子兄弟结构保存。下面是代码viewplain1.#include2.#include3.usingnamespacestd;4.5.#defineMAX_VERTEX_NUM206.boolvisited[20];//用于遍历时辅助使用7.boolsearched[20];//用于建树时辅助使用8.9.//循环队列模版10.template11.classMy_queue;12.13.template14.cla

2、ssNode15.{16.private:17.Tdata;18.Node*next;19.public:20.Node()21.{22.next=0;23.}24.Node(Td)25.{26.data=d;27.next=0;28.}29.friendMy_queue;30.};31.32.template33.classMy_queue34.{35.private:36.Node*tail;37.public:38.My_queue()39.{40.tail=newNode();4

3、1.tail->next=tail;42.}43.44.boolempty()45.{46.return(tail->next==tail);47.}48.49.voidpush(Td)50.{51.Node*p=newNode(d);52.p->next=tail->next;53.tail->next=p;54.tail=p;55.}56.57.Tfront()58.{59.if(empty())60.{61.cout<<"queueisempty!"<

4、T>*p=tail->next;65.Tdata=p->next->data;66.returndata;67.}68.69.voidpop()70.{71.Node*p=tail->next;72.Node*q=p->next;73.p->next=q->next;74.if(q==tail)75.tail=p;76.deleteq;77.}78.};79.80.classALGraph;81.classCS_Tree;82.//树结点83.classCSnode84.{85.stringdata;86.CSno

5、de*firstchild;87.CSnode*nextsibling;88.friendclassCS_Tree;89.friendclassALGraph;90.};91.92.//树类定义93.classCS_Tree94.{95.public:96.voidPreRoot_Traverse(CSnode*T)//先根遍历97.{98.if(T)99.{100.cout<data<<"";101.PreRoot_Traverse(T->firstchild);102.PreRoot_Traverse(T->nex

6、tsibling);103.}104.}105.106.voidPostRoot_Traverse(CSnode*T)//后根遍历107.{108.if(T)109.{110.PostRoot_Traverse(T->firstchild);111.cout<data<<"";112.PostRoot_Traverse(T->nextsibling);113.}114.}115.116.voidLevelOrder_Traverse(CSnode*T)//层次遍历117.{118.My_queueq;

7、119.CSnode*t;120.q.push(T);121.do122.{123.t=q.front();124.do125.{126.cout<data<<"";127.if(t->firstchild)128.q.push(t->firstchild);129.t=t->nextsibling;130.}while(t);131.q.pop();132.}while(!q.empty());133.}134.};135.136.classVNode;137.//表结点138.classArcNode139.{14

8、0.public:141.intadjvex;142.ArcNode*nextarc;143.friendclassVNode;144.};145.146.classALGraph;147.//头结点148.classVNode149.{150.stringdata;151.