搜索
编程论坛 → 开发语言 → 『 C语言论坛 』 → 论坛上的各位大神帮我看看这个图的关键路径是不是求错了，图有2个起始点为什么求出来的关键路径只从其中的一个起始点出发，是不是有问题？万分感谢！
标题：论坛上的各位大神帮我看看这个图的关键路径是不是求错了，图有2个起始点为什 ...
取消只看楼主
zqszqs10
Rank: 1
等　级：新手上路
帖　子：14
专家分：3
注　册：2016-10-27
结帖率：50%
楼主
 已结贴√  问题点数：10 回复次数：0 
论坛上的各位大神帮我看看这个图的关键路径是不是求错了，图有2个起始点为什么求出来的关键路径只从其中的一个起始点出发，是不是有问题？万分感谢！


程序代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VER_NUM 13
#define MAX_ARC_NUM 19
typedef char VertexType[4];
struct ArcInfo
{
    VertexType v1;
    VertexType v2;
};
typedef struct ArcBox
{
    int adjver;
    int weight;
    struct ArcBox *nextarc;
}ArcBox;
typedef struct VerBox
{
    VertexType data;
    ArcBox *firstarc;
}VerBox;
typedef struct Graph
{
    VerBox adjlist[MAX_VER_NUM];
    int vernum;
    int arcnum;
}Graph;
typedef struct StackInfo
{
    int data;
    struct StackInfo *next;
}StackInfo;
typedef struct Stack
{
    StackInfo *ptop;
    StackInfo *pbottom;
}Stack;
typedef struct Path//存放关键路径
{
    char v1[4],v2[4];
    int lenght;
}PathNode;
typedef struct EdgeInfo
{
    char v1[4];
    char v2[4];
    int weight;

}EdgeInfo;
char VerData[][4]={"C1","C2","C3","C4","C5","C6","C7","C8","C9","C10","C11","C12","C13"};
EdgeInfo EdgeData[MAX_ARC_NUM]={{"C1","C3",7},{"C1","C12",4},{"C1","C2",5},{"C1","C4",3},{"C2","C3",2},{"C3","C5",2},{"C3","C7",3},{"C3","C8",5},{"C4","C5",6},{"C5","C7",2}
                                    ,{"C6","C8",5},{"C7","C13",8},{"C8","C13",3},{"C9","C11",2},{"C9","C10",1},{"C9","C12",4},{"C10","C12",3},{"C11","C6",4},{"C12","C13",9}};
