对于图的操作，最基本的就是对图的遍历了，图的遍历主要有两种思想，一种是DFS（Deepth First Search）深度优先遍历，另外一种是BFS（Breadth First Search）广度优先遍历
-
DFS
-
算法特点：DFS算法，从名字中就可以得出信息，深度优先的，那么在算法的执行过程中，总是将沿着一条路径一直深入，直到没有路径了再返回查看其他路径。可以看出，DFS算法是一种递归的过程，我们再联想到树的遍历中，其实DFS算法就是树的先序遍历。
-
算法具体代码：
int graph[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 0 },
{ 1, 1, 0, 0, 1 },
{ 0, 0, 1, 0, 0 }
};
int visited[N] = { 0, };
void DFS(int start)
{
visited[start] = 1;
for (int i = 0; i < N; i++)
{
if (!visited[i] && graph[start][i] == 1) // 找到相邻的点，同时这个点没有被访问过
DFS(i);
}
cout << start << " ";
}
int main()
{
for (int i = 0; i < N; i++)
{
if (!visited[i])
DFS(i);
}
return 0;
}
* 算法分析：由于是递归调用，那么每次递归都是一个单元，这个单元需要做的事情就是去找相邻的没有访问过的节点，对这个节点重复递归，而去寻找这样的节点就是递归的终止条件，即是如果没有找到这样的点，那么递归终止，返回上一层调用
* **非递归版**
* 具体代码：
int graph[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 0 },
{ 1, 1, 0, 0, 1 },
{ 0, 0, 1, 0, 0 }
};
int visited[N] = { 0, };
void DFS(int start)
{
stack<int> s; // 使用一个栈进行辅助
s.push(start);
visited[start] = 1;
bool isPush = false;
while (!s.empty())
{
isPush = false;
int v = s.top();
for (int i = 0; i < N; i++)
{
if (graph[v][i] == 1 && !visited[i])
{
visited[i] = 1;
s.push(i);
isPush = true;
break; // 找到了一个符合节点就先弹出当前位置
}
}
if (!isPush)
{
cout << v << " ";
s.pop();
}
}
}
int main()
{
for (int i = 1; i <= N; i++)
{
if (!visited[i])
DFS(i);
}
return 0;
}
* 算法分析：非递归的情况下，使用迭代的思想，需要借助一个栈去模拟递归的过程，然后用while循环进行控制，在非递归的情况下需要去手动加上两个东西：
* 终止条件：利用一个标记来作控制，用来控制找不到点的情况
* 栈行为：如果找到一个符合的点，那么就将其压入栈，并且弹出本次循环，如果遇到终止条件，那么就将目前的栈弹出一个
-
BFS
-
算法特点：BFS从字面上来理解就是广度搜索，与深度搜索不同的是，BFS会将每个节点的周围符合条件的节点都遍历之后才会继续向下遍历，BFS实际上和树的层序遍历很像。
-
算法实际代码：
int maze[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 1, 0 },
{ 0, 1, 1, 1, 0 },
{ 1, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 0 }
};
int visited[N + 1] = { 0, };
void BFS(int start)
{
queue<int> Q;
Q.push(start);
visited[start] = 1;
while (!Q.empty())
{
int front = Q.front();
cout << front << " ";
Q.pop();
for (int i = 1; i <= N; i++)
{
if (!visited[i] && maze[front - 1][i - 1] == 1)
{
visited[i] = 1;
Q.push(i);
}
}
}
}
int main()
{
for (int i = 1; i <= N; i++)
{
if (visited[i] == 1)
continue;
BFS(i);
}
return 0;
}
-
算法分析：
BFS实际上市借助了队列这种结构，对于每个节点，都将它相邻的同时符合条件的节点压入到队列中，然后在遍历完这个节点的时候就将这个节点给压出队列
