explorer

万丈高楼平地起,勿在浮沙筑高台

0%

[What]算法图解_广度优先搜索

介绍 的相关概念,以及其对应算法。

什么是图

图是用于抽象一组连接,以图形化的方式展现不同的东西是如何相连的(比如到达目的地的路径),其中:

  • 每个点称为 节点
  • 节点与节点之间的连接称为
  • 一个节点与另一个节点的 直接连接 ,被称为 邻居
    • 当一个节点A单向与另一个节点B相连,但B没有指向A. 这称为 B是A的邻居,但A不是B的邻居
    • 当两个节点相互指向对方或没有箭头指向时才 互为邻居

什么是广度优先搜索

广度优先搜索(breadth-first search, BFS) 是用于图的查找算法, 可以找出两样东西之间的最短 路径 ,比如:

  • 编写国际跳棋AI,计算最少走多少步就可以获胜
  • 编写拼写检查器,计算最少编辑多少个地方就可以将错拼的单词改成正确的单词
  • 根据你的人际关系网络找到关系最近的医生
  • 地图app计算到达目的地的最短乘车路径

它可以回答两类问题:

  1. 从节点A出发,有前往节点B的路径吗?
  2. 从节点A出发,前往节点B的最短路径是什么?

搜索的思路:

  1. 将节点按照 相对起点由近到远的方式依次放入队列
  2. 依次从队列取出节点进行路径分析

算法实现

计算图中是否有满足条件的节点

  1. 创建一个队列,用于存储要检查的邻居节点
  2. 从队列中取出一个节点
  3. 检查节点是否满足要求
  4. 如果满足要求则退出否则将此节点的所有邻居节点都加入队列然后回到步骤二
  5. 当队列为空时,则代表没有符合要求的节点
BFS_hello.jpg

注意:节点如果已经检查了,那么需要标记其已经被检查过了,以避免重复检查。

