// crikal.cpp : 定义控制台应用程序的入口点。 // #include "iostream" #include "vector" #include "stack" #include <fstream> using namespace std; #define MaxNumVertex 20 //最大顶点数 #define MaxNumEdge 40 //最大边数 #define infinity 65535//无穷大 typedef int elementtype; //elementtype 为int 型 //结点类型 struct ArcNode { elementtype data;//顶点信息 int weight ; //权重 ArcNode *nextarc ;//指向下一条弧 }; //表头 struct VNode { elementtype data;//顶点信息 ArcNode *firstarc;//指向第一条弧 }; typedef struct VNode AdjList[MaxNumVertex]; class graph{ public: graph(); ~graph(); elementtype insertvertex(elementtype v); //在图中增加一个顶点 elementtype insertedge(elementtype v,elementtype u,elementtype weight);//在图中增加一条从v顶点到u顶点的弧 elementtype firstadj(elementtype v);//求图g中顶点v的第一个邻接点 elementtype nextadj(elementtype v,elementtype m);//求图中顶点v的m邻接点之后的邻接点 elementtype firstpre(elementtype v);//求图中顶点v的第一个前驱 elementtype nextpre(elementtype v,elementtype m);//求图中顶点v的m前驱点之后的前驱点 elementtype degreein(elementtype v);//求图中顶点v的入度数 elementtype FindDegreein(elementtype ind[]);//各顶点的入度存放于入度数组中 elementtype degreeout(elementtype v);//求图中顶点v的入度数 elementtype FindDegreeout(elementtype oud[]);//各顶点的入度存放于入度数组中 elementtype EW(elementtype E[]);//最早发生时间的求解 bool CriticalPath();//关键路径 elementtype create();//创建图 int CurrentVertex;//当前顶点数 void show(); elementtype Getedge(elementtype v,elementtype u);//在图中获得v顶点到u顶点的权重 private: AdjList vertices; elementtype vertex[MaxNumVertex];//顶点表 elementtype edge[MaxNumVertex][MaxNumVertex];//图中弧的类型 }; /* *初始化 */ graph::graph() { CurrentVertex = 0; } /* *在图中增加一个顶点 */ elementtype graph::insertvertex(elementtype v) { //判断这个顶点是否已经存在 int i; bool flags = true; for(i=0;i<CurrentVertex;i++) { if(vertices[i].data==v) { flags = false ; break; } } if(flags) { vertices[CurrentVertex].data = v ; vertices[CurrentVertex].firstarc= NULL; CurrentVertex++; }else cout<<v<<"顶点已经存在!"<<endl; return 0; } /* *在图中增加一条从v顶点到u顶点的弧 */ elementtype graph::insertedge(elementtype v,elementtype u,elementtype weight) { int i ; ArcNode *s = new ArcNode; s->data = u; s->weight = weight; for( i = 0 ; i < CurrentVertex ; i ++ ) { if(vertices[i].data==v)//找到顶点v对应的表头 { ArcNode *p = new ArcNode; ArcNode *q = new ArcNode; p = vertices[i].firstarc ; bool flags = true; if(p==NULL) { //cout<<"Yes "; s->nextarc = p; vertices[i].firstarc = s ; // cout<<vertices[i].data<<","<<vertices[i].firstarc->data<<","<<vertices[i].firstarc->weight<<endl; }else { while(p!=NULL) { if(p->data!=u) { q = p; p = p->nextarc; }else{ flags = false; break; } } if(flags) { s->nextarc = q->nextarc; q->nextarc = s; }else cout<<v<<"->"<<u<<"这条弧弧已经存在!"<<endl; } } } return 0; } /* *求图中顶点v的第一个邻接点 */ elementtype graph::firstadj(elementtype v) { int i; elementtype u = 0; for(i=0;i<CurrentVertex;i++) { if(vertices[i].data==v)//找到顶点v对应的表头 { ArcNode *p = new ArcNode; p = vertices[i].firstarc ; if(p) { u = p->data; }else { break; } } } return u; } /* *求图中顶点v的m邻接点以后的邻接点 */ elementtype graph::nextadj(elementtype v,elementtype m) { int i; elementtype u = 0; for(i=0;i<CurrentVertex;i++) { if(vertices[i].data==v)//找到顶点v对应的表头 { ArcNode *p = new ArcNode; p = vertices[i].firstarc ; while(p) { if(p->data!=m) { p = p ->nextarc ; }else break; } if(p&&p->data==m&&p->nextarc) u = p->nextarc->data ; break; } } return u; } /* *求图中顶点v的第一个前驱 */ elementtype graph::firstpre(elementtype v) { int i; elementtype u = 0; bool flags = false; for(i=0;i<CurrentVertex;i++) { ArcNode *p = new ArcNode; p = vertices[i].firstarc ; while(p) { //cout<<p->data; if(p->data==v) { u = vertices[i].data; flags = true; break; } p = p ->nextarc; } if(flags)break; } return u; } /* *求图中顶点v的m前驱点之后的前驱点 */ elementtype graph::nextpre(elementtype v,elementtype m) { int i,j; elementtype u = 0; bool flags = false; for(i=0;i<CurrentVertex;i++) { if(vertices[i].data==m) { ArcNode *p = new ArcNode; for(j=i+1;j<CurrentVertex;j++) { p = vertices[j].firstarc ; while(p) { if(p->data==v) { u = vertices[j].data; flags = true; break; } p = p ->nextarc; } if(flags)break; } break; } } return u; } /* *求图中顶点v的入度数 */ elementtype graph::degreein(elementtype v) { int i,num = 0; for(i=0;i<CurrentVertex;i++) { ArcNode *p = new ArcNode; p = vertices[i].firstarc ; while(p) { if(p->data==v) { num++; break; } p = p ->nextarc; } } return num; } /* *每个顶点的入度 */ elementtype graph::FindDegreein(elementtype ind[]) { int i; for(i=0;i<CurrentVertex;i++) { ind[vertices[i].data] = degreein(vertices[i].data); } return 0; } /* *求图中顶点v的出度数 */ elementtype graph::degreeout(elementtype v) { int i,num = 0; for(i=0;i<CurrentVertex;i++) { if(vertices[i].data==v) { ArcNode *p = new ArcNode; p = vertices[i].firstarc ; while(p) { num++; p = p ->nextarc; } break; } } return num; } /* *每个顶点的出度 */ elementtype graph::FindDegreeout(elementtype outd[]) { int i; for(i=0;i<CurrentVertex;i++) { outd[vertices[i].data] = degreeout(vertices[i].data); } return 0; } /* *在图中获得v顶点到u顶点的权重 */ elementtype graph::Getedge(elementtype v,elementtype u) { int i; int weight = 0; for(i=0;i<CurrentVertex;i++) { if(vertices[i].data==v) { ArcNode *p = new ArcNode; p = vertices[i].firstarc ; while(p) { if(p->data==u) { weight =p->weight; break; } p = p ->nextarc; } break; } } return weight; } void graph::show() { int i; elementtype m; cout<<"test"<<endl; for( i = 0 ; i < CurrentVertex ; i ++ ) { ArcNode *p = new ArcNode; p = vertices[i].firstarc ; cout<<"表头:"<<vertices[i].data<<endl; while(p!=NULL) { cout<<p->data<<","<<p->weight<<endl; p = p->nextarc; } } cout<<"第一个邻接点:"<<endl; for( i = 0 ; i < CurrentVertex ; i ++ )cout<<vertices[i].data<<","<<firstadj(vertices[i].data)<<endl; cout<<endl; cout<<"第2个邻接点:"<<endl; for( i = 0 ; i < CurrentVertex ; i ++ ) { cout<<vertices[i].data<<":"; m = firstadj(vertices[i].data) ; while(m) { m = nextadj(vertices[i].data,m); cout<<m<<","; } cout<<endl; } cout<<endl; for( i = 0 ; i < CurrentVertex ; i ++ )cout<<"第一个前驱点:"<<vertices[i].data<<","<<firstpre(vertices[i].data)<<endl; //cout<<"第一个前驱点:"<<vertices[CurrentVertex-1].data<<endl; //cout<<firstpre(vertices[CurrentVertex-1].data)<<endl; for( i = 0 ; i < CurrentVertex ; i ++ ) { cout<<"第2个前驱:"<<vertices[i].data<<":"; m = firstpre(vertices[i].data) ; while(m) { m = nextpre(vertices[i].data,m); cout<<m<<","; } cout<<endl; } cout<<endl; for( i = 0 ; i < CurrentVertex ; i ++ )cout<<"入度数目:"<<vertices[i].data<<","<<degreein(vertices[i].data)<<endl; elementtype ind[MaxNumVertex];//求各顶点的入度存放于入度数组ind中 FindDegreein(ind);// for( i = 0 ; i < CurrentVertex ; i ++ )cout<<"入度数目:"<<ind[vertices[i].data]<<endl; for( i = 0 ; i < CurrentVertex ; i ++ )cout<<"出度数目:"<<vertices[i].data<<","<<degreeout(vertices[i].data)<<endl; elementtype outd[MaxNumVertex];//求各顶点的出度存放于出度数组outd中 FindDegreeout(outd);//求各个结点的出度 for( i = 0 ; i < CurrentVertex ; i ++ )cout<<"出度数目:"<<vertices[i].data<<","<<outd[vertices[i].data]<<endl; cout<<Getedge(vertices[CurrentVertex-2].data,vertices[CurrentVertex-1].data)<<endl; } /* *最早发生时间的求解 */ elementtype graph::EW(elementtype E[]) { int i; stack<elementtype> s;//定义并初始索要用到的栈 elementtype x,w,ind[MaxNumVertex];//求各顶点的入度存放于入度数组ind中 FindDegreein(ind); for(i=0;i<CurrentVertex;i++)//各个结点最早发生时间的初始化 { E[vertices[i].data] = -1; } for(i=0;i<CurrentVertex;i++)//将入度为0的顶点入栈 { if(degreein(vertices[i].data)==0) { s.push(vertices[i].data); E[vertices[i].data] = 0;//第一个入度为0的结点的最早发生时间为0 } } int count =0;//用于统计已经完成的结点数目 while(!s.empty()) { x = s.top(); count++;//计数 s.pop(); w = firstadj(x);//开始对v的各个后继顶点的入度-1 while(w!=0) { if(E[w]<(E[x]+Getedge(x,w))) { E[w] = E[x]+Getedge(x,w);//更新w的最早发生时间 } if(!(--ind[w]))//若w的入度-1后为0，则入栈 { s.push(w); } w = nextadj(x,w); } } for(i=0;i<CurrentVertex;i++)//各个结点最早发生时间的初始化 { cout<<E[vertices[i].data]<<endl; } if(count<CurrentVertex)return false;//产生有回路的标志 else return true; return 0; } /* *关键路径 */ bool graph::CriticalPath() { int i; stack<int> s;//定义并初始索要用到的栈 elementtype x,w,ind[MaxNumVertex];//求各顶点的入度存放于入度数组ind中 elementtype outd[MaxNumVertex];//求各顶点的出度存放于出度数组outd中 elementtype E[MaxNumVertex]; elementtype L[MaxNumVertex]; FindDegreein(ind);//求各个结点的入度 FindDegreeout(outd);//求各个结点的出度 EW(E);//求各个结点的最早发生时间 for(i=0;i<CurrentVertex;i++) { L[vertices[i].data] = infinity;//各个结点最迟发生时间的初始化 } for(i=0;i<CurrentVertex;i++)//将出度为0的顶点入栈 { if(degreeout(vertices[i].data)==0) { s.push(vertices[i].data); L[vertices[i].data] = E[vertices[i].data];//第一个出度为0的结点的最迟发生时间 } } int count =0;//用于统计已经完成的结点数目 while(!s.empty()) { x = s.top(); count++;//计数 s.pop(); w = firstpre(x);//开始对v的各个前驱顶点的出度-1 while(w!=0) { if(L[w]>(L[x]-Getedge(w,x))) { L[w] = L[x]-Getedge(w,x);//更新w结点的最迟发生时间 } if(!(--outd[w]))//若w的出度-1后为0，则入栈 { s.push(w); } w = nextpre(x,w); } } cout<<"E[i],L[i]:"<<endl; for(i=0;i<CurrentVertex;i++)//输出各个节点的最早发生时间和最迟发生时间 { cout<<"E["<<i<<"]="<<E[vertices[i].data]<<",L["<<i<<"]="<<L[vertices[i].data]<<endl; } vector<elementtype>equal;//记录E[I]=L[I] for(i=0;i<CurrentVertex;i++) { if(E[vertices[i].data]==L[vertices[i].data]) { equal.push_back(vertices[i].data); } } elementtype start,end; for(i=0;i<CurrentVertex;i++)//寻找起始结点 { if(degreein(vertices[i].data)==0) { start = vertices[i].data; break; } } FindDegreeout(outd);//求各个结点的出度 for(i=CurrentVertex-1;i>=0;i--)//寻找终止结点 { if(degreeout(vertices[i].data)==0) { end = vertices[i].data; break; } } cout<<"CriticalPath is:"; while(start!=end) { for(i=0;i<equal.size();i++)//输出关键路径 { if(Getedge(start,equal[i])!=0) { cout<<start<<"->"; start = equal[i]; if(start==end) { cout<<start<<endl; } break; } } } return 0; } /* *创建图 */ elementtype graph::create() { int i,VertextNum,ArcNum,v,u,weight; ifstream infile("file.txt",ios::in); if(!infile) { cerr<<"open error!"<<endl; exit(1); } infile>>VertextNum>>ArcNum; for( i = 0 ; i < VertextNum ; i ++ ) { infile>>v; insertvertex(v); } for( i = 0 ; i < ArcNum ; i ++ ) { infile>>v>>u>>weight; insertedge(v,u,weight); } infile.close(); cout<<"graph create finish！"<<endl<<endl; return 0; } graph::~graph() { } int main() { graph g; g.create(); g.show(); g.CriticalPath(); return 0; }