《算法导论》学习总结 — XX.第22章 图的基本算法

建议先看看前言:http://www.wutianqi.com/?p=2298

这一章都是一些图的基础概念和算法。

图的两种表示方法:1.邻接表 2.邻接矩阵

BFS(广搜):

广搜就是广度优先搜索,根据名字可以知道,是通过广度来遍历图,也就是层次遍历吧。

在这里以及下面的DFS(深搜),都用到了颜色WHITE,GRAY,BLACK,不过作用不同,具体分别再分析。

在BFS中,WHITE,GRAY,BLACK这三色是用来记录一个点是否被搜到,以及是否它的邻接点都是灰色。(具体见P324倒数第2段)。

P326 的图22-3是个经典的图,看了此图基本就知道BFS是干嘛的了。

在图22-3中,因为他是用字母表示的,我把各点定义为顺时针从标号1开始,于是r点是1号,源点s是2号。

这是我写的具体实现(C/C++):

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
/*
 * Introduction to Algorithms
 * Chapter 22 --- BFS
 * Tanky Woo @ www.WuTianQi.com
 * 2012.1.6
 */
#include <iostream>
#include <queue>
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX 999999
#define NIL 0
 
using namespace std;
 
int node;
int G[100][100];
int color[100];
int dist[100];
int prev[100];
 
void BFS(int source)
{
    for(int i=1; i<=node; ++i)
    {
        color[i] = WHITE;
        dist[i] = MAX;
        prev[i] = NIL;
    }
    color[source] = GRAY;
    dist[source] = 0;
    prev[source] = NIL;
 
    queue<int> que;
    que.push(source);
 
    while(!que.empty())
    {
        int no = que.front();
        que.pop();
        for(int i=1; i<=node; ++i)
            if(G[no][i]==1 && color[i]==WHITE)
            {
                color[i] = GRAY;
                dist[i] = dist[no] + 1;
                prev[i] = no;
                que.push(i);
            }
        color[no] = BLACK;
    }
 
 
}
 
void printPath(int source, int dest)
{
    if(source == dest)
        cout << source;
    else if(prev[dest] == NIL)
        cout << "No path from " << source << " to " << dest << " exist\n";
    else
    {
        printPath(source, prev[dest]);
        cout << " " << dest;
    }
 
}
 
int main()
{
    freopen("input.txt", "r", stdin);
 
    memset(G, 0, sizeof(G));
    cout << "Input the number of the node:\n";
    cin >> node;
    cout << "Input the Graph:\n";
    for(int i=1; i<=node; ++i)
        for(int j=1; j<=node; ++j)
            cin >> G[i][j];
    BFS(2);
 
    cout << dist[4] << endl;
    cout << "The path: ";
    printPath(2, 4);
 
}

这是input.txt的内容:

8
0 1 0 0 0 0 0 1
1 0 0 0 0 0 1 0
0 0 0 1 0 1 1 0
0 0 1 0 1 1 0 0
0 0 0 1 0 1 1 0
0 0 1 1 1 0 0 0
0 1 1 0 1 0 0 0
1 0 0 0 0 0 0 0

可以看到结果,源点(2号)到u点(4号)的距离是3.

源码我上传到我的网盘了:

http://www.kuaipan.cn/file/id_35241628297855049.html

DFS(深搜):

深搜既深度优先搜索,相对于BFS,它是尽可能深的去搜索一个图。

在DFS中,仍然用到了WHITE, GRAY,BLACK,但是它们的用处和BFS有些不同,这里他们是用来表示时间戳,因为DFS会有回溯,所以也就有第一次和第二次搜到。(具体见P330面)

看P331面图22-4。

具体实现(C/C++):

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
/*
 * Introduction to Algorithms
 * Chapter 22 --- DFS
 * Tanky Woo @ www.WuTianQi.com
 * 2012.1.6
 */
 
#include <iostream>
#include <queue>
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define NIL 0
 
using namespace std;
 
int node;
int G[100][100];
int color[100];
int fir[100], sec[100];  // 用来记录前后时间戳
int prev[100];
int time;   // time用来记录时间戳
 
void DFS_VISIT(int no)
{
    color[no] = GRAY;   // 当点no第一次被搜到
    ++time;
    fir[no] = time;
    for(int i=1; i<=node; ++i)
    {
        if(G[no][i]==1 && color[i]==WHITE)
        {
            prev[i] = no;
            DFS_VISIT(i);
        }
    }
    color[no] = BLACK;    // 当点no深搜完回溯时再次搜到
    sec[no] = ++time;
 
}
 
void DFS()
{
    for(int i=1; i<=node; ++i)
    {
        if(color[i] == WHITE)
            prev[i] = NIL;
    }
    time = 0;
    for(int i=1; i<=node; ++i)
    {
        if(color[i] == WHITE)
            DFS_VISIT(i);
    }
}
 
 
int main()
{
    freopen("input.txt", "r", stdin);
 
    memset(G, 0, sizeof(G));
    cout << "Input the number of the node:\n";
    cin >> node;
    cout << "Input the Graph:\n";
    for(int i=1; i<=node; ++i)
        for(int j=1; j<=node; ++j)
            cin >> G[i][j];
 
    DFS();
    cout << "点v(2号)的first:" << fir[2] << " 和second:" << sec[2] << endl;
}

这是input.txt的内容:

6
0 1 0 0 0 1
0 0 0 0 1 0
0 0 0 1 1 0
0 0 0 1 0 0
0 0 0 0 0 1
0 1 0 0 0 0

可以看到结果,点v(2号)的first和second分别是2和7

源码我上传到我的网盘了:

http://www.kuaipan.cn/file/id_35241628297855052.html

(拓扑排序下次再写吧)

小结:

DFS和BFS是图算法的根本,但是刚开始了解可能不太习惯,建议找一些相应的题目来试试手。可以在我Blog搜BFS和DFS,可以找到我曾经做过的题目。

 

DATE: 2012.1.6 @ Home By Tanky Woo

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《《算法导论》学习总结 — XX.第22章 图的基本算法》有931个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注