常用算法模板库(C++)_3

图

图的定义

/*注：在调用成员函数int BFS(int (*Visit)(GraphClass &,int), int Start)前需要定义QueueClass类*/

template

class GraphClass

{

private:

    int Size;

    VexType *Vex;

    ArcType **Arc;

 

    void DfsTravel(int (*Visit)(GraphClass &,int), int Now, bool Visited[]);

 

public:

    void Init();  //初始化图顶点和边

    GraphClass(int x);  //构造函数，创建一个定点数为x的图

    int UpdateVex(int Num, VexType Data);  //更改顶点Num的数据为Data

    int UpdateArc(int x, int y, ArcType Data, bool Untl=false);  //更改边的数据为Data，Untl=true时表示这条边是单向边

    int GetSize();  //返回图的顶点数

    VexType GetVex(int Num);  //获取顶点Num的数据

    ArcType GetArc(int x, int y);  //获取边的数据

    int InDegree(int Num);  //求顶点Num的入度

    int OutDegree(int Num);  //求顶点Num的出度

    int DFS(int (*Visit)(GraphClass &,int), int Start);  //以Start为起点，Visit为访问方式，深度优先遍历图

    int BFS(int (*Visit)(GraphClass &,int), int Start);  //以Start为起点，Visit为访问方式，宽度优先遍历图

    ~GraphClass();  //析构函数

} ;

 

template

void GraphClass::Init()

{

    int i,j;

 

    for (i=0;i<=Size-1;i++) Vex[i]=0;

    for (i=0;i<=Size-1;i++)

        for (j=0;j<=Size-1;j++) Arc[i][j]=0;

}

 

template

GraphClass::GraphClass(int x)

{

    int i;

 

    Size=x;

    Vex=new VexType[Size];

    Arc=new ArcType *[Size];

    for (i=0;i<=Size-1;i++) Arc[i]=new ArcType[Size];

    Init();

}

 

template

int GraphClass::UpdateVex(int Num, VexType Data)

{

    if (Num

    {

        Vex[Num]=Data;

        return 0;

    }

    else return 1;

}

 

template

int GraphClass::UpdateArc(int x, int y, ArcType Data, bool Untl=false)

{

    if (x

    {

        Arc[x][y]=Data;

        if (Untl) Arc[y][x]=0;

        else Arc[y][x]=Data;

        return 0;

    }

    return 1;

}

 

template

int GraphClass::GetSize()

{

    return Size;

}

 

template

VexType GraphClass::GetVex(int Num)

{

    if (Num

    else return 0;

}

 

template

ArcType GraphClass::GetArc(int x, int y)

{

    if (x

    else return 0;

}

 

template

int GraphClass::InDegree(int Num)

{

    int Ans=0,i;

 

    for (i=0;i<=Size-1;i++)

        if (Arc[i][Num]>0) Ans++;

    return Ans;

}

 

template

int GraphClass::OutDegree(int Num)

{

    int Ans=0,i;

 

    for (i=0;i<=Size-1;i++)

        if (Arc[Num][i]>0) Ans++;

    return Ans;

}

 

template

void GraphClass::DfsTravel(int (*Visit)(GraphClass &,int), int Now, bool Visited[])

{

    int i;

 

    Visit(*this,Now);

    Visited[Now]=true;

    for (i=0;i<=Size-1;i++)

        if (Arc[Now][i]>0 && !Visited[i]) DfsTravel(Visit,i,Visited);

}

 

template

int GraphClass::DFS(int (*Visit)(GraphClass &,int), int Start)

{

    int i;

    bool *Visited=new bool[Size];

 

    if (Start

    {

        for (i=0;i<=Size-1;i++) Visited[i]=false;

        DfsTravel(Visit,Start,Visited);

        return 0;

    }

    else return 1;

}

 

template

int GraphClass::BFS(int (*Visit)(GraphClass &,int), int Start)

{

    QueueClass Queue;

    int i,Temp;

    bool *Visited=new bool[Size];

 

    if (Start

    {

        for (i=0;i<=Size-1;i++) Visited[i]=false;

        Queue.Push(Start);

        Visited[Start]=true;

        while (!Queue.Empty())

        {

            Queue.Pop(Temp);

            Visit(*this,Temp);

            for (i=0;i<=Size-1;i++)

                if (Arc[Temp][i]>0 && !Visited[i])

                {

                    Queue.Push(i);

                    Visited[i]=true;

                }

        }

        return 0;

    }

    else return 1;

}

 

template

GraphClass::~GraphClass()

{

    int i;

 

    delete[] Vex;

    for (i=0;i<=Size-1;i++) delete[] Arc[i];

    delete[] Arc;

}

图的最短路径

8.2.1 Dijkstra算法

/*

函数功能：计算图的单源最短路径。

函数原形：void Dijkstra(GraphClass &Graph, int Start);

参数：

GraphClass &Graph：目标图；

int Start：起点下标。

返回值：ArcType *型，结果数组首地址。

备注：无。

*/

template

ArcType *Dijkstra(GraphClass &Graph, int Start)

{

    ArcType *Distance=new ArcType[Graph.GetSize()],Min,Infinite=ArcType(unsigned(~0)/2);

    int i,j,m;

    bool *Used=new bool[Graph.GetSize()];

 

    for (i=0;i<=Graph.GetSize()-1;i++)

    {

        Used[i]=false;

        if (Graph.GetArc(Start,i)>0) Distance[i]=Graph.GetArc(Start,i);

        else Distance[i]=Infinite;

    }

    Distance[Start]=0;

    Used[Start]=1;

    for (i=1;i<=Graph.GetSize()-1;i++)

    {

        Min=Infinite;

        m=Start;

        for (j=0;j<=Graph.GetSize()-1;j++)

            if (!Used[j] && Distance[j]

            {

                m=j;

                Min=Distance[j];

            }

        Used[m]=true;

        for (j=0;j<=Graph.GetSize()-1;j++)

            if (Graph.GetArc(m,j)>0 && !Used[j] && Min+Graph.GetArc(m,j)

    }

    return Distance;

}

8.2.2 Floyd算法

/*

函数功能：计算图的单源最短路径。

函数原形：void Floyd(GraphClass &Graph);

参数：

GraphClass &Graph：目标图。

返回值：ArcType **型，结果数组首地址。

备注：无。

*/

template

ArcType **Floyd(GraphClass &Graph)

{

    ArcType **Distance,Infinite=ArcType(unsigned(~0)/2);

    int i,j,k;

   

    Distance=new ArcType *[Graph.GetSize()];

    for (i=0;i<=Graph.GetSize()-1;i++) Distance[i]=new ArcType[Graph.GetSize()];

    for (i=0;i<=Graph.GetSize()-1;i++)

        for (j=0;j<=Graph.GetSize()-1;j++)

            if (Graph.GetArc(i,j)>0) Distance[i][j]=Graph.GetArc(i,j);

            else Distance[i][j]=Infinite;

    for (k=0;k<=Graph.GetSize()-1;k++)

        for (i=0;i<=Graph.GetSize()-1;i++)

            for (j=0;j<=Graph.GetSize()-1;j++)

                if (i!=j && i!=k && k!=j)

                    if (Distance[i][k]+Distance[k][j]

    return Distance;

}

最小生成树

8.3.1 prim算法

/*

函数功能：求图的最小生成树。

函数原形：GraphClass *Prim(GraphClass &Graph);

参数：

GraphClass &Graph：目标图。

返回值：GraphClass *型，最小生成树地址。

备注：无。

*/

template

GraphClass *Prim(GraphClass &Graph)

{

    ArcType Min,Infinite=ArcType(unsigned(~0)/2);

    GraphClass *Mcst=new GraphClass(Graph.GetSize());

    int i,j,k,x,y;

    bool *Vertex=new bool[Graph.GetSize()];

 

    for (i=0;i<=Graph.GetSize()-1;i++)

    {

        Vertex[i]=false;

        Mcst->UpdateVex(i,Graph.GetVex(i));

    }

    Vertex[0]=true;

    for (k=1;k<=Graph.GetSize()-1;k++)

    {

        Min=Infinite;

        for (i=0;i<=Graph.GetSize()-1;i++)

            for (j=0;j<=Graph.GetSize()-1;j++)

                if (Graph.GetArc(i,j)>0 && Vertex[i] && !Vertex[j] && Graph.GetArc(i,j)

                {

                    Min=Graph.GetArc(i,j);

                    x=i;

                    y=j;

                }

        Vertex[y]=true;

        Mcst->UpdateArc(x,y,Graph.GetArc(x,y));

    }

    return Mcst;

}

8.3.2 Kruskal算法

/*

函数功能：求图的最小生成树。

函数原形：GraphClass *Kruskal(GraphClass &Graph);

参数：

GraphClass &Graph：目标图。

返回值：GraphClass *型，最小生成树地址。

备注：无。

*/

template

GraphClass *Kruskal(GraphClass &Graph)

{

    ArcType Min,Infinite=ArcType(unsigned(~0)/2);

    GraphClass *Mcst=new GraphClass(Graph.GetSize());

    int i,j,k,x,y,a,b,*VexSet=new int[Graph.GetSize()];

 

    for (i=0;i<=Graph.GetSize()-1;i++)

    {

        VexSet[i]=i;

        Mcst->UpdateVex(i,Graph.GetVex(i));

    }

    for (k=1;k<=Graph.GetSize()-1;k++)

    {

        Min=Infinite;

        for (i=0;i<=Graph.GetSize()-1;i++)

            for (j=0;j<=Graph.GetSize()-1;j++)

                if (Graph.GetArc(i,j)>0 && VexSet[i]!=VexSet[j] && Mcst->GetArc(i,j)==0 && Graph.GetArc(i,j)

                {

                    Min=Graph.GetArc(i,j);

                    x=i;

                    y=j;

                    a=VexSet[i];

                    b=VexSet[j];

                }

        for(i=0;i<=Graph.GetSize();i++)

            if(VexSet[i]==b) VexSet[i]=a;

        Mcst->UpdateArc(x,y,Graph.GetArc(x,y));

    }

    return Mcst;

}

拓扑排序

/*

函数功能：求有向图的拓扑序列。

函数原形：int TopSort(GraphClass &Graph, int Sequence[]);

参数：

GraphClass &Graph：目标图；

int Sequence[]：拓扑序列。

返回值：int型，返回1表示有向图中有环路。

备注：需定义StackClass类。

*/

template

int TopSort(GraphClass &Graph, int Sequence[])

{

    StackClass Stack;

    int i,x,Count,*InDegree=new int[Graph.GetSize()];

 

    for (i=0;i<=Graph.GetSize()-1;i++) InDegree[i]=Graph.InDegree(i);

    for (i=0;i<=Graph.GetSize()-1;i++)

        if (InDegree[i]==0) Stack.Push(i);

    Count=0;

    while (!Stack.Empty())

    {

        Stack.Pop(x);

        Sequence[Count++]=x;

        for (i=0;i<=Graph.GetSize()-1;i++)

            if (Graph.GetArc(x,i)>0)

                if (--InDegree[i]==0) Stack.Push(i);

    }

    if (Count==Graph.GetSize()) return 0;

    else return 1;

}

关键路径

/*

函数功能：求有向图的关键路径。

函数原形：GraphClass *CriticalPath(GraphClass &Graph);

参数：

GraphClass &Graph：目标图。

返回值：GraphClass *型，关键路径地址，如果图中有环路，返回NULL。

备注：需定义TopSort，和StackClass类。

*/

template

GraphClass *CriticalPath(GraphClass &Graph)

{

    ArcType Min,Max,*VexEarlest=new ArcType[Graph.GetSize()],*VexLatest=new ArcType[Graph.GetSize()],Infinite=ArcType(unsigned(~0)/2);

    GraphClass *Path=new GraphClass(Graph.GetSize());

    int i,j,*Sequence=new int[Graph.GetSize()];

 

    if (TopSort(Graph,Sequence)==0)

    {

        for (i=0;i<=Graph.GetSize()-1;i++) Path->UpdateVex(i,Graph.GetVex(i));

        VexEarlest[0]=0;

        for (i=1;i<=Graph.GetSize()-1;i++)

        {

            Max=0;

            for (j=0;j<=Graph.GetSize()-1;j++)

                if (Graph.GetArc(j,Sequence[i])>0 && VexEarlest[j]+Graph.GetArc(j,Sequence[i])>Max) Max=VexEarlest[j]+Graph.GetArc(j,Sequence[i]);

            VexEarlest[Sequence[i]]=Max;

        }

        VexLatest[Graph.GetSize()-1]=VexEarlest[Graph.GetSize()-1];

        for (i=Graph.GetSize()-2;i>=0;i--)

        {

            Min=Infinite;

            for (j=0;j<=Graph.GetSize()-1;j++)

                if (Graph.GetArc(Sequence[i],j)>0 && VexLatest[j]-Graph.GetArc(Sequence[i],j)

            VexLatest[Sequence[i]]=Min;

        }

        for (i=0;i<=Graph.GetSize()-1;i++)

            for (j=0;j<=Graph.GetSize()-1;j++)

                if (Graph.GetArc(i,j)>0 && VexEarlest[i]==VexLatest[i] && VexEarlest[j]==VexLatest[j]) Path->UpdateArc(i,j,Graph.GetArc(i,j),1);

        return Path;

    }

    else return NULL;

}

高精度计算

加法

/*

函数功能：高精度加法。

函数原形：string Add(string Num1, string Num2);

参数：

string Num1, string Num2：被加数与加数。

返回值：string型，两数之和。

备注：需包含。

*/

string Add(string Num1, string Num2)

{

    string Ans;

    int *a,*b,i,Max,Len,Len1,Len2,k;

 

    Len1=(int)Num1.length();

    Len2=(int)Num2.length();

    if (Len1>Len2) Len=Len1;

    else Len=Len2;

    Max=Len;

    a=new int[Len+1];

    for (i=0;i<=Len;i++) a[i]=0;

    b=new int[Len];

    for (i=0;i<=Len-1;i++) b[i]=0;

    k=0;

    for (i=Len1-1;i>=0;i--) a[k++]=Num1[i]-'0';

    k=0;

    for (i=Len2-1;i>=0;i--) b[k++]=Num2[i]-'0';

    for (i=0;i<=Len-1;i++)

    {

        a[i]=a[i]+b[i];

        if (a[i]>=10)

        {

            a[i]=a[i]-10;

            a[i+1]++;

        }

    }

    while (Len+1>Max || a[Len+1]==0) Len--;

    for (i=Len+1;i>=0;i--) Ans.append(1,a[i]+'0');

    return Ans;

}

减法

/*

函数功能：高精度减法。

函数原形：string Sub(string Num1, string Num2);

参数：

string Num1, string Num2：被减数与减数。

返回值：string型，两数之差。

备注：需包含。

*/

string Sub(string Num1, string Num2)

{

    string Ans;

    int *a,*b,i,Max,Len,Len1,Len2,k;

 

    Len1=(int)Num1.length();

    Len2=(int)Num2.length();

    Len=Len1;

    Max=Len;

    a=new int[Len];

    b=new int[Len];

    for (i=0;i<=Len-1;i++)

    {

        a[i]=0;

        b[i]=0;

    }

    k=0;

    for (i=Len1-1;i>=0;i--) a[k++]=Num1[i]-'0';

    k=0;

    for (i=Len2-1;i>=0;i--) b[k++]=Num2[i]-'0';

    for (i=0;i<=Len-1;i++)

        if (a[i]

        {

            a[i+1]--;

            a[i]=a[i]+10;

            a[i]=a[i]-b[i];

        }

        else a[i]=a[i]-b[i];

    while (a[Len]==0 && Len>0 || Len>=Max) Len--;

    for (i=Len;i>=0;i--) Ans.append(1,a[i]+'0');

    return Ans;

}

乘法

/*

函数功能：高精度乘法。

函数原形：string Sub(string Num1, string Num2);

参数：

string Num1, string Num2：被乘数与乘数。

返回值：string型，两数之积。

备注：需包含。

*/

string Mul(string Num1, string Num2)

{

    string Ans;

    int *a,*b,*c,Max,Len1,Len2,Len,k,x,y,z,i,j,w;

 

    Len1=(int)Num1.length();

    Len2=(int)Num2.length();

    Len=Len1+Len2;

    Max=Len;

    a=new int[Len1];

    for (i=0;i<=Len1-1;i++) a[i]=0;

    b=new int[Len2];

    for (i=0;i<=Len2-1;i++) b[i]=0;

    c=new int[Len];

    for (i=0;i<=Len-1;i++) c[i]=0;

    k=0;

    for (i=Len1-1;i>=0;i--) a[k++]=Num1[i]-'0';

    k=0;

    for (i=Len2-1;i>=0;i--) b[k++]=Num2[i]-'0';

    for (i=0;i<=Len1-1;i++)

        for (j=0;j<=Len2-1;j++)

        {

            x=a[i]*b[j];

            y=x/10;

            z=x%10;

            w=i+j;

            c[w]=c[w]+z;

            c[w+1]=c[w+1]+c[w]/10+y;

            c[w]=c[w]%10;

        }

    while (c[Len]==0 && Len>0 || Len>=Max) Len--;

    for (i=Len;i>=0;i--) Ans.append(1,c[i]+'0');

    return Ans;

}