当前位置: 代码迷 >> Web前端 >> 图的使用
  详细解决方案

图的使用

热度:248   发布时间:2012-11-08 08:48:11.0
图的应用

/*在程序设计中更多的是注重程序的逻辑性,因此在设计验证实验程序中,更多的是考虑程序完整性,
也就是在设计程序时有一个清晰地思路,经过认真的研究,对面向对象的程序设计语言的前提下,
对抽象数据类型的了解显得更为重要,在做实验之前更多的是要知道程序的功能,以便设计更为人性化
程序
*/
/*该实验采用邻接矩阵作为存储结构
首先建立以邻接矩阵为存储结构的图的抽象数据类型
方法的实现:对建立的无向图,进行深度及广度优先遍历,因此该实验主要是设计抽象数据类型,
并做好算法的实现与调用。
*/
/*生成树的求解:
生成树可以在图的遍历中得到:
在一个连通无向图G=(V,E)中,如果从任一个顶点开始进行深度优先遍历,必定将边集E分成两个集合T和B,其中T是遍历过程中经历的边的集合,
B是剩余的边的集合。显然,边集T和图G所有顶点一起构成连通图G的一棵生成树。因此,修改深度优先遍历算法,输出遍历所经过的边。
*/

#include<iostream.h>
const int MaxSize=10;
template<class T>
class MGraph
{
public:
?? MGraph(T a[],int n,int e);??? //构造函数
?? ~MGraph() {}???????????????? //析构函数
?? void DFSTraverse(int v);????? //深度优先遍历
?? void DFSTraverse1(int v);???? //深度优先非递归算法 ,这里的v代表数组元素的下标
?? void DFSTraverse2(int v);
?? void DFSTraverseSCH(int v);?? //生成树求解,利用深度优先遍历算法改进即可
?? void BFSTraverse(int v);????? //广度优先遍历
private:
?? T vertex[MaxSize];??????????? //存放图中顶点的数组
?? int arc[MaxSize][MaxSize];???? //存放图中边的数组,邻接存储的核心部分,其取值就是两个顶点之间有没有边相连
?? int vertexNum,arcNum;
?? int visited[MaxSize];
};
//构造函数
template<class T>
MGraph<T>::MGraph(T a[],int n,int e)
{
vertexNum=n; arcNum=e;
for(int i=0;i<vertexNum;i++)
?? vertex[i]=a[i];?????????? //初始化定点数组,将定点数组赋值
for(i=0;i<MaxSize;i++)
?? visited[i]=0;
for(i=0;i<vertexNum;i++)?????? //初始化邻接矩阵
?? for(int j=0;j<vertexNum;j++)
??? arc[i][j]=0;
for(int k=0;k<arcNum;k++)????? //程序在此处跳转的原因是,arcNum赋给的初值为零
{??
?? int i,j;
?? cout<<"请输入两位正整数:"<<endl;
?? cin>>i>>j;
?? arc[i][j]=1;
?? arc[j][i]=1;?????????????? //由于其为无向图邻接矩阵,矩阵关于对角线对称
}
}
template<class T>
void MGraph<T>::DFSTraverse(int v)??? //深度优先遍历递归算法
{
//int visited[MaxSize];?????????????? //visited[数组一定要初始化】,初始化问题是一个相当重要的问题,在下面的判断语句中,其显得尤为重要,不然的话程序将跳出循环,不向下执行
/*for(int i=0;i<MaxSize;i++)
?? visited1[i]=0;*/
cout<<vertex[v]<<" ";??????????????? //visited 数组不能再这里进行初始化,递归调用将使数组不断地初始化,陷入死循环
visited[v]=1;
?? for(int j=0;j<vertexNum;j++)
{ if(arc[v][j]==1&&visited[j]==0)
???? DFSTraverse(j);
}
}
template<class T>
void MGraph<T>::DFSTraverse1(int v)
{
int s[MaxSize];
int visited1[MaxSize];
for(int i=0;i<MaxSize;i++)
?? visited1[i]=0;
int top=-1;
cout<<vertex[v]<<" ";
visited1[v]=1;
s[++top]=v;?????????????? //利用栈的思想
while(top!=-1)
{
?? v=s[top];????????????? //初步调试是栈顶元素无法取出,v没有进栈
?? for(int j=0;j<vertexNum;j++)
??? if(arc[v][j]==1&&visited1[j]==0)
??? {
???? cout<<vertex[j]<<" ";
???? visited1[j]=1; //这里的visited1该函数中的visited独立与主函数中的visited数组
???? s[++top]=j;
???? //break;
??? }
??? if(j==vertexNum) top--;
}
}
/*在这个算法中我们需要注意的是:visited1数组的记录问题,由于在类中已经定义了一个visited数组,一定要区别两者,在编写程序运行无误后,并不等于我们就已经成功,我
要做的还要验证程序是否符合运算的结果,在调试程序的过程中,寻找到这种方法,我们才能在编写程序中寻找到乐趣。在非递归算法中一定要理解栈的概念,它能帮助你理解程序的逻辑性
在调试程序总起着至关重要的作用*/
template<class T>
void MGraph<T>::DFSTraverse2(int v)
{
int s[MaxSize];
int visited1[MaxSize];
for(int i=0;i<MaxSize;i++)
?? visited1[i]=0;
int top=-1;
cout<<vertex[v]<<" ";
visited1[v]=1;??????? //这里的visited1为正确,在以后的程序中其没有任何变化
s[++top]=v;?????????????? //利用栈的思想
while(top!=-1)
{
?? v=s[top];????????????? //初步调试是栈顶元素无法取出,v没有进栈; 问题的关键是让最开始的顶点出栈
?? for(int j=0;j<vertexNum;j++)
?? { if(arc[v][j]==1&&visited1[j]==0)
??? {
???? //cout<<vertex[j]<<" ";
???? cout<<"("<<v<<j<<")"<<" ";
???? visited1[j]=1; //这里的visited1该函数中的visited独立与主函数中的visited数组
???? s[++top]=j;
???? //break;
??? }
??? //if(j==vertexNum) top--;
?? }
??
?? if(top>0)????? //此函数设计是让栈顶元素无法出栈
?? {
??? cout<<vertex[s[top]]<<" ";
??? top--;
?? }
?? if(top==0)
??? top--;
}
}
template<class T>
void MGraph<T>::DFSTraverseSCH(int v)?? //由于此算法采用的visited数组同深度优先遍历算法是一样的,为避免发生两者的冲突,建立一一验证
{
visited[v]=1;
for(int j=0;j<vertexNum;j++)
?? if(arc[v][j]==1&&visited[j]==0)
?? {
??? cout<<"("<<v<<j<<")"<<" ";
??? DFSTraverseSCH(j);
?? }


}
/*
1,visited2数组初始化
2,重复下面的操作直到front==rear
??? 队头元素后移;
??? 以v存在未被访问的结点
???? 访问标志置1;
???? 队尾数组下标后移
*/
template<class T>
void MGraph<T>::BFSTraverse(int v)
{
int front,rear;
int visited2[MaxSize],q[MaxSize];
for(int i=0;i<MaxSize;i++)
?? visited2[i]=0;
front=rear=-1;
cout<<vertex[v]<<" ";
visited2[v]=1;
q[++rear]=v;
while(front!=rear)
{
?? v=q[++front];????????????????? //此种方法模拟出队,就是头数组下标后移
?? for(int j=0;j<vertexNum;j++)
??? if(arc[v][j]==1&&visited2[j]==0)
??? {
???? cout<<vertex[j]<<" ";
???? visited2[j]=1;
???? q[++rear]=j;
??? }
}
}

