广度优先搜索

广度优先搜索

#include "graph.hpp"
#include <list>

void bfs(Node *node)
{
    if (node == nullptr)
    {
        return;
    }
    // queue<Node*, list<Node*>> que;
    queue<Node *> que;
    unordered_set<Node *> hashset;
    que.push(node);
    hashset.insert(node);
    while (!que.empty())
    {
        Node *cur = que.front();
        que.pop();
        // todo
        cout << cur->value << endl;
        for (auto &next : cur->nexts)
        {
            if (hashset.find(next) == hashset.end())
            {
                hashset.insert(next);
                que.push(next);
            }
        }
    }
}

int main()
{

    return 0;
}

拓扑排序

#include "graph.hpp"
#include <list>
#include <stdlib.h>
#include <crtdbg.h>

vector<vector<Node *>> sortedTopology(Graph *graph)
{
    // key: 某一个node， value: 剩余的入度
    unordered_map<Node *, int> inMap;
    // 入度为 0 的 node 才能进这个队列
    queue<Node *> zeroInQue;
    for (auto &node : graph->nodes)
    {
        inMap[node.second.get()] = node.second.get()->in;
        if (node.second.get()->in == 0)
        {
            zeroInQue.push(node.second.get());
        }
    }

    // count1 表示批量编译了几次；count2 表示总共有多少文件被成功编译了
    // 如果 count2 != graph->nodes.size() 则说明图中存在环（ps：隔离开的两个图也是能编译的）
    int count1 = 0, count2 = 0;
    // 拓扑排序的结果放入result
    vector<vector<Node *>> result;
    while (!zeroInQue.empty())
    {
        int size = zeroInQue.size();
        result.push_back(vector<Node*>());
        while (size--)
        {
            Node *cur = zeroInQue.front();
            zeroInQue.pop();
            result[count1].push_back(cur);
            count2++;
            for(auto & next : cur->nexts)
            {
                if(--inMap[next] == 0)
                {
                    zeroInQue.push(next);
                }
            }
        }
        count1++;
    }

    if (count2 != graph->nodes.size())
    {
        cout << "There is a cyclic dependency" << endl;
    }
    
    return result;
}

void test1()
{
    // vector<vector<int>> matrix = {{1, 1, 2}, {1, 2, 3}, {1, 3, 4}, {1, 1, 5}, {1, 1, 3}, {1, 2, 4}};
    vector<vector<int>> matrix = {{1, 1, 2}, {1, 2, 3}, {1, 3, 4}, {1, 1, 5}, {1, 1, 3}, {1, 4, 2}};

    shared_ptr<Graph> graph = creatGraph(matrix);
    vector<vector<Node *>> res = sortedTopology(graph.get());
}


int main()
{
    test1();
    _CrtDumpMemoryLeaks();	//检测内存泄露

    return 0;
}