图论在实际生活中的应用(2)

MGraph G;

int Locatevex(MGraph G,char v)//图的基本操作，寻找V的位置 { int i=0; while(i

int CreateUDG(MGraph &G) //数组邻接矩阵表示法构造无向图 { char v1,v2; int weight; cout<<\请输入图的顶点数和边的条数\ cin>>G.vexnum>>G.arcnum; cout<<\请输入顶点的名称(0--9)\ for(int i=0;i>G.vexs[i];

for(int q=0;q>v1>>v2>>weight; int a=Locatevex(G,v1); int b=Locatevex(G,v2); G.arcs[a][b]=weight; G.arcs[b][a]=G.arcs[a][b]; } cout<<\该图的邻接矩阵表示为：\\n\for(int n=0;n

cout<

void Minway(MGraph G,bool *visited,char vexs,int Long,char vb,string path) //递归求取所有顶点a到顶点i的路径 { if(vexs==vb) { path=path+\ allPath.push_back(path); all.push_back(Long); cout<<\路径:\ 长度:\ } else { path=path+\ int i=Locatevex(G,vexs); visited[i]=true; for(int j=0;j

void CountMinway(MGraph G) //该函数调用递归部分实现递归 { char va,vb; string path; cout<<\请输入您所处的位置:\ cin>>va;

cout<<\请输入您想到达的位置:\ cin>>vb; cout<

int i=Locatevex(G,va); bool visited[100]; for(int j=0;j

int Long=0; path+=va; for( j=0;j

void Minway()//输出最短路径 { int min=10000; for(int i=0;i

void main() { CreateUDG(G); //建图 CountMinway(G); //找出所有路径 Minway(); //输出最短路径 }

程序描述：通过输入顶点的个数、边的条数和名称以及两点之间的权值得到一个带权值的矩阵。再输入你所处的位置和你要到的位置，程序将通过Floyd算法给出可以到达的路径，并给出最优的路径（即权值最小的路径）。

输入图的顶点个数和边的条数，并输入顶点的名称如图3所示。

图3 数据输入图

输入边的权值，输入格式为边的起点名称 终点名称 和权值，如图4所示。

图4 权值的输入

程序自动生成并输出图的邻接矩阵如图5所示。

图5 图的邻接矩阵

输入所在的位置和想要去的位置，程序给出可以到达的所以路径及其权值，并给出最短的路径及其权值如图6所示。

图6 输出结果

总结

图论其实是一门应用数学，它的概念和结果来源非常广泛，既有来自生产实践的问题，也有来自理论研究的问题。它具有以下特点：蕴含了丰富的思想、漂亮的图形和巧妙的证明；涉及的问题多且广泛，问题外表简单朴素，本质上却十分复杂深刻；解决问题的方法千变万化。非常灵活，常常是一种问题一种解法。图论研究的内容非常广泛，如图的连通性、遍历性、图的计数、图的着色、图的极值问题、图的可平面性等。

在实际生活中，图论是有很大的利用价值的，应用的范围也很广泛。在教材《图论及其算法》中就介绍了图论在实际生活中各方面的应用，例如解决中国投递员问题，解决旅行推销员问题，解决七桥问题等。

有的时候通过人工计算和处理图论问题很费时费力而且准确性无法保证，所以我们需要将问题抽象出来再进行分析，通过计算机编程实现，在经过调试和修改实现所需要的功能。通过计算机可以快速的处理问题并准确地给出答案。

参考文献：

[1]殷剑宏、吴亚开.图论及其算法[M].合肥:中国科学技术大学出版社,2005 [2]严蔚敏.数据结构（c语言版）[M].北京:清华大学出版社,2009