啊哈，算法自学记——8th

图：
简单地说，图就是由一-些小圆点(称为顶点)和连接这些小圆点的直线(称为边)组成的。例如上图是由五个顶点(编号为1、2、3、4、5)和5条边(1-2、1-3、1-5、2-4、3-5)组成。

图中每个顶点右上方的数就表示这个顶点是第几个被访问到的，我们还为这个数起了很好听的名字一时间戳。

深度优先遍历的主要思想就是:
首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点:当没有未访问过的顶点时，则回到上-一个顶点，继续试探访问别的顶点，直到所有的顶点都被访问过。显然，深度优先遍历是沿着图的某一条 分支遍历直到末端，然后回溯，再沿着另- -条进行同样的遍历，直到所有的顶点都被访问过为止。
他访问的顺序依次是1-2-4-3-5

广度优先遍历的主要思想就是:
首先以一个未被访问过的顶点作为起始顶点，访问其所有相邻的顶点，然后对每个相邻的顶点，再访问它们相邻的未被访问过的顶点，直到所有顶点都被访问过，遍历结束。（像剥洋葱一样，一层一层遍历）
它访问的顺序依次是：1-2-3-5-4

图的存储：

上图二维数组中第i行第j列表示的就是顶点i到顶点j是否有边。1表示有边，∞表示没有边，这里我们将自己到自己(即i等于j)设为0。我们将这种存储图的方法称为图的邻接矩阵存储法。

深度优先搜索：

#include <stdio.h>

int book[101],sum,n,e[101][101];

void dfs(int cur)
{
    printf("%d ",cur);
    sum++;
    if(sum==n)return;
    for (int i = 1; i <= n; i++)
    {
        if (e[cur][i]==1 && book[i]==0)
        {
            book[i]=1;
            dfs(i);
        }
    }
    return;
}

int main(int argc, char const *argv[])
{
    int i,j,m,a,b;

    printf("Input the size of the map:
");
    scanf("%d %d",&n,&m);

    for (int i = 1; i <= n; i++)//初始化数组
    {
        for (int j = 1; j <= m; j++)
        {
            if(i==j)
                e[i][j]=0;//自己到自己的设为0
            else
            {
                e[i][j]=999999;//没有边的设为∞，用999999来代替
            }
            
        }
        
    }

    //读定点之间的边
    for (int i = 1; i <= m; i++)    
    {
        printf("Input a line:
");
        scanf("%d %d",&a,&b);
        e[a][b]=1;
        e[b][a]=1;//双向图所以e[b][a]=1
    }
    
    book[1]=1;//从一号位出发，标记一号位已经访问过
    dfs(1);

    return 0;
}

运行结果：

广度优先搜索：

#include <stdio.h>

int main(int argc, char const *argv[])
{
    int cur,a,b,m,n,e[101][101],book[101]={0};
    int que[10001],head,tail;

    printf("Input the size of the map:
");
    scanf("%d %d",&n,&m);

    for (int i = 1; i <= n; i++)//初始化数组
    {
        for (int j = 1; j <= m; j++)
        {
            if(i==j)
                e[i][j]=0;//自己到自己的设为0
            else
            {
                e[i][j]=999999;//没有边的设为∞，用999999来代替
            }
            
        }
        
    }

    //读定点之间的边
    for (int i = 1; i <= m; i++)    
    {
        printf("Input a line:
");
        scanf("%d %d",&a,&b);
        e[a][b]=1;
        e[b][a]=1;//双向图所以e[b][a]=1
    }

    //队列初始化
    head=1;
    tail=1;

    //从一号位出发
    que[tail]=1;//入队
    tail++;
    book[1]=1;//标记一号位已经遍历过

    while (head<tail)//队列不为空的时候循环 
    {
        cur=que[head];//当前正在访问的定点编号
        for (int i = 1; i <= n;  i++)//从1~n依次尝试
        {
            if (e[cur][i]==1 && book[i]==0)//如果有边并且没有遍历过
            {
                que[tail]=i;//加入队列
                tail++;
                book[i]=1;//标记
            }
            
            if(tail>n)//说明所有定点都别访问过了
                break;
        }
        head++;//当一个定点扩展后，head++才能继续向下扩展
    }
    
    printf("Result:
");
    for (int i = 1; i < tail; i++)
    {
        printf("%d ",que[i]);
    }
    
    return 0;
}

运行结果：