数控专业毕业论文 数控轴类零件加工工艺毕业设计.doc

数据结构论文 
最短路径
1 题目:
创建一个具有n(n≥1)个顶点的无向图的邻接矩阵,并对其按照“深度优先搜索”和“广度优先搜索”方法进行遍历。
2 目标:
。
、边数以及边的关系,并自动生成邻接矩阵。
。
。
3 设计思想:
考虑用一个n维数组来存放无向图,若两个结点之间有边,则n维数组对应下标的那个元素值为1,否则为0;
在输入图的顶点数和边数时我充分考虑了边界条件,[0,MAXV]范围内,边数在[0,*(-1)/2]范围内,在这个范围内,程序继续向下执行,否则返回重新输入;
输出邻接矩阵的实质是输出 n维数组,我用两重循环来实现;
深度优先遍历我采用迪杰特斯拉算法,不过要在此算法中间加一个判断,所有的结点是否都已经遍历过,如果是就退出,如果不是,则按顺序从序号小的开始向大的寻找,找到一个没有遍历过的结点继续调用深度优先遍历算法;
广度优先遍历我采用了非递归算法,其实质和深度优先遍历算法相同;
在主函数中直接调用CreatGraph(G), DispMatrix(G) ,DepthDisp(G,v) ,WidthDisp(G)函数即可。
4 算法描述:
step1:设置无向图最多的顶点数// 这个设置为了更好的输出邻接矩阵;
step2: 定义无向图的数据结构;
step3:实现生成无向图函数CreatGraph(G)
输入顶点数n,判断它是否在允许的范围内,不在则返回重新输入;
,判断它是否在允许的范围内,不在则返回重新输入;
输入边,for语句(k=1 to ){ 输入两顶点v,w,判断v!=w & 0<v<=Gverxnum & 0<w<=Gverxnum ,如果是在n维数组中第v行第w列和第w行第v列元素都为1,否则返回重新输入;
step4:实现输出邻接矩阵函数 DispMatrix(Graph &G) , 双重for循环实现输出无向图的邻接矩阵;
step5:实现深度优先遍历的递归算法函数DepthDisp(Graph &G,int v)
从v开始遍历,设置计数器num=0 ,并置顶点v已访问;
for语句(i=1 to )判断 [v][i]!=0&&visited[i]==0,如果是递归调用深度优先遍历的递归算法函数DepthDisp(G, i),如果不是则退出;
用for和if 语句判断是否所有的顶点都已经遍历完,
if num<
for (i=1 to )
if (visited[i]==1) i++
如果不是,则继续调用深度优先遍历的递归算法函数 DepthDisp(G,i);
step6:实现广度优先遍历的非递归算法函数 WidthDisp(Graph &G)
输入广度优先遍历的出发点m ,判断0<m< ,如果不是,则返回重新输入;
for ( i=1 to )
{判断第i个顶点与第m之间是否有边,有边则输出,k++,判断k=,等于,则退出,遍历完毕,不等于,转到与m有边的顶点继续遍历,要是有边的都已经遍历过,继续找一个没有遍历的顶点,继续;}
step7: 主函数直接调用CreatGraph(G), DispMatrix(G) ,DepthDisp(G,v) ,WidthDisp(G)函数即可;
5 程序流程图:
1. 创建无向图函数的流程图如下:
:
3. 实现广度优先遍历的流程图如下:
6 源程序
//二,不带权值的无向图的遍历:
#include<>
#define MAXV 20 //定义顶点的最大个数
struct Graph // 定义无向图的数据结构
{ int vexs[MAXV];
int arcs[MAXV][ MAXV];
int vexnum, um;
};
static int visited[MAXV];
void CreatGraph(Graph &G) // 实现创建无向图的函数
{ int i, j, k, v, w;
cout<<"请输入顶点数:";
cin>>;
while(> MAXV)
{ cout<<"图的顶点数超限,请重新输入:"; //纠错功能
cin>>; }
cout<<"请输入边数:";
cin>>G