基础算法03

不过是笔记本罢了(悲~

Dijkstra 算法（狄克斯特拉算法）

这是一种求解无负权边图的最短路径的算法，他的大概过程是先将已确定最短路径的点和未确定最短路径的点分别分为两个集合，一开始所有点都处于后者集合，随后依次从后者集合取出最短路长度最小的点，移到前者集合中。这里要注意这个算法只适用于有向无环图。

该算法是求源点到其他各个顶点的最短路径，如果求解任意两个顶点的最短路径，则需要以每个顶点为源点，重复调用n次Dijkstra算法。

算法步骤：

1. 初始化，令集合S={u}，对于集合V-S中的所有顶点i，$dist[i]=G.Edge[u][i]$。
2. 找最小，在集合V-S中依照贪心策略寻找使得dist[j]具有最小值的顶点t，即$dist[t]=min(dist[j])$，即顶点t就是集合V-S中距离原点u最近的顶点。
3. 将顶点t加入集合S中，更新V-S
4. 如果结合V-S为空则算法结束，否则跳转第五步
5. 在第2步中已经找到了源点到t的最短路径，那么对集合V−S中所有与顶点t相邻的顶点j，都可以借助t走捷径。如果$dist[j]>dist[t]+G.Edge[t][j]$，则$dist[j]=dist[t]+G.Edge[t][j]$，记录顶点j的前驱为t，有p[j]=t，转到第2步。

代码实现

首先该算法需要一个图结构，包含顶点集合，边集合，顶点数，边数，

typedef struct{
	VexType Vex[MaxVnum];
	EdgeType Edge[MaxVnum][MaxVnum];
	int vexnum,edgenum; //顶点数，边数
}AMGragh;

需要一个查找下标的函数

int locatevex(AMGragh G,VexType x)
{
    for(int i=0;i<G.vexnum;i++)//查找顶点信息的下标
		if(x==G.Vex[i])
			return i;
    return -1;//没找到
}

Floyd算法（佛洛依德算法）

这是一个利用点来求得两点间路径最短的算法，它可以求出任意两点的最短距离。主要思路如下：将图中边的信息用邻接矩阵表达出来之后，依次比较两点的关系，查看是否有中间点的存在能使两点的距离变得更小，如果存在该中间点，则更新路径，注意一开始不能直接到达的点间距离设为无穷。

class Graph:
    def __init__(self, n=0, e=0):
        self.list = ["a"*e]  #点的集合
        self.edge=[[INF]*e]
        self.n = n#边数量
        self.e = e#点数量

    def CreateAdjGraph(self,n,e,a,b):#a表示节点名称，b表示邻接矩阵
        self.n = n
        self.e = e
        self.list=a
        self.edge=b

    def locateVex(self,value):# 这一步是找到名称为value的点的下标
        for i in range(self.e):# 遍历点集合
            if value==self.list[i]:
                return i
        return False  #没找到

    def Floyd(self):# 寻找最小路径算法，anser是答案矩阵，表示任意两点的最小值。
        for i in range(self.e):
            for j in range(self.e):
                anser[i][j]=self.edge[i][j]# 初始状态边的权就是答案矩阵
                if anser[i][j]<INF and i!=j:
                    pare[i][j]=i # pare是前驱矩阵，表示从i到j的最短路径中j的前一个点。
                else:
                    pare[i][j]=-1# 从i到j不存在路径
# 三层循环2333
        for k in range(self.e):
            for i in range(self.e):
                for j in range(self.e):
                    if anser[i][k]+anser[k][j]<anser[i][j]:# i到k到j比i到j距离短
                        anser[i][j]=anser[i][k]+anser[k][j]# 更新图信息
                        pare[i][j]=pare[k][j]# 将k点加入i到j路径中

    def output(self):# 分别输出两个矩阵，视情况而定
        for i in range(self.e):
            for j in range(self.e):
                print(anser[i][j],end=" ")
            print("\n")

        print("\n")

        for i in range(self.e):
            for j in range(self.e):
                print(pare[i][j],end=" ")
            print("\n")

    def FindTheLeast(self,s,e):#s代表起点，e代表终点
        global route
        if pare[s][e]!=-1:# s到e连通
            self.FindTheLeast(s,pare[s][e])# 一直找到s到e中s的下一个点
            route+=str(self.list[pare[s][e]])+"------>"# 加入答案
            # print(self.list[pare[s][e]],end="----->")
        # print(self.list[e])

Kruskal算法实现最小生成树

首先我们先知道一个最小生成树的性质：树中一定不会出现环，其边数等于顶点数减一

这个算法采用边贪心策略，基本思路是隐去图中的所有边，这样所有的点都成为了一个个独立的块。然后对所有的边按照权来排序，排序结束后按照边权从小到大一条一条加入当前的最小生成树当中，如果成环则舍弃这个边，随后重复这个过程，知道边数等于总顶点数减一或者测试完所有边时结束。值得一提的是，如果结束之后最小生成树的边数小于总顶点数减1，说明该图不连通。

二叉搜索（查找）树

二叉搜索树的中序遍历具备有序性，因此二分查找树的查找效率较高。

基本步骤：

• 若整个树为空，查找失败，返回空指针
• 若非空，将待查找值x和关键字T->data比较，若小于，查找左子树，大于，查找右子树

前面的代码较简单，查找采用的是递归查找:

typedef struct Node
{
	ElemType data;
	Node *lchild,*rchild;
}Node,*BSTree;

BSTree Search(BSTree T,ElemType value)
{
	if((!T)||value==T->data)
		return T;
	else if(value<T->data)
		return Search(T->lchild,value);
	else
		return Search(T->rchild,value);
}
void InsertTree(BSTree &T,ElemType e)
{
	if(!T)
	{
		BSTree S=new Node;
		S->data=e;
		S->lchild=NULL;
		S->rchild=NULL;
	}
	else if(e>T->data) InsertTree(T->rchild,e);
	else if(e<T->data) InsertTree(T->lchild,e);
}
void CreateBST(BSTree &T)
{
	T=NULL;
	ElemType e;
	cin>>e;
	while(e!=ENDFLAG)
	{
		InsertTree(T,e);
		cin>>e;
	}
}

删除

删除就要分情况讨论，

1. 当待删除节点左子树为空时，其右子树子承父业代替其位置
2. 当待删除节点右子树为空时，其左子树子承父业代替其位置
3. 当待删除节点没有子节点，直接删除
4. 当待删除结点有两个非空子节点，一般是用左子树最大值和右子树最小值代替它，然后删除

代码如下：

void DeleteBST(BSTree &T,char key)
{
  //从二叉排序树T中删除关键字等于key的结点
    BSTree p=T;BSTree f=NULL;
    BSTree q;
    BSTree s;
    if(!T) return; //树为空则返回
    while(p)//查找
    {
        if(p->data==key) break;  //找到关键字等于key的结点p，结束循环
        f=p;                //f为p的双亲
        if (p->data>key)
            p=p->lchild; //在p的左子树中继续查找
        else
            p=p->rchild; //在p的右子树中继续查找
    }
    if(!p) return; //找不到被删结点则返回
    //三种情况：p左右子树均不空、无右子树、无左子树
    if((p->lchild)&&(p->rchild))//被删结点p左右子树均不空
    {
        q=p;
        s=p->lchild;
        while(s->rchild)//在p的左子树中继续查找其前驱结点，即最右下结点
        {
            q=s;
            s=s->rchild;
        }
        p->data=s->data;  //s的值赋值给被删结点p,然后删除s结点
        if(q!=p)
            q->rchild=s->lchild; //重接q的右子树
        else
            q->lchild=s->lchild; //重接q的左子树
        delete s;
    }
    else
    {
        if(!p->rchild)//被删结点p无右子树，只需重接其左子树
        {
            q=p;
            p=p->lchild;
        }
        else if(!p->lchild)//被删结点p无左子树，只需重接其右子树
        {
             q=p;
             p=p->rchild;
        }
        /*――――――――――将p所指的子树挂接到其双亲结点f相应的位置――――――――*/
        if(!f)
            T=p;  //被删结点为根结点
        else if(q==f->lchild)
                f->lchild=p; //挂接到f的左子树位置
            else
                f->rchild=p;//挂接到f的右子树位置
        delete q;
	}
}

删除的代码有点难以理解，最好是根据图像来理解，首先我们要清楚这里的f节点，p节点，q节点和s节点到底是什么，f节点是待删除节点的父亲节点，p节点是待删除节点，q节点是p节点的左子树的最右节点(有点逆天)，s节点是q节点的最右的值，图像如下：

通过这个图我们就可以看到删除的过程了，首先是找到s节点，它将是代替被删除节点的节点，当p节点被修改值之后就可以删除s节点了，当构建完q节点的右子树之后，p节点被删除，s节点取代p节点的位置，最后再修改f节点的指向即可。

当然存在一种特殊情况：p的左子树里面没有右子树，这样的话p和q节点将代表了同一个节点，这时只需要将s替代掉p节点然后重接p节点的左子树即可。

平衡二叉树（AVL树）

概念

二叉搜索树的查找，插入，删除的时间复杂度均线性正比于二叉搜索树的高度，因此高度越小，效率越高。首先得明白平衡二叉树的定义，或者说平衡二叉树的一些性质：

• 左右子树的高度差的绝对值不超过1
• 左右子树也是平衡二叉树

另外节点左右子树的高度差称为平衡因子。

知道平衡二叉树的定义之后我们开始插入平衡二叉树，我们在这个二叉树当中插入20。

插入后的二叉树如下，这时我们从新插入节点向上，找到最近的不平衡节点，即左右子树高度差值大于1，以该节点为根节点的树称为最小不平衡树，也就是说我们要将该不平衡树调整为平衡二叉树即可。

基本结构代码：

typedef struct AVLNode{
   int data;
   int height;
   struct AVLNode *lchild;
   struct AVLNode *rchild;
}*AVLTree;

AVLTree Empty(AVLTree &T)//删除树
{
    if(T==NULL) return NULL;
    Empty(T->lchild);
    Empty(T->rchild);
    delete T;
    return NULL;
}

inline int Height(AVLTree T)//计算高度
{
    if(T==NULL) return 0;
    return T->height;
}

void updateHeight(AVLTree &T)//更新高度
{
     T->height=max(Height(T->lchild),Height(T->rchild))+1;
}

调整方法

知道要做什么之后，就要了解如何平衡这个树。调整平衡可以分为4种情况：LL, RR, LR, RL。

LL旋转

LL型的意思就是最近不平衡节点A和插入节点C之间的路径是两个左子树，即A的左子树的左子树为C。方法是将A顺时针旋转代替B的右子树位置，这时$T_3$空闲出来，A节点没有左子树，将被抛弃的子树$T_3$拼接到A的左子树即可。

代码：

AVLTree LL_Rotation(AVLTree &T)//LL旋转
{
    AVLTree temp=T->lchild;//temp节点是B节点
    T->lchild=temp->rchild;//T3节点接到A节点的左子树
    temp->rchild=T;//A节点接到B节点的右子树
    updateHeight(T);//更新高度
    updateHeight(temp);
    return temp;
}

RR旋转

RR型的概念理解如上，旋转方法是将A逆时针旋转取代B的左子树位置，将被抛弃的子树$T_2$放到A的右子树。

代码：

AVLTree RR_Rotation(AVLTree &T)//RR旋转
{
    AVLTree temp=T->rchild;
    T->rchild=temp->lchild;
    temp->lchild=T;
    updateHeight(T);//更新高度
    updateHeight(temp);
    return temp;
}

LR旋转

LR旋转需要分两次旋转，首先是将B做RR型旋转，后将A做LL型旋转。注意一下这里图因为方便看是移动了C节点，但实际上就是移动B到C下面并将C左子树拼接到B右子树。

AVLTree LR_Rotation(AVLTree &T)//LR旋转
{
     T->lchild=RR_Rotation(T->lchild);
     return LL_Rotation(T);
}

RL旋转

分两次旋转，B做L旋转，然后A再做R旋转。

AVLTree RL_Rotation(AVLTree &T)//RL旋转
{
    T->rchild=LL_Rotation(T->rchild);
    return RR_Rotation(T);
}

算法步骤

1. 在平衡二叉树中寻找x，如果查找失败，执行插入操作
2. 创建一个新节点p存储x，该节点双亲节点为f，高度为1。
3. 从双亲节点f出发，向上寻找最近的不平衡节点，逐层检查，如平衡更新高度，不平衡则判断类型并调整平衡。

插入节点代码：

AVLTree Insert(AVLTree &T,int x)
{
    if(T==NULL) //如果为空，创建新结点
    {
        T=new AVLNode;
        T->lchild=T->rchild=NULL;
        T->data=x;
        T->height=1;
        return T;
     }
    if(T->data==x) return T;//查找成功，什么也不做，查找失败时才插入
    if(x<T->data)//插入到左子树
    {
        T->lchild=Insert(T->lchild,x);//注意插入后饭后结果挂接到T->lchild
        if(Height(T->lchild)-Height(T->rchild)==2)//插入后看是否平衡，如果不平衡显然是插入的那一边高度大
        {                                         //沿着高度大的那条路径判断
            if(x<T->lchild->data)//判断是LL还是LR,即插入的是lchild节点的lchild 还是rchild
                T=LL_Rotation(T);
            else
                T=LR_Rotation(T);
        }
    }
    else//插入到右子树
    {
        T->rchild=Insert(T->rchild,x);
        if(Height(T->rchild)-Height(T->lchild)==2)
        {
            if(x>T->rchild->data)
                T=RR_Rotation(T);
            else
                T=RL_Rotation(T);
        }
    }
    updateHeight(T);
    return T;
}

删除节点代码：

AVLTree adjust(AVLTree &T)//删除结点后，需要判断是否还是平衡，如果不平衡，就要调整
{
    if(T==NULL) return NULL;
    if(Height(T->lchild)-Height(T->rchild)==2)//沿着高度大的那条路径判断
    {
        if(Height(T->lchild->lchild)>=Height(T->lchild->rchild))
            T=LL_Rotation(T);
        else
            T=LR_Rotation(T);
    }
    if(Height(T->rchild)-Height(T->lchild)==2)//沿着高度大的那条路径判断
    {
        if(Height(T->rchild->rchild)>=Height(T->rchild->lchild))
            T=RR_Rotation(T);
        else
            T=RL_Rotation(T);
    }
    updateHeight(T);
    return T;
}

AVLTree Delete(AVLTree &T,int x)
{
    if(T==NULL) return NULL;
    if(T->data==x)//如果找到删除节点
    {
        if(T->rchild==NULL)//如果该节点的右孩子为NULL,那么直接删除
        {
            AVLTree temp=T;
            T=T->lchild;
            delete temp;
        }
        else//否则，将其右子树的最左孩子作为这个节点，并且递归删除这个节点的值
        {
           AVLTree temp;
           temp=T->rchild;
           while(temp->lchild)
              temp=temp->lchild;
           T->data=temp->data;
           T->rchild=Delete(T->rchild,T->data);
           updateHeight(T);
        }
        return T;
    }

    if(T->data>x)//调节删除节点后可能涉及的节点
        T->lchild=Delete(T->lchild,x);
    if(T->data<x)
        T->rchild=Delete(T->rchild,x);
    updateHeight(T);
	T=adjust(T);
    return T;
}