邻接矩阵无向图深度优先搜索

邻接矩阵实现的无向图深度优先搜索

Martix Graph:
0 0 1 1 0 1 0
0 0 1 0 0 0 0
1 1 0 1 0 0 0
1 0 1 0 0 0 0
0 0 0 0 0 0 1
1 0 0 0 0 0 1
0 0 0 0 1 1 0
DFS: A C B D F G E
BFS: A C D F B G E

邻接矩阵无向图

0	0	1	1	0	1	0
0	0	1	0	0	0	0
1	1	0	1	0	0	0
1	0	1	0	0	0	0
0	0	0	0	0	0	1
1	0	0	0	0	0	1
0	0	0	0	1	1	0

对上面的图G1进行深度优先遍历，从顶点A开始。
第1步：访问A。
代码实现：

// 初始化所有顶点都没有被访问
  for (i = 0; i < mVexNum; i++)
      visited[i] = 0; // 没有被访问的节点 置“0”。
// 开始遍历每一个顶点      
for (i = 0; i < mVexNum; i++)
    {
        //printf("\n== LOOP(%d)\n", i);
        if (!visited[i])
            DFS(i, visited);
    }
// 根据每个顶点的状态值 访问每个顶点
void MatrixUDG::DFS(int i, int *visited)
{
    int w;
    // 一但访问了 就会将顶点是否被访问过的状态数值设置为“1”
    visited[i] = 1;
    cout << mVexs[i] << " ";
    // 遍历该顶点的所有邻接顶点。若是没有访问过，那么继续往下走
    for (w = firstVertex(i); w >= 0; w = nextVertex(i, w))
    {
        if (!visited[w])
            DFS(w, visited);
    }  
}
// 遍历第一个顶点
int MatrixUDG::firstVertex(int v)
{
    int i;
    if (v<0 || v>(mVexNum-1))
        return -1;
    for (i = 0; i < mVexNum; i++)
    // 这句代码是关键 就是遍历某一行 编译顶点可到达的相邻顶点
        if (mMatrix[v][i] == 1)
            return i;
    return -1;
}

int MatrixUDG::nextVertex(int v, int w)
{
    int i;

    if (v<0 || v>(mVexNum-1) || w<0 || w>(mVexNum-1))
        return -1;

    for (i = w + 1; i < mVexNum; i++)
    //   if (mMatrix[v][i] == 1)这句代码找到和顶点相邻的顶点的时候，就以这个顶点为新的顶点继续 firstVertex(int v)找到之后再进行nextVertex。如此迭代下去，实现深度优先查找，联想一下广度优先就是遍历第一个顶点的所有节点，再往下遍历。
        if (mMatrix[v][i] == 1)
            return i;

    return -1;
}

第2步：访问(A的邻接点)C。
在第1步访问A之后，接下来应该访问的是A的邻接点，即"C,D,F"中的一个。但在本文的实现中，顶点ABCDEFG是按照顺序存储，C在"D和F"的前面，因此，先访问C。
第3步：访问(C的邻接点)B。
在第2步访问C之后，接下来应该访问C的邻接点，即"B和D"中一个(A已经被访问过，就不算在内)。而由于B在D之前，先访问B。
第4步：访问(C的邻接点)D。
在第3步访问了C的邻接点B之后，B没有未被访问的邻接点；因此，返回到访问C的另一个邻接点D。
第5步：访问(A的邻接点)F。
前面已经访问了A，并且访问完了"A的邻接点B的所有邻接点(包括递归的邻接点在内)"；因此，此时返回到访问A的另一个邻接点F。
第6步：访问(F的邻接点)G。
第7步：访问(G的邻接点)E。

因此访问顺序是：A -> C -> B -> D -> F -> G -> E