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.测试结果