数据结构基础图的遍历（一）之 DFS

谁借莪１个温暖的怀抱￠ 2022-08-02 05:54 170阅读 0赞

*  **图的遍历**

> 图的遍历是指从图中的某一顶点出发，按照一定的策略访问图中的每一个顶点。当然，每个顶点有且只能被访问一次。在图的遍历中，深度优先和广度优先是最常使用的两种遍历方式。这两种遍历方式对无向图和有向图都是适用的，并且都是从指定的顶点开始遍历的。

*  **深度优先遍历**

> 深度优先遍历也叫深度优先搜索(Depth First Search)。它的遍历规则：不断地沿着顶点的深度方向遍历。顶点的深度方向是指它的邻接点方向。具体点，给定一图G=<V,E>，用visited\[i\]表示顶点i的访问情况，则初始情况下所有的visited\[i\]都为false。假设从顶点V0开始遍历，则下一个遍历的顶点是V0的第一个邻接点Vi，接着遍历Vi的第一个邻接点Vj，…… 直到所有的顶点都被访问过。 所谓的第一个是指在某种存储结构中(邻接矩阵、邻接表)，所有邻接点中存储位置最近的，通常指的是下标最小的。

*  **在遍历的过程中有两种情况经常出现下列两种特殊情况**

> 1.某个顶点的邻接点都已被访问过的情况，此时需回溯已访问过的顶点。  
> 2.图不连通，所有的已访问过的顶点都已回溯完了，仍找不出未被访问的顶点。此时需从下标0开始检测visited\[i\]，找到未被访问的顶点i，从i开始新一轮的深度搜索。

*  **遍历分析**

> 以下图为例从V0开始遍历

![Center][]

> V0有两个邻接点V1和V2，选择下标最小的V1遍历。接着从V1开始深度遍历，V1只有邻接点V3，也就是没有选择的，遍历V3。接着从V3开始遍历，V3只有邻接点V0，而V0已经被遍历过。此时出现了上面提到的情况一，开始回溯V1，V1无未被遍历的邻接点，接着回溯V0，V0有一个未被遍历的邻接点V2，新的一轮深度遍历从V2开始。V2无邻接点，且无法回溯。此时出现了情况二，检测visited\[i\]，只有V4了。深度遍历完成。看到回溯，应该可以想到需要使用栈。

> 遍历序列 V0->V1->V3->V2->V4。

> 从其它顶点出发的深度优先遍历序列是：

> > V1->V3->V0->V2->V4。
> 
> > V2->V0->V1->V3->V4。
> 
> > V3->V0->V1->V2->V4。
> 
> > V4->V2->V0->V1->V3。

*  **源码实现**

**【代码思想】**

> **从某一指定点出发，找它的相邻顶点，如果遇到相邻点访问完毕，但是，访问顶点数未到达图中顶点总数时，则回溯至上一顶点，查找相应邻接点，有则向下无则回溯，至**访问顶点数到达图中顶点总数时停止。

**【代码示例】**

/* 邻接矩阵的深度优先递归算法 */  
    void DFS(MGraph G, int i)  
    {  
        int j;  
        visited[i] = TRUE;  
        printf("%c ", G.vexs[i]);/* 打印顶点，也可以其它操作 */  
        for(j = 0; j < G.numVertexes; j++)  
            if(G.arc[i][j] == 1 && !visited[j])  
                DFS(G, j);/* 对为访问的邻接顶点递归调用 */  
    }  
      
    /* 邻接矩阵的深度遍历操作 */  
    void DFSTraverse(MGraph G)  
    {  
        int i;
        for(i = 0; i < G.numVertexes; i++)  
            visited[i] = FALSE; /* 初始所有顶点状态都是未访问过状态 */  
        for(i = 0; i < G.numVertexes; i++)  
            if(!visited[i]) /* 对未访问过的顶点调用DFS，若是连通图，只会执行一次 */   
                DFS(G, i);  
    }

/* 邻接表的深度优先递归算法 */  
    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 < GL->numVertexes; i++)  
            visited[i] = FALSE; /* 初始所有顶点状态都是未访问过状态 */  
        for(i = 0; i < GL->numVertexes; i++)  
            if(!visited[i]) /* 对未访问过的顶点调用DFS,若是连通图,只会执行一次 */   
                DFS(GL, i);  
    }

**【指针范例（不推荐）】**

/*深度优先搜索 
    从vertex开始遍历，visit是遍历顶点的函数指针 
    */  
    void Graph::dfs(int vertex, void (*visit)(int))  
    {  
        stack<int> s;  
        //visited[i]用于标记顶点i是否被访问过  
        bool *visited = new bool[numV];  
        //count用于统计已遍历过的顶点数  
        int i, count;  
        for (i = 0; i < numV; i++)  
            visited[i] = false;  
        count = 0;  
        while (count < numV)  
        {  
            visit(vertex);  
            visited[vertex] = true;  
            s.push(vertex);  
            count++;  
            if (count == numV)  
                break;  
            while (visited[vertex])  
            {  
                for (i = 0; i < numV  
                    && (visited[i]   
                    || matrix[vertex][i] == 0 || matrix[vertex][i] == MAXWEIGHT); i++);  
                if (i == numV)  //当前顶点vertex的所有邻接点都已访问完了  
                {  
                    if (!s.empty())  
                    {  
                        s.pop();   //此时vertex正是栈顶，应先出栈  
                        if (!s.empty())  
                        {  
                            vertex = s.top();  
                            s.pop();  
                        }  
                        else  //若栈已空，则需从头开始寻找新的、未访问过的顶点  
                        {  
                            for (vertex = 0; vertex < numV && visited[vertex]; vertex++);  
                        }  
                    }  
                    else  //若栈已空，则需从头开始寻找新的、未访问过的顶点  
                    {  
                        for (vertex = 0; vertex < numV && visited[vertex]; vertex++);  
                    }  
                }  
                else  //找到新的顶点应更新当前访问的顶点vertex  
                    vertex = i;  
            }  
        }  
        delete[]visited;  
    }  
    void visit(int vertex)  
    {  
        cout << setw(4) << vertex;  
    }  
    int main()  
    {  
        cout << "******图的遍历：深度优先、广度优先***by David***" << endl;  
        bool isDirected, isWeighted;  
        int numV;  
        cout << "建图" << endl;  
        cout << "输入顶点数 ";  
        cin >> numV;  
        cout << "边是否带权值，0(不带) or 1(带) ";  
        cin >> isWeighted;  
        cout << "是否是有向图，0(无向) or 1(有向) ";  
        cin >> isDirected;  
        Graph graph(numV, isWeighted, isDirected);  
        cout << "这是一个";  
        isDirected ? cout << "有向、" : cout << "无向、";  
        isWeighted ? cout << "有权图" << endl : cout << "无权图" << endl;  
        graph.createGraph();  
        cout << "打印邻接矩阵" << endl;  
        graph.printAdjacentMatrix();  
        cout << endl;  
        cout << "深度遍历" << endl;  
        for (int i = 0; i < numV; i++)  
        {  
            graph.dfs(i, visit);  
            cout << endl;  
        }  
        cout << endl;  
        cout << "广度遍历" << endl;  
        for (int i = 0; i < numV; i++)  
        {  
            graph.bfs(i, visit);  
            cout << endl;  
        }  
        system("pause");  
        return 0;  
    }

【源码详址】

http://blog.csdn.net/manoel/article/details/16119969

http://blog.csdn.net/zhangxiangDavaid/article/details/38323633

[Center]: /images/20220731/cef2e804d8a84a4c86e45035c5a9e8a7.png