Day22-图算法-图的深搜和宽搜

BUPTrenyi

发布于 2019-07-15 09:03:32

81800

代码可运行

文章被收录于专栏：算法其实很好玩算法其实很好玩

运行总次数：0

代码可运行

一唠嗑

更两篇文章着实有点累，今天偷个懒~

今天先更一下图算法的基础知识-宽搜和深搜

二问题来了

Q：给定一个图，给出图的深度优先搜索和宽度优先搜索结果。

三讲一讲

图有邻接矩阵和邻接表两种表示方法，我在下面写的是邻接表。

概念解释

深度优先搜索：

从图中某个顶点V出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发，深度优先搜索遍历图，直至图中所有和V有路径相通，且未被访问的顶点，都被访问到。若此时还有其他顶点未被访问到，就选一个未被访问的顶点，重复上述过程。

宽度优先搜索：（类似于二叉树的层次遍历，利用队列）

从图中某个顶点V出发，在访问了V之后，依次访问V的各个未被访问的邻接点，然后分别从这些邻接点出发，依次访问他们的邻接点。并保证，先被访问的顶点的邻接点，要先于，后被访问的顶点的邻接点被访问。直至图中已被访问的顶点的邻接点，全被访问到。若此时还有其他顶点未被访问到，就选一个未被访问的顶点，重复上述过程。

四完整代码及注释

//
// Created by renyi on 2019-07-10.
//
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

//图的顶点的数据结构
struct GraphNode{
    int value;
    vector<GraphNode*> neighbors;//相邻节点指针数组
    GraphNode(int v) : value(v) {};
};

//图的深度优先搜索
void depthFirstSearch(GraphNode* root, int visit[]){
    visit[root->value] = 1;//标记已经访问的图的顶点
    printf("%d ", root->value);
    for (int i = 0; i < root->neighbors.size(); i++) {//遍历该顶点相邻的，且未被访问的顶点
        if (visit[root->neighbors[i]->value] != 1){
            depthFirstSearch(root->neighbors[i], visit);
        }
    }
}

//图的宽度优先搜索
void breadthFirstSearch(GraphNode* root, int visit[]){
    queue<GraphNode*> q;
    q.push(root);
    visit[root->value] = 1;

    while (!q.empty()){
        GraphNode* node = q.front();
        q.pop();
        printf("%d ", node->value);
        for (int i = 0; i < node->neighbors.size(); i++) {
            if (visit[node->neighbors[i]->value] != 1){
                q.push(node->neighbors[i]);
                visit[node->neighbors[i]->value] = 1;
            }
        }
    }
}

int main(){
    const int maxN = 5;
    GraphNode* graph[maxN];//建立一个数组graph，存储图的各个顶点
    for (int i = 0; i < maxN; i++) {
        graph[i] = new GraphNode(i);
    }
    //有了5个顶点之后，开始按照配图连接边
    graph[0]->neighbors.push_back(graph[4]);
    graph[0]->neighbors.push_back(graph[2]);
    graph[1]->neighbors.push_back(graph[0]);
    graph[1]->neighbors.push_back(graph[2]);
    graph[2]->neighbors.push_back(graph[3]);
    graph[3]->neighbors.push_back(graph[4]);
    graph[4]->neighbors.push_back(graph[3]);

    int depthVisit[maxN] = {0};//建立数组，标记各个顶点是否被访问
    printf("深度优先搜索的结果是:\n");
    for (int i = 0; i < maxN; i++) {
        if (depthVisit[i] == 0){
            printf("第%d次加入的节点是: %d\n", i, graph[i]->value);
            printf("加入后遍历的结果是:\n");
            depthFirstSearch(graph[i], depthVisit);
            printf("\n");
        }
    }

    int breadthVisit[maxN] = {0};
    printf("宽度优先搜索的结果是:\n");
    for (int i = 0; i < maxN; i++) {
        if (breadthVisit[i] == 0){
            printf("第%d次加入的节点是: %d\n", i, graph[i]->value);
            printf("加入后遍历的结果是:\n");
            breadthFirstSearch(graph[i], breadthVisit);
            printf("\n");
        }
    }
    return 0;
}