算法导论—无向图的遍历(BFS+DFS，MATLAB)

华电北风吹
天津大学认知计算与应用重点实验室
最后修改日期：2015/8/22

无向图的存储方式有邻接矩阵，邻接链表，稀疏矩阵等。无向图主要包含两方面内容，图的遍历和寻找联通分量。

一、无向图的遍历
无向图的遍历有两种方式—广度优先搜索(BFS)和深度优先搜索(DFS)。广度优先搜索在遍历一个顶点的所有节点时，先把当前节点所有相邻节点遍历了，然后遍历当前节点第一个相邻的节点的所有相邻节点，广度优先搜索使用队列来实现。深度优先搜索在遍历当前节点的所有相邻节点时，先对当前节点的第一个相邻节点进行访问，然后遍历第一个相邻节点的相邻节点，依次递归，因此深度优先搜索使用栈实现。

1、BFS图遍历代码：

function result=BFSTraversal(startNode,Graph)

% 广度优先搜索
% Graph 图连通矩阵
[m n]=size(Graph);
nodelist=zeros(m,1);
queue=startNode;
nodelist(startNode)=1;
result=startNode;
while isempty(queue)==false
    i=queue(1);
    queue(1)=[];
    for j=1:n
        if(Graph(i,j)>0&&nodelist(j)==0&&i~=j)
            queue=[queue;j];
            nodelist(j)=1;
            result=[result;j];
        end
    end
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2、DFS图遍历代码

function result=DFSTraversal(startNode,Graph)

global nodelist
m=size(Graph,1);
nodelist=zeros(m,1);
result=DFSRecursion(startNode,Graph);
1
2
3
4
5
6

function result=DFSRecursion(startNode,Graph)

global nodelist

nodelist(startNode)=1;
result=[startNode];
n=size(Graph,2);
for j=1:n
    if(Graph(startNode,j)>0&&nodelist(j)==0&&startNode~=j)
        result=[result DFSRecursion(j,Graph)];
    end
end
1
2
3
4
5
6
7
8
9
10
11
12

二、寻找联通分量
寻找联通分量的方法就是把一个节点的所有相邻节点找出来，然后再在未访问过的节点中选择一个节点用遍历方法寻找相邻节点。

1、基于BFS的寻找联通分量代码：

function resultSet=BFSDivideGraph(Graph)
% 连通分量(广度优先搜索)
% Graph 图连通矩阵,无向图，对称矩阵
resultSet=[];
[m n]=size(Graph);
nodelist=zeros(m,1);
p=1;
for k=1:m
    if(nodelist(k)==0)
        startNode=k;
        queue=startNode;
        nodelist(startNode)=1;
        result=startNode;
        while isempty(queue)==false
            i=queue(1);
            queue(1)=[];
            for j=1:n
                if(Graph(i,j)>0&&nodelist(j)==0&&i~=j)
                    queue=[queue;j];
                    nodelist(j)=1;
                    result=[result;j];
                end
            end
        end
        resultSet(p).graph=result;
        p=p+1;
    end
end
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

2、基于BFS的寻找联通分量代码：
在访问记录链表中选择未访问过的节点作为深度优先搜索的起点直到所有节点都被访问过即可。

三、图的高级应用
1、BFS
最短路径(Dijkstra)，最小生成树(Prim)，拓扑排序

2、DFS
拓扑排序，强连通分量

本文代码基于邻接矩阵实现。