1、實習報告題目：圖遍歷的演示編譯環境：Microsoft Visual Studio 2010功能實現：以鄰接表為存儲結構，演示在連通無向圖上訪問全部節點的操作；實現連通無向圖的深度優先遍歷和廣度優先遍歷；建立深度優先生成樹和廣度優先生成樹，按凹入表或樹形打印生成樹。一、 需求分析1. 以鄰接表為存儲結構，演示在連通無向圖上訪問全部節點的操作。該無向圖為一個交通網絡，共25個節點，30條邊，遍歷時需要以用戶指定的節點為起點，建立深度優先生成樹和廣度優先生成樹，再按凹入表或樹形打印生成樹。2. 程序的測試數據：graph.txt文件所表示的無向交通圖。二、 概要設計1. 主要數據結構設計：stru

2、ct ArcNode/邊表結點int vexIndex;/鄰接點域，即鄰接點在頂點表中的下標ArcNode* next;struct VertexNode/頂點表結點string vertex;/數據域ArcNode* firstArc;struct TNode/樹結點string data;struct TNode *fristchild, *nextchild;2. 鄰接表類設計：class GraphTraversepublic:VertexNode VexListMaxSize;/頂點表數組int vertexNumberber;/圖的頂點數int arcNumberber;/圖的邊數

3、bool HasCreated;/圖是否創建void ReadFile();/從文件讀取數據，并建立該圖void DisplayGraph();/以鄰接表顯示圖TNode* DFSForest(int);/建立深度優先生成樹void DFSTree(int, TNode*);/深度優先遍歷圖TNode* BFSForest(int);/建立廣度優先生成樹void BFSTree(int, TNode*);/廣度優先遍歷圖void PrintTree(TNode*, int);/按照凹入表方式打印樹;三、 詳細設計1. 主要操作函數的實現：(1) 建立深度優先生成樹函數：TNode* Graph

4、Traverse:DFSForest(int v)int i,j;TNode *p,*q,*DT;j=v;for(i=0;i<vertexNumberber;i+)Visitedi=0;for(i=0;i<vertexNumberber;i+)if(Visited(i+j)%vertexNumberber=0)p=new TNode;p->data=VexList(i+j)%vertexNumberber.vertex;p->fristchild=NULL;p->nextchild=NULL;DT=p;q=p;DFSTree(i+j)%vertexNumberbe

5、r),p);return DT;(2) 深度優先遍歷圖函數：void GraphTraverse:DFSTree(int v, TNode* DT)int j=0;int i=0;TNode *p,*q;int first=1;Visitedv=1;for(ArcNode *m=VexListv.firstArc;m;m=m->next)j=m->vexIndex;if(Visitedj=0)p=new TNode;p->data=VexListj.vertex;p->fristchild=NULL;p->nextchild=NULL;if(first)DT-&g

6、t;fristchild=p;first=0;elseq->nextchild=p;q=p;DFSTree(j,q);(3) 建立廣度優先生成樹函數：TNode* GraphTraverse:BFSForest(int v)int i,j;TNode *p,*q,*BT;BT=NULL;j=v;for(i=0;i<vertexNumberber;i+)Visitedi=0;for(i=0;i<vertexNumberber;i+)if(Visited(i+j)%vertexNumberber=0)p=new TNode;p->data=VexList(i+j)%vert

7、exNumberber.vertex;p->fristchild=NULL;p->nextchild=NULL;BT=p;q=p;BFSTree(i+j)%vertexNumberber),p);return BT;(4) 廣度優先遍歷圖函數：void GraphTraverse:BFSTree(int v,TNode*BT)int front=-1;int rear=-1;int j=0;int a,b;int first=1;a=b=0;TNode *m, *n, *r, *curMaxSize;r=BT;ArcNode *p;Visitedv=1;Query+rear=v;w

8、hile(front!=rear)first=1;v=Query+front;for(p=VexListv.firstArc;p;p=p->next)j=p->vexIndex;if(Visitedj=0)m=new TNode;m->data=VexListj.vertex;m->fristchild=NULL;m->nextchild=NULL;Visitedj=1;Query+rear=j;if(first)r->fristchild=m;first=0;elsen->nextchild=m;cura+=m;n=m;r=curb+;(5) 打印函

9、數：按照凹入表方式打印樹。void GraphTraverse:PrintTree(TNode *T,int i)int j;TNode *p;cout<<ends;for(j=1;j<=i;j+)cout<<ends<<ends;cout<<T->data<<endl;for(p=T->fristchild;p;p=p->nextchild)PrintTree(p,i+1);2. 主函數的實現：void main()string s1;int flag;TNode *DT,*BT;GraphTraverse

10、graphnet;string begin;int i;flag=atoi(s1.c_str(); while(flag>5|flag<1)cout<<"輸入錯誤，請重新輸入！"<<endl;cout<<endl<<"請輸入操作序號："cin>>s1;flag=atoi(s1.c_str(); while(flag!=5)switch(flag)case 1:graphnet.ReadFile();break;case 2:graphnet.DisplayGraph();break;

11、case 3:cout<<"請輸入遍歷起點："cin>>begin;for(i=0;i<graphnet.vertexNumberber;i+)if(graphnet.VexListi.vertex=begin)break;if(i=graphnet.vertexNumberber)cout<<"輸入的起點不存在！"<<endl;break;elseDT=graphnet.DFSForest(i);cout<<"深度優先遍歷結果如下（凹入表）："<<endl

12、;graphnet.PrintTree(DT,0);break;case 4:cout<<"請輸入遍歷起點："cin>>begin;for(i=0;i<graphnet.vertexNumberber;i+)if(graphnet.VexListi.vertex=begin)break;if(i=graphnet.vertexNumberber)cout<<"輸入的起點不存在！"<<endl;break;elseBT=graphnet.BFSForest(i);cout<<"廣度

13、優先遍歷結果如下（凹入表）："<<endl;graphnet.PrintTree(BT,0);break;flag=atoi(s1.c_str(); while(flag>5|flag<1)cout<<"輸入錯誤，請重新輸入！"<<endl;cout<<endl<<"請輸入操作序號："cin>>s1;flag=atoi(s1.c_str(); 四、 用戶手冊1. 本程序的執行文件為：GraphTraverse.exe2. 進入程序的用戶界面，并根據程序提示，輸入文件名及其路徑，讀取文件