The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

张宏数据结构作业之-AOE网关键路径(Activity On Edge)

 

#include<iostream>
#include
<cmath>
#include
<algorithm>
#include
<stack>
#include
<fstream>
using namespace std;
#define MAX 100000

struct node
{
    
int v;
    
int w;
    node 
*next;
}
;

node adj[MAX];
node reversed_adj[MAX];
int indegree[MAX];
int ve[MAX];
int vl[MAX];

void initial(int n)
{
    
int i;
    
for(i=1;i<=n;i++)
    
{
        adj[i].v
=i;
        adj[i].w
=-1;
        reversed_adj[i].v
=i;
        reversed_adj[i].w
=-1;
        adj[i].next
=NULL;
        reversed_adj[i].next
=NULL;
    }

}


void findindegree(node adj[],int n)
{
    
int i;
    
for(i=1;i<=n;i++)
        indegree[i]
=0;
    
for(i=1;i<=n;i++)
    
{
        node 
*p=adj[i].next;
        
while(p!=NULL)
        
{
            indegree[p
->v]++;
            p
=p->next;
        }

    }

}



void creat(node adj[],node reversed_adj[],int n)
{
    fstream file(
"test.txt");
    
int i;
    cout
<<"您将建立一个具有"<<n<<"个顶点的邻接表,请依次输入边和权值,并以0 0 0结束"<<endl;
    
for(i=1;;i++)
    
{

        
int a,b,c;
        printf(
"请输入第%d条边以及权值(u v w):",i);
        file
>>a>>b>>c;
        cout
<<endl;
        
if(a==0&&b==0&&c==0)
            
break;
        node 
*p;
        node 
*q;
        
/////////////////////
        p=&adj[a];
        q
=new node;
        q
->v=b;
        q
->w=c;
        q
->next=p->next;
        p
->next=q;
        
////////////////////
        p=&reversed_adj[b];
        q
=new node;
        q
->v=a;
        q
->w=c;
        q
->next=p->next;
        p
->next=q;
        
///////////////////
    }


}



void topsort(node adj[],int n,int v[],int x)
{
    
int i;
    node 
*p;
    stack
<int>mystack;
    
while(!mystack.empty())
        mystack.pop();
    findindegree(adj,n);
    
for(i=1;i<=n;i++)
        v[i]
=x;
    
for(i=1;i<=n;i++)
    
{
        
if(indegree[i]==0)
        
{

            mystack.push(i);
        }

    }

    
////////////////////////////
    while(mystack.size()!=0)
    
{

        i
=mystack.top();
        mystack.pop();
        
for(p=adj[i].next;p!=NULL;p=p->next)
        
{

            indegree[p
->v]--;
            
if(indegree[p->v]==0)
                mystack.push(p
->v);
            
if(x==0)
            
{
                
if(v[i]+p->w  >  v[p->v])
                
{

                    v[p
->v]=v[i]+p->w;
                }

            }

            
else
            
{
                
if(v[i]-p->w  <  v[p->v])
                    v[p
->v]=v[i]-p->w;
            }
   

        }

    }

}



void printedg(node adj[],int n,int ve[],int vl[])
{
    
int i;
    node 
*p;
    
int k;
    
int e;
    
int l;

    
for(i=1;i<=n;i++)
    
{
        p
=adj[i].next;
        
while(p!=NULL)
        

            k
=p->v;
            e
=ve[i];
            l
=vl[k]-p->w;
            cout
<<i<<' '<<k<<' '<<e<<' '<<l;
            
if(e==l) cout<<"*";
            cout
<<endl;
            p
=p->next;
        }
//while
    }
//for

}




int main ()
{
    
int n;
    cout
<<"请输入顶点数n:";
    cin
>>n;
    initial(n);
    creat(adj,reversed_adj,n);
//建立邻接表和逆邻接表
    topsort(adj,n,ve,0);
    topsort(reversed_adj,n,vl,ve[n]);
    printedg(adj,n,ve,vl);
    system(
"pause");
    
return 0;

}



为了验证程序的正确性,故做以下测试:

输入部分为:

输出部分为:

其中前两个数代表两个顶点之间的通路,后两个数分别代表最早开始时间和最迟开始时间 带有*的通路组成关键路径;

思考:在做这个的时候,我突然觉得拓扑排序和单元最短路好像有某种相似,究竟是不是这样呢?希望网路上的朋友能帮我解答这个问题。多谢!

posted on 2009-04-14 18:55 abilitytao 阅读(2597) 评论(3)  编辑 收藏 引用

评论

# re: 张宏数据结构作业之-AOE网关键路径(Activity On Edge) 2009-04-15 12:30 brightcoder

最短路是BFS,拓扑是DFS  回复  更多评论   

# re: 张宏数据结构作业之-AOE网关键路径(Activity On Edge) 2010-03-06 10:29 吴伟斌

你的代码怎么运行时内存老是异常啊   回复  更多评论   

# re: 张宏数据结构作业之-AOE网关键路径(Activity On Edge) 2010-03-13 00:29 abilitytao

@吴伟斌
真的?能给个截图么?  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理