Stack T;//存放拓扑排序结果求ltv使用
char result[MAX_VER_NUM][4];//存放拓扑结果用于输出结果使用
int Indegree[MAX_VER_NUM]={0},Visited[MAX_VER_NUM];
int *etv,*ltv;
int LocateVer(Graph G,VertexType v)
{
    int i;
    for(i=0;i<G.vernum;i++)
    {
        if(strcmp(v,G.adjlist[i].data)==0)
        {
            return i;
        }
    }
    return -1;
}
void CreateGraph(Graph **G)
{
    VertexType v1,v2;
    //char c;
    int i,j,k,l,w;
    ArcBox *pnew;
    //FILE *fp;
    (*G)=new Graph;
    (*G)->arcnum=MAX_ARC_NUM;
    (*G)->vernum=MAX_VER_NUM;
    for(i=0;i<(*G)->vernum;i++)
    {
        strcpy((*G)->adjlist[i].data,VerData[i]);
        (*G)->adjlist[i].firstarc=NULL;
    }
    //fp=fopen("data.txt","r");
    //if(fp==NULL) printf("文件打开失败！"),exit(0);
    for(k=0;k<(*G)->arcnum;k++)
    {
        /*c=fgetc(fp);
        l=0;
        while(c!=' ')
        {
            v1[l++]=c;
            c=fgetc(fp);
        }
        v1[l]='\0';
        c=fgetc(fp);
        l=0;
        while(c!=' ')
        {
            v2[l++]=c;
            c=fgetc(fp);
        }
        v2[l]='\0';
        fscanf(fp,"%d",&w);
        fgetc(fp);*/
        strcpy(v1,EdgeData[k].v1);
        strcpy(v2,EdgeData[k].v2);
        w=EdgeData[k].weight;

        i=LocateVer(**G,v1);
        j=LocateVer(**G,v2);
        if(i>=0&&j>=0)
        {
            pnew=new ArcBox;
            pnew->adjver=j;
            pnew->weight=w;
            pnew->nextarc=(*G)->adjlist[i].firstarc;
            (*G)->adjlist[i].firstarc=pnew;
        }        
    }
    return;
}
void FindInDegree(Graph G)//求各顶点的入度
{
    int i;
    ArcBox *p;
    for(i=0;i<G.vernum;i++)
    {
        p=G.adjlist[i].firstarc;
        while(p!=NULL)
        {
            Indegree[p->adjver]++;
            p=p->nextarc;
        }
    }
    return;
}
void ShowAdjList(Graph G)//查看邻接表
{
    int i;
    ArcBox *p;
    for(i=0;i<G.vernum;i++)
    {
        p=G.adjlist[i].firstarc;
        printf("[%d|%s]",i,G.adjlist[i].data);
        while(p!=NULL)
        {
            printf("->[%d|%s|%d]",p->adjver,G.adjlist[p->adjver].data,p->weight);    
            p=p->nextarc;
        }
        printf("\n");
    }

}
void InitStack(Stack *S,Stack *T)
{
    S->pbottom=S->ptop=(StackInfo *)malloc(1*sizeof(StackInfo));
    S->ptop->next=NULL;

    T->pbottom=T->ptop=(StackInfo *)malloc(1*sizeof(StackInfo));
    T->ptop->next=NULL;
    return;
}
void Push(Stack *S,int i)
{
    StackInfo *pnew;
    pnew=(StackInfo *)malloc(1*sizeof(StackInfo));
    pnew->data=i;
    pnew->next=S->ptop;
    S->ptop=pnew;
    return;
}
int EmptyStack(Stack S)
{
    if(S.pbottom==S.ptop)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
void Pop(Stack *S,int *i)
{
    StackInfo *p;
    p=S->ptop;
    S->ptop=p->next;
    *i=p->data;
    free(p);
    return;
}
bool TopoSort(Graph *G)
{
    int i,k,count=0,l=0;
    Stack S;
    ArcBox *p;
    etv=(int *)malloc(G->vernum*sizeof(int));
    ltv=(int *)malloc(G->vernum*sizeof(int));
    InitStack(&S,&T);
    FindInDegree(*G);
    for(i=0;i<G->vernum;i++)
    {
        etv[i]=0;
        if(Indegree[i]==0)
        {
            Push(&S,i);            
        }
    }
    while(EmptyStack(S)==0)
    {
        Pop(&S,&i);Push(&T,i);count++;
        strcpy(result[l++],G->adjlist[i].data);
        printf("%-3s ",G->adjlist[i].data);
        for(p=G->adjlist[i].firstarc;p!=NULL;p=p->nextarc)
        {
            k=p->adjver;
            if(--Indegree[k] ==0)
            {
                Push(&S,k);
            }
            if(etv[i]+p->weight>etv[k])
            {
                etv[k]=etv[i]+p->weight;
            }
        }
    }
    printf("\n         etv：");
    if(count<G->vernum) 
    {    
        printf("该图有环无法进行拓扑排序！\n");
        return false;
    }
    else
    {
        for(i=0;i<G->vernum;i++)//输出etv
        {
            l=LocateVer(*G,result[i]);
            printf("%-3d ",etv[l]);    
        }
        printf("\n");
        return true;
    }    
}
int FirstAdjVer(Graph *G,int v)
{
    int n=-1;
    ArcBox *p;
    p=G->adjlist[v].firstarc;
    if(p!=NULL)
    {
        n=p->adjver;
    }
    return n;
}
int NextAdjVer(Graph *G,int v,int w)
{
    int n=-1;
    ArcBox *p;
    p=G->adjlist[v].firstarc;
    while(p!=NULL)
    {
        if(p->adjver==w && p->nextarc!=NULL)
        {
            n=p->nextarc->adjver;
            break;
        }
        p=p->nextarc;
    }
    return n;
}
void DFS(Graph *G,int v,int *flag)
{
    int w;
    Visited[v]=1;
    for(w=FirstAdjVer(G,v);w>=0;w=NextAdjVer(G,v,w))
    {
        if(Visited[w]==0 &&*flag==1)
        {
            DFS(G,w,flag);
            Visited[w]=0;
        }
        else
        {            
            *flag=0;
            break;
        }
    }
}
int IsDAG(Graph *G)
{
    int i,v,flag=1;
    for(i=0;i<G->vernum;i++)
    {
        Visited[i]=0;
    }
    for(v=0;v<G->vernum;v++)
    {
        if(Visited[v]==0 && flag==1)
        {
            DFS(G,v,&flag);
            Visited[v]=0;
        }
    }
    return flag;
}
void TSDFS(Graph *G,int v)
{
    int w;
    Visited[v]=1;
    for(w=FirstAdjVer(G,v);w>=0;w=NextAdjVer(G,v,w))
    {
        if(Visited[w]==0)
        {
            TSDFS(G,w);
        }
    }
    printf("%s ",G->adjlist[v].data);
    return;
}
void TopoSort_DFS(Graph *G)
{
    int i,v;
    if(IsDAG(G))
    {
        for(i=0;i<G->vernum;i++)
        {
            Visited[i]=0;
        }
        for(v=0;v<G->vernum;v++)
        {
            if(Visited[v]==0)
            {
                TSDFS(G,v);
            }
        }
    }
    else printf("该图有环无法拓朴排序!\n");
}
void CriticalPath(Graph *G)
{
    int i,k,l=0;
    ArcBox *p;
    int ete[MAX_ARC_NUM],lte[MAX_ARC_NUM];
    PathNode path[MAX_ARC_NUM];
    for(i=0;i<G->vernum;i++)
    {
        ltv[i]=etv[G->vernum-1];
    }
    while(EmptyStack(T)==0)
    {
        Pop(&T,&i);
        for(p=G->adjlist[i].firstarc;p!=NULL;p=p->nextarc)
        {
            k=p->adjver;
            if(ltv[i]>ltv[k]-p->weight)
            {
                ltv[i]=ltv[k]-p->weight;
            }
        }
    }
    FindInDegree(*G);
    for(i=0;i<G->vernum;i++)//起始点ltv置为0
    {
        if(Indegree[i]==0)
        {
            ltv[i]=0;            
        }
    }
    printf("         ltv：");
    for(i=0;i<G->vernum;i++)//输出ltv
    {
        k=LocateVer(*G,result[i]);
        printf("%-3d ",ltv[k]);
    }
    printf("\n");
    k=0;
    printf("\n 弧：");
    for(i=0;i<G->arcnum;i++)
    {
        printf("%c%-2d ",'a',i+1);
    }
    printf("\bete：");
    for(i=0;i<G->vernum;i++)//对ete求值
    {
        for(p=G->adjlist[i].firstarc;p!=NULL;p=p->nextarc)
        {
            ete[k]=etv[i];
            lte[k]=ltv[p->adjver]-p->weight;
            if(ete[k]==lte[k])
            {
                strcpy(path[l].v1,G->adjlist[i].data);
                strcpy(path[l].v2,G->adjlist[p->adjver].data);
                path[l].lenght=p->weight;
                l++;
            }
            k++;
            printf("%-3d ",ete[k-1]);
        }
    }
    printf("\blte：");
    for(i=0;i<G->arcnum;i++)//输了lte的值
    {
        printf("%-3d ",lte[i]);
    }
    printf("\n关键路径为：\n");
    for(i=0;i<l;i++)//输出关键路径
    {
        printf("<%-3s--%-3s>  %d\n",path[i].v1,path[i].v2,path[i].lenght);
    }
}
int main()
{
    Graph *G;
    CreateGraph(&G);
    printf("邻接表信息：\n");
    ShowAdjList(*G);
    printf("拓朴排序结果：");
    TopoSort(G);
    //printf("\n深度优先遍历逆向拓扑排序:");
    //TopoSort_DFS(G);
    //putchar(10);
    CriticalPath(G);
    return 0;
}
搜索更多相关主题的帖子: int　Graph　for　return　printf　
2017-06-27 22:38



参与讨论请移步原网站贴子：https://bbs.bccn.net/thread-478992-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有，并保留所有权利。
Powered by Discuz, Processed in 0.566654 second(s), 9 queries.
Copyright©2004-2025, BCCN.NET, All Rights Reserved