Status CreateALGraph(ALGraph *ALG,FILE *fp)//创立无向图的邻接表;
{
    ArcType *p = NULL;
    int i,j,w;
    
    fscanf(fp,"%d",&ALG->VexNums);
    for(i = 1;i <= ALG->VexNums;i++)    //初始化;
    {
        ALG->Vex[i].VNode = i;
        ALG->FirstArc[i] = NULL;
    }
    while(fscanf(fp,"%d%d%d",&i,&j,&w) == 3)
    {
        if(!(p = (ArcType *)malloc(sizeof(ArcType))))
            {printf("/n内存溢出。");return 1;}
        p->Adj = j;
        p->Weight = w;
        p->NextArc = ALG->FirstArc[i];
        ALG->FirstArc[i] = p;                            
        if(!(p = (ArcType *)malloc(sizeof(ArcType))))
            {printf("/n内存溢出。");return 1;}
        p->Adj = i;        //无向邻接表,反向赋值...:-(
        p->Weight = w;
        p->NextArc = ALG->FirstArc[j];
        ALG->FirstArc[j] = p;
    }
    return 0;
}
//=================================================================================
Status AL2AM(ALGraph ALG,AMGraph *AMG)    //转换为图的邻接矩阵;
{
    int i,j;
    ArcType *p = NULL;
    AMG->VexNums = ALG.VexNums;
    for(i = 1;i <= AMG->VexNums;i++)        //初始化;
        for(j = 1;j <= AMG->VexNums;j++)
            AMG->Weight[i][j] = INT_MAX;
    for(i = 1;i <= ALG.VexNums;i++)
    {
        AMG->Vex[i] = ALG.Vex[i];
        p = ALG.FirstArc[i];
        while(p != NULL)
        {
            AMG->Weight[i][p->Adj] = p->Weight;
            p = p->NextArc;
        }
    }
    return 0;
}
//=================================================================================
Status ALG_Travers(ALGraph ALG)            //图的遍历;
{
    int i,Visited[MaxSize];
    printf("/n  1. 图的深度遍历：");    
    printf("/n递  归：");
    for(i = 1;i <= ALG.VexNums;i++)        Visited[i] = 0;
    for(i = 1;i <= ALG.VexNums;i++)
        if(Visited[i] == 0)        ALG_DFS(ALG,i,Visited);
    printf("/n非递归：");
    for(i = 1;i <= ALG.VexNums;i++)        Visited[i] = 0;
    for(i = 1;i <= ALG.VexNums;i++)
        if(Visited[i] == 0)        ALG_DFS_Uni(ALG,i,Visited);
    printf("/n/n  2. 图的广度遍历：/n/t");    
    for(i = 1;i <= ALG.VexNums;i++)        Visited[i] = 0;
    for(i = 1;i <= ALG.VexNums;i++)
        if(Visited[i] == 0)        ALG_BFS(ALG,i,Visited);
    return 0;
}
//=================================================================================
Status ALG_DFS(ALGraph ALG,int v,int *Visited)    //图的深度遍历(递  归);
{
    ArcType *p = NULL;
    Visited[v] = 1;
    printf("%2d ->",v);
    p = ALG.FirstArc[v];
    while(p != NULL)
    {
        if(Visited[p->Adj] == 0)    ALG_DFS(ALG,p->Adj,Visited);
        p = p->NextArc;
    }
    return 0;
}
//=================================================================================
Status ALG_DFS_Uni(ALGraph ALG,int v,int *Visited)//图的深度遍历(非递归);
{
    ElemType Stack[MaxSize];
    ArcType *p = NULL;
    int top = -1;
    Visited[v] = 1;
    printf("%2d ->",v);
    Stack[++top] = v;
    while(top != -1)
    {
        p = ALG.FirstArc[Stack[top]];
        while(p != NULL)
        {
            if(Visited[p->Adj] == 0)
            {
                Visited[p->Adj] = 1;
                printf("%2d ->",p->Adj);
                Stack[++top] = p->Adj;
                break;
            }
            p = p->NextArc;
        }
        if(p == NULL)    --top;
    }
    return 0;
}
//=================================================================================
Status ALG_BFS(ALGraph ALG,int v,int *Visited)    //图的广度遍历;
{
    int rear,front;
    ElemType Queue[MaxSize];
    ArcType *p = NULL;
    rear = front = 0;
    Visited[v] = 1;
    printf("%2d ->",v);
    rear =(rear + 1)%MaxSize;
    Queue[rear] = v;
    while(rear != front)
    {
        front = (front + 1)%MaxSize;
        p = ALG.FirstArc[Queue[front]];
        while(p != NULL)
        {
            if(Visited[p->Adj] == 0)
            {
                Visited[p->Adj] = 1;
                printf("%2d ->",p->Adj);
                rear =(rear + 1)%MaxSize;
                Queue[rear] = p->Adj;
            }
            p = p->NextArc;
        }
    }
    return 0;
}
//=================================================================================
Status CreateMST(ALGraph ALG,AMGraph AMG)//构造最小生成树;
{
    MST MST_MP[MaxSize],MST_LP[MaxSize],MST_MK[MaxSize],MST_LK[MaxSize];  
    printf("/n/n  1. Prim普里姆(图的邻接矩阵)：/n");    
    AMG_Prim(AMG,MST_MP);        PrintMST(MST_MP);
    printf("/n/n  2. Kruskal克鲁斯卡尔(图的邻接表)：/n");
    ALG_Kruskal(ALG,MST_LK);    PrintMST(MST_LK);
    printf("/n/n  3. Prim普里姆(图的邻接表)：/n");    
    ALG_Prim(ALG,MST_LP);    PrintMST(MST_LP);
    printf("/n/n  4. Kruskal克鲁斯卡尔(图的邻接矩阵)：/n");
    AMG_Kruskal(AMG,MST_MK);        PrintMST(MST_MK);
    return 0;
}
//=================================================================================
Status AMG_Prim(AMGraph AMG,MST *MST_P) //Prim普里姆(邻接矩阵)，适于稠密网;
{
    int i,j,k,Vex[MaxSize];            //最小生成树结点;
    unsigned int min,lowcost[MaxSize];    //(由Vex[i]到i)权值;
    for(i = 2;i <= AMG.VexNums;i++)
    {
        Vex[i] = 1;            //表示V-U中各点与U(当前仅含顶点1)的关系;
        lowcost[i] = AMG.Weight[1][i];    //各点对U的权值(1到各点的权值);
    }
//    Vex[1] = 1;                //从顶点1开始遍历;
    lowcost[1] = 0;                //U中仅包含顶点1;                  
    for(i = 1;i <= AMG.VexNums;i++)
    {
        k = i;
        min = INT_MAX;
        for(j = 1;j <= AMG.VexNums;j++)//得到与当前点i相临且权值最小min的顶点k;
        {
            if(lowcost[j] < min && lowcost[j] != 0)//找(V-U)各点对U中权值最小的;
            {
                min = lowcost[j];
                k = j;
            }
        }
        if(min == INT_MAX)    break;  //若U与V-U再没有边(不连通或V==U),退出循环;
        printf("[%2d,%2d]；",Vex[k],k);
        MST_P[i].head = Vex[k];        //将得到的MST各点送入MST_P;
        MST_P[i].tail = k;
        MST_P[i].Weight = lowcost[k];
//        vex[k] = 0;
        lowcost[k] = 0;            //顶点k并入U;

        for(j = 1;j <= AMG.VexNums;j++)    //重新计算U与V-U间各个权值;
        {
            if(AMG.Weight[k][j] < lowcost[j])
            {
                Vex[j] = k;
                lowcost[j] = AMG.Weight[k][j];
            }
        }
    }
    if(i == AMG.VexNums) MST_P[0].Weight = i - 1;    
    else MST_P[0].Weight = 0;//MST结点数如与图中总数不等,则不能生成MST或有误;
    return 0;
}
//=================================================================================
Status ALG_Prim(ALGraph ALG,MST *MST_P) //(图的邻接表)Prim普里姆，适于稠密网;
{
//    struct    {ElemType Vex;    unsigned int lowcost;}closedge[MaxSize];
    int i,j,k,Vex[MaxSize];
    unsigned int min,lowcost[MaxSize];
    ArcType *p = NULL;
    for(i = 1;i <= ALG.VexNums;i++)
    {
        Vex[i] = 1;
        p = ALG.FirstArc[1];    //从[1]开始遍历;
        while(p != NULL)
        {
            if(p->Adj == i)        lowcost[i] = p->Weight;
            p = p->NextArc;
        }
    }
//    Vex[1] = 1;
    lowcost[1] = 0;
    for(i = 1;i <= ALG.VexNums;i++)
    {
        k = i;
        min = INT_MAX;
        for(j = 1;j <= ALG.VexNums;j++)
        {
            if(lowcost[j] < min && lowcost[j] != 0)
            {
                min = lowcost[j];
                k = j;
            }
        }
        if(min == INT_MAX)    break;  //若U与V-U再没有边(不连通或V==U),退出循环;
        printf("[%2d,%2d]；",Vex[k],k);
        MST_P[i].head = Vex[k];        //将得到的MST各点送入MST_P;
        MST_P[i].tail = k;
        MST_P[i].Weight = lowcost[k];
//        vex[k] = 0;
        lowcost[k] = 0;            //顶点k并入U;

        for(j = 1;j <= ALG.VexNums;j++)
        {
            p = ALG.FirstArc[k];
            while(p != NULL)
            {
                if(p->Adj == j && p->Weight < lowcost[j])
                {
                    lowcost[j] = p->Weight;
                    Vex[j] = k;
                }
                p = p->NextArc;
            }
        }
    }
    if(i == ALG.VexNums) MST_P[0].Weight = i - 1;    
    else MST_P[0].Weight = 0;//MST结点数如与图中总数不等,则不能生成MST或有误;
    return 0;
}
//=================================================================================
Status FindVex(int *Vex,int v)//(Kruskal)找顶点所在树的根结点在数组Vex中的序号;
{
    int t;
    t = v;
    while(Vex[t] > 0)
        t = Vex[t];
    return t;
}
//=================================================================================
Status AMG_Kruskal(AMGraph AMG,MST *MST_K)//Kruskal(邻接矩阵),适于稀疏网;
{
typedef struct{    ElemType v1,v2;    unsigned int cost;    }EdgeType;
    EdgeType Edgs[MaxSize];
    int i,j,k,vex1,vex2,Vex[MaxSize];
    ElemType tv;
    unsigned int tc;
    k = 1;
    Edgs[0].cost = 0;                //记录总边数到Edgs[0].cost中;
    for(i = 1;i <= AMG.VexNums;i++)  //将所有两点间关系初始化到Edgs中;
    {
        for(j = 1;j < i;j++)
        {
            Edgs[k].v1 = AMG.Vex[j].VNode;    //j变化快,赋予v1(较小的坐标在前);
            Edgs[k].v2 = AMG.Vex[i].VNode;
            Edgs[k].cost = AMG.Weight[i][j];
            if(AMG.Weight[i][j] < INT_MAX)        ++Edgs[0].cost;
            ++k;
        }
    }
    for(i = 1;i < AMG.VexNums*AMG.VexNums;i++)    //Edgs按cost值,非递减排序;
    {
        k = i;
        for(j = i+1;j <= AMG.VexNums*AMG.VexNums;j++)
            if(Edgs[k].cost > Edgs[j].cost)        k = j;
        if(k != i)
        {
            tv = Edgs[i].v1; Edgs[i].v1 = Edgs[k].v1; Edgs[k].v1 = tv;
            tv = Edgs[i].v2; Edgs[i].v2 = Edgs[k].v2; Edgs[k].v2 = tv;
            tc = Edgs[i].cost; Edgs[i].cost = Edgs[k].cost; Edgs[k].cost = tc;
        }
    }

    for(i = 1;i <= AMG.VexNums;i++)    Vex[i] = 0;    //各点初始均独立;
    i = k = 1;
    while(k < AMG.VexNums)
    {
        vex1 = FindVex(Vex,Edgs[i].v1);
        vex2 = FindVex(Vex,Edgs[i].v2);
        if(vex1 != vex2)
        {
            Vex[vex2] = vex1;
            printf("[%2d,%2d]；",Edgs[i].v1,Edgs[i].v2);
            MST_K[k].head = Edgs[i].v1;    //将得到的MST各点送入MST_K;
            MST_K[k].tail = Edgs[i].v2;
            MST_K[k].Weight = Edgs[i].cost;
            if(++k >= (int)Edgs[0].cost - 1)    break;
        }
        ++i;
    }
    if(k - 1 == AMG.VexNums - 1)    MST_K[0].Weight = AMG.VexNums - 1;
    else MST_K[0].Weight = 0;
    return 0;
}
//=================================================================================
Status ALG_Kruskal(ALGraph ALG,MST *MST_K)//Kruskal(邻接表),适于稀疏网;
{
typedef struct{ElemType v1,v2;unsigned int cost;}    EdgeType;
    int i,j,k;
    ElemType Vex[MaxSize],v1,v2,tv;
    unsigned int tc;
    ArcType *p = NULL;
    EdgeType Edge[MaxSize];
    
    for(j = 1,i = 1;i <= ALG.VexNums;i++)    //将所有两点间关系初始化到Edgs中;
    {
        Edge[j].v1 = ALG.Vex[i].VNode;
        p = ALG.FirstArc[i];
        while(p != NULL)
        {
            Edge[j].v2 = p->Adj;
            Edge[j].cost = p->Weight;
            p = p->NextArc;
            Edge[j].v1 = ALG.Vex[i].VNode;
            if(Edge[j].v1 < Edge[j].v2)    ++j;
        }
    }
    if(Edge[j].v1 > Edge[j].v2)    Edge[0].cost = j - 1;
    else Edge[0].cost = j;            //记录总边数到Edgs[0].cost中;
    
    for(i = 1;i < (int)Edge[0].cost;i++)      //Edgs按cost值,非递减排序;
    {
        k = i;
        for(j = i + 1;j <= (int)Edge[0].cost;j++)
            if(Edge[k].cost > Edge[j].cost)        k = j;
        if(k != i)
        {
            tv = Edge[i].v1; Edge[i].v1 = Edge[k].v1; Edge[k].v1 = tv;
            tv = Edge[i].v2; Edge[i].v2 = Edge[k].v2; Edge[k].v2 = tv;
            tc = Edge[i].cost; Edge[i].cost = Edge[k].cost; Edge[k].cost = tc;
        }
    }
    
    for(i = 1;i <= (int)Edge[0].cost;i++)    Vex[i] = 0;
    for(k = 1,i = 1;i <= (int)Edge[0].cost;i++)
    {
        v1 = FindVex(Vex,Edge[i].v1);
        v2 = FindVex(Vex,Edge[i].v2);
        if(v1 != v2)
        {
            Vex[v2] = v1;
            printf("[%2d,%2d]；",Edge[i].v1,Edge[i].v2);
            MST_K[k].head = Edge[i].v1;
            MST_K[k].tail = Edge[i].v2;
            MST_K[k].Weight = Edge[i].cost;
            ++k;
        }
    }
    if(k - 1 == ALG.VexNums - 1)    MST_K[0].Weight = ALG.VexNums - 1;
    else MST_K[0].Weight = 0;
    return 0;
}
//================================================================================
Status Prn_ALGraph(ALGraph ALG)            //输出邻接表;
{
    int i;
    ArcType *p = NULL;
    for(i = 1;i <= ALG.VexNums;i++)
    {
        printf("/n  %2d ==>  ",i);
        p = ALG.FirstArc[i];
        while(p != NULL)
        {
            printf("%2d(%3d) ->",p->Adj,p->Weight);
            p = p->NextArc;
        }
    }
    printf("/n");
    return 0;
}
//=================================================================================
Status Prn_AMGraph(AMGraph AMG)            //输出邻接矩阵;
{
    int i,j;
    for(i = 1;i <= AMG.VexNums;i++)
    {
        printf("/n/t");
        for(j = 1;j <= AMG.VexNums;j++)
        {
            if(AMG.Weight[i][j] < INT_MAX)    printf(" %3d ",AMG.Weight[i][j]);
            else printf("  ∞ ");
        }                                    
        printf("/n");
    }
    return 0;
}
//=================================================================================
Status PrintMST(MST *MT)            //输出最小生成树;
{
    unsigned int i = 1;
    if(MT[0].Weight == 0)    {printf("/n/t不能生成最小生成树。/n");return 1;}
    printf("/n/t边 信 息/t权  值");
    for(i = 1;i <= MT[0].Weight;i++)
        printf("/n/t(%2d,%2d)/t/t[%4d]",MT[i].head,MT[i].tail,MT[i].Weight);
    return 0;
}

 2/2   首页 上一页 1 2