最短路径与最小生成树.doc

数 据 结 构实验报告 姓 名： 邱金梁 班 级： rJBJava101 学 号： 201007092137指导老师： 杨 关 时 间： 2012年6月13日一 、最小生成树#include/头文件using namespace std;#define MAX_VERTEX_NUM 20/最大结点数#define MAX 200typedef struct Close/结构体char adjvex;int lowcost;Close,closeMAX_VERTEX_NUM;typedef struct ArcNodeint adjvex;ArcNode *nextarc;int info;ArcNode;typedef struct VNodechar data;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList verties;int vexnum,arcnum;ALGraph;ALGraph G;/对象Gint LocateVek(ALGraph ,char );/返回结点位置int minimum(close);/返回最小数void MinSpanTree_PRIM(ALGraph,char);/最小生成树void Create(ALGraph &);/创建邻接表int main()char a;int i=1;Create(G);/*for(int i=1;inextarc)coutG.vertiesi.data-adjvex.data=infoendl;*/while(i)couta;MinSpanTree_PRIM(G,a);couti;return 0;int LocateVek(ALGraph G,char u)int i;for(i=1;i=G.vexnum;i+)if(u=G.vertiesi.data)return i;return -1;int minimum(close m)/返回最小数int i=0,j,n=200;for(i=1;i=G.vexnum;i+)if(mi.lowcostn&mi.lowcost!=0)n=mi.lowcost;j=i;return j;void MinSpanTree_PRIM(ALGraph G,char u)int j,k,a;close closedge;ArcNode *s,*p,*q;for(j=1;j=MAX_VERTEX_NUM;j+)closedgej.lowcost=MAX;/把所有值都赋为最大k=LocateVek(G,u);for(j=1;jnextarc)if(j=s-adjvex)closedgej.lowcost=s-info;break;closedgek.lowcost=0;cout最小生成树 : ;/查找并输出最小生成树for(j=1;jG.vexnum;j+)k=minimum(closedge);cout(closedgek.adjvex,G.vertiesk.data);closedgek.lowcost=0;for(int i=1;inextarc)if(p-infoadjvex)closedgei.adjvex=G.vertiesk.data;closedgei.lowcost=p-info;coutendl;cout边及对应权值: =1;j-)if(closedgej.lowcost=0&G.vertiesj.data!=u)cout(closedgej.adjvex,G.vertiesj.datanextarc)if(a-64=q-adjvex)coutinfoendl;void Create(ALGraph &G)int i,j,k,x;char a,b;ArcNode *s;coutG.vexnum;coutG.arcnum;cout输入顶点信息:endl;for(i=1;iG.vertiesi.data;G.vertiesi.firstarc=NULL;for(i=1;i=G.arcnum;i+)coutab;cinx;j=a-64;k=b-64;/将字符型转化成整数型s=new ArcNode;s-info=x;s-adjvex=k;s-nextarc=G.vertiesj.firstarc;G.vertiesj.firstarc=s;s=new ArcNode;s-info=x;s-adjvex=j;s-nextarc=G.vertiesk.firstarc;G.vertiesk.firstarc=s;二、最短路径#include#include#include#includeusing namespace std;enum Mark UNVISITED,VISITED;typedef struct DocuNode int n; Mark m; DocuNode;typedef struct Docu int n; DocuNode * Node; int* edge; Docu;Mark getMark(Docu*D , int i) return D-Nodei.m;void setMark(Docu*D,int v,Mark m) D-Nodev.m=m;int first(Docu*D , int v) int i; for(i=0 ; in ; i+) if(D-edgevi)!=-1) return i; return i;int next(Docu*D , int v , int w) int i; for(i=w+1 ; in ; i+) if(D-edgevi)!=-1) return i; return i;int weight(Docu*D,int v,int w) return D-edgevw;int minVertex(Docu*D , int *B) int i , v; for(i=0; in; i+) if(getMark(D,i)=UNVISITED) v=i; break; for(i+; in; i+) if(getMark(D,i)=UNVISITED&(BiBv)&Bi!=-1)|(Bv=-1) v=i; return v;void Dijkstra(Docu*D , int *B , int s) int i,v,w; for(i=0; in; i+) v=minVertex(D,B); if(Bv=-1) return; setMark(D,v,VISITED); for(w=first(D,v); wn; w=next(D,v,w) if(Bw(Bv+weight(D,v,w)|(Bw=-1) Bw=Bv+weight(D,v,w); int main() Docu* D; ifstream fin(Docu.txt); int i , j; D=(Docu*)malloc(sizeof(Docu); finD-n;/从文件中读取节点数 D-Node=(DocuNode*)malloc(sizeof(DocuNode); for(i=0 ; in ; i+) D-Nodei.m=UNVISITED; /将所有节点设为未被访问的 D-edge=(int*)calloc(1,sizeof(int*)*D-n); if(!D-edge) /若内存未分配成功 couterror; for(i=0 ; in ; i+) D-edgei=(int*)calloc(1,sizeof(int)*D-n); if(!D-edgei) /若内存未分配成功 couterror; for(i=0 ; in ; i+) for(j=0 ; jn ; j+) finD-edgeij; /从文件中读取边