void main()
{
//char a[4]={"we","are","good","!"};??? 定义一个数组,其存储的是图中的结点元素,对于整数元素不需要将双引号,因为编译器会认为其为字符,引起编译错误
int a[4]={1,3,4,5};
int b[5]={1,2,3,4,5};
MGraph<int> g(a,4,4);??????? //对象的初始化,采用对象调用定义的构造函数,根据函数的重载,其会自动匹配定义的构造函数,而不是默认的构造函数,注意图的逻辑性,
//int a[5]={1,2,3,4,5,};
//MGraph<int> g(a,5,5);
//cout<<"深度优先遍历递归算法的结果为:";
??? //g.DFSTraverse(0);cout<<endl;
cout<<"深度优先非递归算法的结果为:";
g.DFSTraverse2(0);?? cout<<endl;
cout<<"深度优先算法2的结果为:";
g.DFSTraverse1(0);cout<<endl;
cout<<"广度优先遍历非递归算法:";
g.BFSTraverse(0); cout<<endl;
cout<<"深度优先遍历生成树为:";
g.DFSTraverseSCH(0);
MGraph<int> G(b,5,5);
cout<<"深度优先遍历递归算法的结果为:";
G.DFSTraverse(0);cout<<endl;
G.DFSTraverse2(0);cout<<endl;?????????????? //示例数据组合

}

  相关解决方案