图论在实际生活中的应用

来，从而形成一个无向图。再根据实际情况：不同地点的距离问题；路的畅通与否等给相应的边赋上权值，最后得出一个赋权图，如图2：

图2 赋权图

2.2 Floyd算法用C++实现

#include #include #include using namespace std;

#define MAX_VEX_NUM 10

vector allPath; //向量，用来存放所有的顶点a到顶点i的路径 vector all; //向量，用来存放对应路径的长度 struct MGraph { char vexs[MAX_VEX_NUM];

int arcs[MAX_VEX_NUM][MAX_VEX_NUM]; int vexnum,arcnum; };

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所示。