C++ 图结构算法.doc

#include iostream #include stdlib.h #includewindows.h #define MAXNUM 20 #define MAXEDGE 65535 using namespace std; typedef struct { char VertexInfo; //顶点信息 int VertexSN; //顶点序号 int isTravel; //遍历标志 }TVertex; typedef struct{ int VertexSum; //顶点总数 TVertex Vertex[MAXNUM]; //顶点数组 int EdgeSum; //边总数 int EdgeValue[MAXNUM][MAXNUM]; //边权值 }TGraph; TVertex Vertex[5]={ //默认顶点数组 {a,0,0}, {b,1,0}, {c,2,0}, {d,3,0}, {e,4,0} }; int GM[5][5]={ //默认权值数组 {MAXEDGE,3,7,MAXEDGE,8}, {3,MAXEDGE,4,9,MAXEDGE}, {7,4,MAXEDGE,MAXEDGE,MAXEDGE}, {MAXEDGE,9,MAXEDGE,MAXEDGE,2}, {8,MAXEDGE,MAXEDGE,2,MAXEDGE} }; //以顶点信息查找顶点序号 int FindVertexNum(TGraph *myGraph,char Info){ for (int i=0;iMAXNUM;i++) { if (Info==myGraph-Vertex[i].VertexInfo) { return myGraph-Vertex[i].VertexSN; } } return -1;//未找到对应顶点 } //初始化图 void InitGraph(TGraph *myGraph){ cout要创建的图有多少个顶点?; cinmyGraph-VertexSum; cout要创建的图有多少条边?; cinmyGraph-EdgeSum; for (int i=0;imyGraph-VertexSum;i++) { myGraph-Vertex[i].isTravel=0; //设置各顶点均未遍历 for (int j=0;jmyGraph-VertexSum;j++) { myGraph-EdgeValue[i][j]=MAXEDGE; //设置图没有边权(以最大值表示) } } } //创建图 void CreateGraph(TGraph * myGraph){ char startPoint,endPoint; int edgeValue=-1; cout输入各顶点的信息,以空格分隔.\n; for(int i=0;imyGraph-VertexSum;i++){ cinmyGraph-Vertex[i].VertexInfo; myGraph-Vertex[i].VertexSN=i; } cout顶点\t值\n; for(int i=0;imyGraph-VertexSum;i++) { couti+1\tmyGraph-Vertex[i].VertexInfoendl; } cout输入顶点间的权值,格式:\t a b 10\n; for (int i=0;imyGraph-EdgeSum;i++) { cinstartPointendPointedgeValue; int startPos=FindVertexNum(myGraph,startPoint); int endPos=FindVertexNum(myGraph,endPoint); if (startPos!=-1endPos!=-1) { myGraph-EdgeValue[startPos][endPos]=edgeValue; myGraph-EdgeValue[endPos][startPos]=edgeValue; } } } //显示图 void ShowGraph(TGraph *myGraph){ for (int i=0;imyGraph-VertexSum;i++) { for (int j=0;jmyGraph-VertexSum;j++) { if (myGraph-EdgeValue[i][j]==MAXEDGE) { cou