数据结构_图遍历的演示

实习报告

题目：图遍历的演示

编译环境：Microsoft Visual Studio 2010

功能实现：以邻接表为存储结构，演示在连通无向图上访问全部节点的操作；

实现连通无向图的深度优先遍历和广度优先遍历；

建立深度优先生成树和广度优先生成树，按凹入表或树形打印生成树。

一、 需求分析

1. 以邻接表为存储结构，演示在连通无向图上访问全部节点的操作。该无向图为

一个交通网络，共25个节点，30条边，遍历时需要以用户指定的节点为起点，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。 2. 程序的测试数据：graph.txt文件所表示的无向交通图。

二、 概要设计

1. 主要数据结构设计：

struct ArcNode //边表结点 { int vexIndex; //邻接点域，即邻接点在顶点表中的下标 ArcNode* next; };

struct VertexNode //顶点表结点 { string vertex; //数据域 ArcNode* firstArc; };

struct TNode //树结点 { string data; struct TNode *fristchild, *nextchild; }; 2. 邻接表类设计：

class GraphTraverse {

public:

};

VertexNode VexList[MaxSize]; int vertexNumberber; int arcNumberber; 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* GraphTraverse::DFSForest(int v) { int i,j; TNode *p,*q,*DT; j=v; for(i=0;idata=VexList[(i+j)%vertexNumberber].vertex; p->fristchild=NULL; p->nextchild=NULL; DT=p; q=p; DFSTree(((i+j)%vertexNumberber),p); } } return DT; } (2) 深度优先遍历图函数：

void GraphTraverse::DFSTree(int v, TNode* DT) { int j=0; int i=0; TNode *p,*q; int first=1; Visited[v]=1; for(ArcNode *m=VexList[v].firstArc;m;m=m->next) { j=m->vexIndex; if(Visited[j]==0) { p=new TNode; p->data=VexList[j].vertex; p->fristchild=NULL; p->nextchild=NULL; if(first) { DT->fristchild=p; first=0; } else q->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

}

p->data=VexList[(i+j)%vertexNumberber].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, *cur[MaxSize]; r=BT; ArcNode *p; Visited[v]=1; Query[++rear]=v; while(front!=rear) { first=1; v=Query[++front]; for(p=VexList[v].firstArc;p;p=p->next) { j=p->vexIndex; if(Visited[j]==0) { m=new TNode; m->data=VexList[j].vertex; m->fristchild=NULL; m->nextchild=NULL; Visited[j]=1; Query[++rear]=j; if(first) { r->fristchild=m; first=0; }

}

}

else n->nextchild=m; cur[a++]=m; n=m; } }

r=cur[b++];

(5) 打印函数：按照凹入表方式打印树。

void GraphTraverse::PrintTree(TNode *T,int i) { int j; TNode *p; cout<data<fristchild;p;p=p->nextchild) PrintTree(p,i+1); } 2. 主函数的实现：

void main()

{ string s1; int flag; TNode *DT,*BT; GraphTraverse graphnet; string begin; int i; flag=atoi(s1.c_str()); while(flag>5||flag<1) { cout<<\输入错误，请重新输入！\ cout<>s1; flag=atoi(s1.c_str()); } while(flag!=5) { switch(flag)