这是为了避免节点之间是直接或间接的互为邻居关系,
如果不加入检查标记,将会进入无限循环。
  • c 代码
    BFS_code.jpg

    假设具有以上关系图, 要寻找谁的身上有钥匙(假设钥匙在 Anuj 那里)。

    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
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    #include <stdio.h>
    #include <stdbool.h>
    #include <stdlib.h>
    #include <string.h>
    #include <assert.h>

    typedef struct
    {
    char *name;
    bool is_checked;
    bool is_key;
    }node_t;

    static node_t relational_you[] =
    {
    {
    .name = "you",
    .is_checked = false,
    .is_key = false,
    },
    {
    .name = "bob",
    .is_checked = false,
    .is_key = false,
    },
    {
    .name = "alice",
    .is_checked = false,
    .is_key = false,
    },
    {
    .name = "claire",
    .is_checked = false,
    .is_key = false,
    },
    };
    static node_t relational_bob[] =
    {
    {
    .name = "bob",
    .is_checked = false,
    .is_key = false,
    },
    {
    .name = "anuj",
    .is_checked = false,
    .is_key = true,
    },
    {
    .name = "peggy",
    .is_checked = false,
    .is_key = false,
    },
    };
    static node_t relational_alice[] =
    {
    {
    .name = "alice",
    .is_checked = false,
    .is_key = false,
    },
    {
    .name = "peggy",
    .is_checked = false,
    .is_key = false,
    },
    };
    static node_t relational_claire[] =
    {
    {
    .name = "claire",
    .is_checked = false,
    .is_key = false,
    },
    {
    .name = "thom",
    .is_checked = false,
    .is_key = false,
    },
    {
    .name = "jonny",
    .is_checked = false,
    .is_key = false,
    },
    };
    static node_t relational_anuj[] =
    {
    {
    .name = "anuj",
    .is_checked = false,
    .is_key = false,
    },
    };
    static node_t relational_peggy[] =
    {
    {
    .name = "peggy",
    .is_checked = false,
    .is_key = false,
    },
    };
    static node_t relational_thom[] =
    {
    {
    .name = "thom",
    .is_checked = false,
    .is_key = false,
    },
    };
    static node_t relational_jonny[] =
    {
    {
    .name = "jonny",
    .is_checked = false,
    .is_key = false,
    },
    };
    static struct
    {
    node_t queue[20];
    int size;
    int remain_count;
    int start_index;
    int stop_index;
    }bfs_queue;

    static void bfs_queue_init(void)
    {

    bfs_queue.size = sizeof(bfs_queue.queue) / sizeof(node_t);
    bfs_queue.remain_count = bfs_queue.size;
    bfs_queue.start_index = 0;
    bfs_queue.stop_index = 0;
    }
    static bool bfs_queue_push(const node_t *node)
    {

    if(bfs_queue.remain_count <= 0)
    {
    printf("bfs queue is full!\n");
    return false;
    }

    printf("bfs push [%s]\n", node->name);
    bfs_queue.queue[bfs_queue.stop_index] = *node;
    if(++bfs_queue.stop_index >= bfs_queue.size)
    {
    bfs_queue.stop_index = 0;
    }
    bfs_queue.remain_count -= 1;

    return true;
    }
    static bool bfs_queue_pop(node_t *node)
    {

    if(bfs_queue.remain_count >= bfs_queue.size)
    {
    printf("bfs queue is empty!\n");
    return false;
    }

    *node = bfs_queue.queue[bfs_queue.start_index];
    printf("bfs pop [%s]\n", node->name);
    if(++bfs_queue.start_index >= bfs_queue.size)
    {
    bfs_queue.start_index = 0;
    }
    bfs_queue.remain_count += 1;

    return true;
    }
    static bool queue_add(node_t *node, int queue_size)
    {

    printf("add [%s] to queue,size = %d\n", node[0].name, queue_size);
    for(int i = 1; i < queue_size; i++)
    {
    if(bfs_queue_push(node + i) == false)
    {
    return false;
    }
    }

    return true;
    }
    static char first_name[10];
    bool key_find(char *name)
    {

    node_t node;
    node_t *node_queue;
    int queue_size = 0;

    if(strcmp(name, "you") == 0)
    {
    node_queue = relational_you;
    queue_size = sizeof(relational_you) / sizeof(node_t);
    }
    else if(strcmp(name, "bob") == 0)
    {
    node_queue = relational_bob;
    queue_size = sizeof(relational_bob) / sizeof(node_t);
    }
    else if(strcmp(name, "alice") == 0)
    {
    node_queue = relational_alice;
    queue_size = sizeof(relational_alice) / sizeof(node_t);
    }
    else if(strcmp(name, "claire") == 0)
    {
    node_queue = relational_claire;
    queue_size = sizeof(relational_claire) / sizeof(node_t);
    }
    else if(strcmp(name, "anuj") == 0)
    {
    node_queue = relational_anuj;
    queue_size = sizeof(relational_anuj) / sizeof(node_t);
    }
    else if(strcmp(name, "peggy") == 0)
    {
    node_queue = relational_peggy;
    queue_size = sizeof(relational_peggy) / sizeof(node_t);
    }
    else if(strcmp(name, "thom") == 0)
    {
    node_queue = relational_thom;
    queue_size = sizeof(relational_thom) / sizeof(node_t);
    }
    else if(strcmp(name, "jonny") == 0)
    {
    node_queue = relational_jonny;
    queue_size = sizeof(relational_jonny) / sizeof(node_t);
    }
    else
    {
    assert(1);
    }

    if(queue_add(node_queue, queue_size) == false)
    {
    printf("Can not add [%s] to queue\n", node_queue[0].name);
    }

    do
    {
    if(bfs_queue_pop(&node) == false) return false;
    }while(node.is_checked == true);

    if(node.is_key == true)
    {
    if(strcpy(first_name, node.name)) assert(1);
    return true;
    }
    else
    {
    node.is_checked = true;
    return key_find(node.name);
    }
    }
    int main(int argc, char *argv[])
    {

    memset(first_name, 0, 10);
    if(strcpy(first_name, relational_you[0].name))
    {
    assert(1);
    }
    bfs_queue_init();
    if(key_find(first_name) == true)
    {
    printf("[%s] has the key!\n", first_name);
    }
    else
    {
    printf("Can not find key!\n");
    }

    return 0;
    }
  • 运行时间
    1. 在搜索网络过程中,需要每一条边都要搜索,时间为 O(边数)
    2. 将队列中的人数添加到总队列,时间为 O(人数)

    所以运行时间为 O(人数 + 边数),写作 O(V + E),V为顶点,E为边数。

Last Updated 2020-06-28 Sun 11:59.
Render by hexo-renderer-org with Emacs 26.3 (Org mode 9.3.7)