图的深度优先遍历(DFS) 与 广度优先遍历(BFS)

发表于 更新于 分类于 ，
本文字数： 2.8k

DFS —— 在一条路上一路到底的遍历

BFS —— 层层递进的遍历

数据结构课代码实现 之 深度优先遍历(DFS) 与 广度优先遍历(BFS)

简要理解

附之前的三篇文章：

DFS（深度优先遍历） 与 BFS（广度优先遍历）

DFS经典问题

BFS经典问题

代码实现

这里提供的代码默认都是从 0 号地址的结点开始的，请自行修改

请区分点的 地址 与 储存的数据！

邻接表存图

BFS

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
bool visited[MAX_VERTEX_NUM];

void visit(ALGraph g, int i)
{
    cout << "BFS顺序遍历下当前点的储存值为："; 
    cout << g.vertices[i].data << endl;
}

void BFSTraverse(ALGraph G)
{
    for(int i = 0;i < G.vexnum;i++)
        visited[i] = false;
    queue<ArcNode *> q;
    for(int i = 0;i < G.vexnum;i++)
    {
        if(!visited[i])
        {
            visited[i] = true;
            visit(G, i);
            if(G.vertices[i].firstarc != NULL)
                q.push(G.vertices[i].firstarc);
            while(!q.empty())
            {
                ArcNode* t = q.front();
                q.pop();
                for(int j = t->adjvex;t->nextarc != NULL;t = t->nextarc, j = t->adjvex)
                {
                    if(!visited[j])
                    {
                        visited[j] = true;
                        visit(G, j);
                        q.push(G.vertices[j].firstarc);
                    }
                }
            }
        }
    }
}

int main()
{
    ALGraph g;
    CreateGraph(g);
    BFSTraverse(g);   
	return 0;
}

DFS

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
bool visited[MAX_VERTEX_NUM];

void visit(ALGraph g, int i)
{
    cout << "DFS顺序遍历下当前点的储存值为： "; 
    cout << g.vertices[i].data << endl;
}

void DFS(ALGraph g, int i)
{
    visited[i] = true; 
    visit(g, i);
    int j;
    ArcNode* k;
    for(j = g.vertices[i].firstarc->adjvex, k = g.vertices[i].firstarc;k->nextarc != NULL;k = k->nextarc, j = k->adjvex)
        if(!visited[j])
			DFS(g, j);
}

void DFSTraverse(ALGraph g)
{
    for(int i = 0;i < g.vexnum;i++)
        visited[i] = false;
    for(int i = 0;i < g.vexnum;i++)
        if(!visited[i])
            DFS(g, i);
}

int main()
{
    ALGraph g;
    CreateGraph(g);
    DFSTraverse(g);   
	return 0;
}

邻接矩阵存图

BFS

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
bool visited[MAX_VERTEX_NUM];

void visit(MGraph g, int i)
{
    cout << "BFS顺序遍历下当前点的储存值为： "; 
    cout << g.vexs[i] << endl;
}

void BFSTraverse(MGraph G)
{
    for(int i = 0;i < G.vexnum;i++) 
        visited[i] = false;
    queue<int> q;
    for(int i = 0;i < G.vexnum;i++)
    {
        if(!visited[i])
        {
            visited[i] = true;
            visit(G, i);
            q.push(i);
            while(!q.empty())
            {
                int t = q.front();
                q.pop();
                for(int j = 0;j < G.vexnum;j++)
                {
                    if(G.arcs[t][j].adj != INFINITY && !visited[j])
                    {
                        visited[j] = true;
                        visit(G, j);
                        q.push(j);
                    }
                }
            }
        }
    }
}

int main()
{
    MGraph a;
    CreateGraph(a);
    BFSTraverse(a);
    return 0;
}

DFS

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
bool visited[MAX_VERTEX_NUM];

void visit(MGraph g, int i)
{
    cout << "DFS顺序遍历下当前点的储存值为： "; 
    cout << g.vexs[i] << endl;
}

void DFS(MGraph G, int i)
{
    visited[i] = true;
    visit(G, i);
    int j = 0;
    for(int k = 0;k < G.vexnum;k++)
        if(!visited[k] && G.arcs[i][k].adj != INFINITY)
            DFS(G, k);
}

void DFSTraverse(MGraph &G)
{
    for(int i = 0;i < G.vexnum;i++)
        visited[i] = false;
    for(int i = 0;i < G.vexnum;i++)
        if(!visited[i])
            DFS(G, i);
}

int main()
{
    MGraph a;
    CreateGraph(a);
    DFSTraverse(a);
    return 0;
}