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

//
// 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;
}