【大话数据结构C语言】42 图的深度优先遍历

还是类比学习，这里使用树来对比

 

树因为根结点只有一个，并且所有的结点都只有一个双亲，所以不是很难理解

但是图就比较复杂了，原因是图的任一顶点都可以和其余的所有顶点相邻接，因此极有可能存在重复走过某个顶点或漏了某个顶点的遍历过程

 

因此就引出了图的遍历方法，大佬们设计了两种遍历次序方案： 深度优先遍历和广度优先遍历

 

深度优化遍历(DepthFirstSearch)，也有称为深度优化搜索，简称为DFS

它的具体思想类似于在家里找钥匙的方案，无论从哪一间房间开始都可以，将房间内的墙角、床头柜、床上、床下、衣柜、电视柜等挨个寻找，做到不放过任何一个死角，当所有的抽屉、储藏柜中全部都找遍，接着再寻找下一个房间

 

 

使用迷宫分析问题：

右手原则：

在没有碰到重复顶点的情况下， 分叉路口始终是向右手边走，每路过一个顶点就做一个记号右手原则：在没有碰到重复顶点的情况下，分叉路口始终是向右手边走，每路过一个顶点就做一个记号

 

其实深度优先遍历就是一个递归的思想

 

 

你可能发现整个过程是一个树的遍历，下边是遍历的过程

 

 

代码实现：

AdList_DFS.c

#define TRUE 1
#define FALSE 0
#define MAX 256

typedef int Boolean;    // 这里我们定义Boolean为布尔类型，其值为TRUE或FALSE
Boolean visited[MAX];   // 访问标志的数组

void DFS(GraphAdjList GL, int i)
{
    EdgeNode *p;
    
    visited[i] = TRUE;
    printf("%c " GL->adjList[i].data);
    p = GL->adjList[i].firstEdge;
    
    while(p)
    {
        if( !visited[p->adjvex] )
        {
            DFS(GL, p->adjvex);
        }
        p = p->next;
    }
}

// 邻接表的深度遍历操作
void DFSTraverse(GraphAdjList GL)
{
    int i;
    
    for( i=0; i numVertexes; i++ )
    {
        visited[i] = FALSE;     // 初始化所有顶点状态都是未访问过状态
    }
    
    for( i=0; i numVertexes; i++ )
    {
        if( !visited[i] )       // 若是连通图，只会执行一次
        {
            DFS(GL, i);
        }
    }
}

 

 

AdMatrix_DFS.c

#define TRUE 1
#define FALSE 0
#define MAX 256

typedef int Boolean;    // 这里我们定义Boolean为布尔类型，其值为TRUE或FALSE
Boolean visited[MAX];   // 访问标志的数组

void DFS(MGraph G, int i)
{
    int j;
    
    visited[j] = TRUE;          // 访问过的顶点设置为TRUE
    printf("%c ", G.vexs[i]);   // 打印顶点
    for( j=0; j