MENU

搜索(1)

June 23, 2018 • Read: 329 • 算法

图的存储

在讨论图的遍历问题之前,我们先来讨论一下图的存储问题,也就是我们在写程序的时候如何保存、表示一个图。首先我们会用连续的整数编号来表示点集。比如1号顶点、2号顶点……

其次,我们有两种方法表示边集。一种叫做邻接矩阵表示法,另一种叫邻接表表示法

邻接矩阵是说我们用一个二维矩阵A来表示边集。A~ij~=0表示顶点i和顶点j之间不存在边,A~ij~=1表示顶点i和顶点j之间存在边。例如:
image
除了邻接矩阵表示法以外,我们还有一种表示法叫邻接表表示法。图中的每一个顶点i都有一个线性表,保存与i相连的顶点编号
image
在程序中,一般用一个数组嵌套vector的方法来表示邻接表:vector<int> g[N+1]。g[i]是一个vector,可以想象成一个变长数组,里面保存着每一个与i相邻的顶点编号。比如与1相连的有2,3,4,在程序中就有g1 = 2, g1=3, g1=4

图的遍历

假设这个图是这样:
image
搜索需要一个起点,我们不妨设从1号顶点起始。在搜索过程中,我们维护一个布尔数组bool visited[N+1],这个数组用来表示每个顶点是不是已经遍历过了。visited[i]=true表示顶点i已经遍历过了,visited[i]=false表示i还没有遍历过。DFS一般我们可以用递归实现,如果采用邻接矩阵,伪代码如下:

Visited[] = {FALSE,FALSE,...FASLE}
Visited[x] = TRUE
For i = 1...N
    If !Visited[i] AND A[x][i]
        DFS(i)

当我们执行DFS(1)的时候,程序就会开始从1号节点开始遍历。注意我们只会对visited[x]的值是FALSE的顶点x执行DFS(x),而执行DFS(x)的第一句就是令Visited[x]=TRUE,所以对于N个顶点的图,DFS函数最多被调用N次。而每一次DFS执行中都要i循环从1到N遍历一遍。所以整个复杂度是O(N^2)
如果采用邻接表,伪代码如下:

Visited[] = {FALSE,FALSE,...FALSE}
Visited[x] = TURE
For i in g[x]
    If !Visited[i]
        DFS(i)

因为g[x]中直接保存了与x相连的顶点编号,所以循环For i in g[x]:中直接i就是x的邻居顶点。用邻接表的复杂度是O(N+M)的,其中M是图的边数

对于上图来说,深度优先搜索的过程是这样的
image
红色的边代表DFS的调用关系,一开始是DFS(1)->DFS(2)->DFS(3)->DFS(4)。执行DFS(4)的时候会发现没有可以继续DFS的顶点,会回溯到DFS(3)。DFS(3)也回溯到DFS(2),DFS(2)会再回溯到DFS(1)。DFS(1)继续执行会调用DFS(1)->DFS(5)->DFS(6)。最后再从DFS(6)回溯到DFS(1),结束遍历

下面我们来通过一道题,写一个DFS完整的程序
image
这道题的基本思路就是从1号节点出发开始遍历。如果遍历结束时所有visited[]数组的值全都是true,那么就说明整个图是连通的,否则就不是。代码如下:

#include <iostream>
#include <vector>
using namespace std;
int n,m;
vector<int> g[100001];
bool visited[100001],ans;
void dfs(int x)
{
    visited[x] = true;
    for(int i : g[x])
        if(!visited[i])
            dfs(i);
}
int main()
{
    cin >> n >> m;
    for(int i = 0;i < n;i++)
        visited[i] = false;
    for(int i = 0;i < m;i++)
    {
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);    
    }
    dfs(1);
    ans = true;
    for(int i = 1;i <= n;i++)
        ans = ans && visited[i];
    if(ans)
        cout << "YES" << endl;
    else
        cout << "NO" << endl; 
    return 0;
} 

第16行是读入顶点数和边数。第18行是初始化visited数组。第19到第25行是在读入边集数据,并保存在邻接表里。这里读入边的时候需要注意一些细节

一是重边的问题,也就是输入数据会不会有一条边出现了1次以上。比如u=1, v=2有一行,u=2,v=1也有一行。重边在某些情况下是需要特殊处理的,比如去掉重边只保留一条。在这道题中重边不会影响程序的正确性,所以我们没有去重

二是自环的问题,也就是输入数据会不会有u=v这样数据。与重边类似,自环在某些情况下也是要特殊处理的。不过在我们这道题中自环仍是无所谓,所以我们也没有处理

第26行dfs(1)就是从1开始进行深度优先搜索。Dfs函数在第7-13行,比较简单明了。首先是第9行将当前顶点x标记为已经访问过的。然后就是10~12行,对于所有在g[x]中的顶点i,也就是与x相邻的顶点,如果i还没有被访问过,就递归执行dfs(i)

第26行dfs(1)函数返回之后,与1直接或者间接相连的顶点x就应该都被标记为已经访问过(visited[x]=true)。第28-29行我们在检查visited[1-N]是不是都是true,其实就是检查顶点1~N是不是都被访问过了。根据结果输出答案

最后编辑于: October 19, 2018
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment