图论基础——遍历图的DFS

1.问题分析：

 首先先介绍一下什么是图（graph）：简单大白话地说，图就是由一些小圆点（顶点）和一些把这些小圆点连接起来的直线（边）组成的，如图所示：

现在在我们要做的就是对这个图的所有顶点遍历一遍，也就是都访问一次。我们这里使用深度优先搜索来遍历这个图，会得到以下的结果：

遍历这个图的访问顺序如下：

每个顶点上面的红色数字代表这个顶点是第几个被访问的，我们称为时间戳

2.算法设计 

       深度优先搜索的主要思想就是：首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的的顶点：当没有未访问过的顶点时，则回到上一个顶点，继续试探访问别的顶点，直到所有的顶点都被访问过。

       显然，深度优先搜索是沿着图的某一条分支遍历直到末端，然后回溯，再沿着另一条进行同样的遍历，直到所有顶点都被访问过为止。我们依旧是使用一个二维数组edge来存储这个图的边：

图中二维数组i行j列表示的就是判断i跟j之间是否相连。1表示有边，∞表示没有边，自己到自己是不可达的，我们初始化为0。

接下来就是应用dfs进行遍历：

void dfs(int cur)
{
    cout << cur;
    sum++;
    if(sum==n)
    {
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(edge[cur][i]==1 && marked[i]==0)
        {
            marked[i]=1;
            dfs(i);
        }
    }
    return;
}

 

3.源代码 

 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int N=111;
const int INF=999999999;
int marked[N];//用来标记这个点有没有被遍历
int edge[N][N];//用来存储边
int sum;//记录遍历顶点的个数
int n;//点的个数
int m;//边的条数

void dfs(int cur)
{
    cout << cur;
    sum++;
    if(sum==n)
    {
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(edge[cur][i]==1 && marked[i]==0)
        {
            marked[i]=1;
            dfs(i);
        }
    }
    return;
}

int main()
{
    int point_a;
    int point_b;
    cout << "请输入顶点个数和边的条数：" << endl;
    cin >> n >> m;
    for (int i=1;i<=n;i++)//初始化
    {
        for (int j=1;j<=n;j++)
        {
            if(i==j)//自己不可达自己
            {
                edge[i][j]=0; //设置为0
            }
            else
            {
                edge[i][j]=INF; //不可达，设置为∞
            }
        }
    }
    cout << "请输入边的两点：" << endl;
    for(int i=1;i<=m;i++)
    {
        cin >> point_a >> point_b ;
        edge[point_a][point_b]=1;
        edge[point_b][point_a]=1;
    }
    cout << "遍历顺序是： "<< endl;
    marked[1]=1;
    dfs(1);
    return 0;
}

 

4.测试结果