Scott's world.

第七讲图中

Word count: 1.6kReading time: 7 min
2019/07/26 Share

第七讲 图(中)

Tree Traversals Aagin

题意理解

核心算法

Complete Binary Search Tree

题意理解

核心算法

  • 存储结构

  • 实现步骤

  • 实现核心代码

    • 排序

      C/C++有一个快速的排序库函数

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      //自定义排序规则
      int compare(const void *a,const void *b)
      {
      return *(int*)a-*(int*)b;
      }

      #include<stdlib.h>
      int main()
      {
      ......
      qsort(A,N,sizeof(int),compare);
      }
    • 计算左子树的规模

Huffman Code

题意理解

  • Huffman Codes 的特点

    1.最优编码-WPL最小

    2.无歧义解码-前缀码:数据仅存于叶子结点

    3.没有度为1的结点(满足1,2则必然有3)

    满足2,3不一定有1

核心算法

  • 计算最优编码长度

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    MinHeap H=createHeap(N); //创建一个空的,容量为N的最小堆
    H = ReadData(N); //将f[]读入H->Data[]中
    HuffmanTree T=Huffman(H); //建立哈夫曼树
    int CodeLen = WPL(T,0);

    int WPL(HuffmanTree T,int Depth)
    {
    if(!T->Left && !T->Right)
    return (Depth*T->Weight);
    else //否则T一定有两个孩子
    return (WPL(T->Left,Depth+1)
    +WPL(T->Right,Depth+1));
    }
  • 检查是否正确

    • 长度是否正确

      WPL

    • 建树的过程中检查是否满足前缀码要求

最短路径问题

在网络中,求两个不同顶点之间的所有路径中,边的权值之和最小的那一条路径

  • 问题分类
    • 单源最短路径问题:从某固定源点出发,求其到所有其他顶点的最短路径
      • 无向图
      • 有向图
    • 多源最短路径问题:求任意两顶点间的最短路径

无权图的单源最短路算法

  • 按照递增的顺序找出到各个顶点的最短路

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    //伪代码
    /*
    dist[w]=S到W的最短路径
    dist[S]=0
    path[W]=S到W的路上经过的某顶点
    */

    void Unweighted(Vertex S)
    {
    Enqueue(S,Q);
    while(!IsEmpty(Q)){
    V=Dequeue(Q);
    for(V的每个邻接点W)
    if(dist[W]==-1){
    dist[W]=dist[V]+1;
    path[W]=V;
    Enqueue(W,Q);
    }
    }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    /* 邻接表存储 - 无权图的单源最短路算法 */

    /* dist[]和path[]全部初始化为-1 */
    void Unweighted(LGraph Graph,int dist[],int path[],Vertex S)
    {
    Queue Q;
    Vertex V;
    PtrToAdjVNode W;

    Q=CreateQueue(Graph->Nv); /* 创建空队列, MaxSize为外部定义的常数 */
    dist[S]=0; //初始化源点
    AddQ(Q,S);

    while(!IsEmpty(Q)){
    V=DeleteQ(Q);
    for(W=Graph->G[V].FirstEdge;W;W=W->Next)/* 对V的每个邻接点W->AdjV */
    if(dist[W->AdjV]==-1){
    /* 若W->AdjV未被访问过 */
    dist[W->AdjV] = dist[V]+1; /* W->AdjV到S的距离更新 */
    path[W->AdjV] = V; /* 将V记录在S到W->AdjV的路径上 */
    AddQ(Q, W->AdjV);
    }
    }
    }

有权图的单源最短路算法

Dijkstra算法

dist[W] = min{dist[W],dist[V]+权重}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//伪代码
void Dijkstra(Vertex s)
{
while(1)
{
V=未收录顶点中dist最小者;
if(这样的V不存在)
break;
collected[V]=true;
for(V的每个邻接点w)
if(collected[W]==false)
if(dist[V]+E_<V,W> < dist[W])
{
dist[W]=dist[V]+E_<V,E>;
path[W]=V;
}
}
//不能解决有负边的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/* 邻接矩阵存储 - 有权图的单源最短路算法 */

Vertex FindMinDist(MGraph Graph,int dist[],int collected[])
{
//返回未被收录顶点中dist最小者
Vertex MinV,V;
int MinDist = INFINITY;

for(V=0;V<Graph->Nv;V++)
{
if(collected[V]==false && dist[V]<MinDist){
/* 若V未被收录,且dist[V]更小 */
MinDist = dist[V]; /* 更新最小距离 */
MinV = V; /* 更新对应顶点 */
}
}
if(MinDist <INFINITY) //若找到最小dist
return MinV; //返回对应的顶点下标
else return ERROR; //若这样的顶点不存在,返回错误标记
}

bool Dijkstra(MGraph Graph,int dist[],int path[],Vertex S)
{
int collected[MaxVertexNum];
Vertex V,W;

/* 初始化:此处默认邻接矩阵中不存在的边用INFINITY表示 */
for(V=0;V<Graph->Nv;V++)
{
dist[V]=Graph->G[S][V];
if(dist[V]<INFINITY)
path[V]=S;
else
path[V]=-1
}
/* 先将起点收入集合 */
dist[S]=0;
collected[S]=true;

while(1){
/* V = 未被收录顶点中dist最小者 */
V =FindMinDist(Graph,dist,collected);
if(V==ERROR)
break; //若这样的V不存在则算法结束
collected[V]=true; //收录V
for(W=0;W<Graph->Nv;W++) /* 对图中的每个顶点W */
/* 若W是V的邻接点并且未被收录 */
if(collected[W]==false && Graph->G[V][W]<INFINITY){
if(Graph->G[V][W]<0)/* 若有负边 */
return false;/* 不能正确解决,返回错误标记 */
/* 若收录V使得dist[W]变小 */
if(dist[V]+Graph->G[V][W]<dist[W]){
dist[W]=dist[V]+Graph->G[V][W];/* 更新dist[W] */
path[W]=V;/* 更新S到W的路径 */
}
}
}
return true; /* 算法执行完毕,返回正确标记 */
}
  • 其时间复杂度T

  • 其一般步骤为

多源最短路算法

Floyd算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//伪代码
void Floyd()
{
for(i=0;i<N,;i++)
for(j=0;j<N;j++)
{
D[i][j]=G[i][j];
path[i][j]=-1;
}

for(k=0;k<N;k++)
for(i=0;i<N,;i++)
for(j=0;j<N;j++)
if(D[i][k]+D[k][j]<D[i][j]){
D[i][j]=D[i][k]+D[k][j];
path[i][j]=k;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* 邻接矩阵存储 - 多源最短路算法 */

void Floyd(MGraph Graph,WeightType D[][MaxVertexNum],Vertex path[][MaxVertexNum])
{
Vertex i,j,k;

//初始化
for ( i=0; i<Graph->Nv; i++ )
for( j=0; j<Graph->Nv; j++ ) {
D[i][j] = Graph->G[i][j];
path[i][j] = -1;
}

for( k=0; k<Graph->Nv; k++ )
for( i=0; i<Graph->Nv; i++ )
for( j=0; j<Graph->Nv; j++ )
if( D[i][k] + D[k][j] < D[i][j] ) {
D[i][j] = D[i][k] + D[k][j];
if ( i==j && D[i][j]<0 ) /* 若发现负值圈 */
return false; /* 不能正确解决,返回错误标记 */
path[i][j] = k;
}
return true; /* 算法执行完毕,返回正确标记 */
}

应用例题:哈利波特的考试

题意理解

程序框架搭建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void FIndAnimal(MGraph Graph)
{
WeightType D[MaxVertexNum][MaxVertexNum],MaxDist,MinDist;
Vertex Animal,i;

Floyd(Graph,D);

MinDist=INFINITY;
for(i=0;i<Graph->Nv;i++){
MaxDist=FindMaxDist(D,i,Graph->Nv);
if(MaxDist==INFINITY){ //说明有从i无法变出的动物
printf("0\n");
return ;
}
if(MinDist>MaxDist){ //找到最长距离更小的动物
//更新距离,记录编号
MinDist=MaxDist;
Animal=i+1;
}
}
printf("%d %d\n",Animal,MinDist);
}

WeightType FindMaxDist(WeightType D[][MaxVertexNum,Vertex i,int N])
{
WeightType MaxDist;
Vertex j;

MaxDist = 0;
for(j=0;j<N;j++) //找出i到其他动物j的最长距离
if(i!=j &&D[i][j]>MaxDist)
MaxDist = D[i][j];

return MaxDist;
}

模块引用与裁剪

CATALOG
  1. 1. 第七讲 图(中)
    1. 1.1. Tree Traversals Aagin
      1. 1.1.1. 题意理解
      2. 1.1.2. 核心算法
    2. 1.2. Complete Binary Search Tree
      1. 1.2.1. 题意理解
      2. 1.2.2. 核心算法
    3. 1.3. Huffman Code
      1. 1.3.1. 题意理解
      2. 1.3.2. 核心算法
    4. 1.4. 最短路径问题
      1. 1.4.1. 无权图的单源最短路算法
      2. 1.4.2. 有权图的单源最短路算法
        1. 1.4.2.1. Dijkstra算法
      3. 1.4.3. 多源最短路算法
        1. 1.4.3.1. Floyd算法
    5. 1.5. 应用例题:哈利波特的考试
      1. 1.5.1. 题意理解
      2. 1.5.2. 程序框架搭建
      3. 1.5.3. 模块引用与裁剪