图的构建

图的构建

graph.hpp

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <memory>
#include <vector>
#include <set>
#include <queue>
using namespace std;

class Edge;
class Node
{
public:
    int value;
    // in表示一个点的入度，表示有多少个有向边的箭头指向它
    unsigned int in;
    // out表示一个点的出度，表示有多少个边是从这个点指向外面的
    unsigned int out;
    vector<Node*> nexts;
    vector<Edge*> edges;

public:
    Node(int val)
    {
        this->value = val;
        in = 0;
        out = 0;
        nexts = vector<Node*>();
        edges = vector<Edge*>();
    }
    ~Node()
    {
        nexts.clear();
        edges.clear();
    }
};

class Edge
{
public:
    int weight;
    Node* from;
    Node* to;
    Edge(int wei, Node* f, Node* t)
    {
        this->weight = wei;
        this->from = f;
        this->to = t;
    }
    Edge(Node* f, Node* t)
    {
        this->from = f;
        this->to = t;
    }
    ~Edge()
    {
    }
};

class Graph
{
public:
    // 把所有的点集和边集合都委托给Graph结构来管理
    unordered_map<int, shared_ptr<Node>> nodes;
    unordered_set<shared_ptr<Edge>> edges;
    Graph()
    {
        nodes = unordered_map<int, shared_ptr<Node>>();
        edges = unordered_set<shared_ptr<Edge>>();
    }
    ~Graph()
    {
        nodes.clear();
        edges.clear();
    }
};

// matrix 每一行表示图中的边
// 必须为N*3的矩阵
// [weight, fromNode, toNode]
std::shared_ptr<Graph> creatGraph(vector<vector<int>>& matrix)
{
    // shared_ptr<Graph> graph = make_shared<Graph>(Graph());
    shared_ptr<Graph> graph = shared_ptr<Graph>(new Graph());
    for (int i = 0; i < matrix.size(); i++)
    {
        int weight = matrix[i][0];
        int from = matrix[i][1];
        int to = matrix[i][2];
        if (graph.get()->nodes.find(from) == graph.get()->nodes.end())
        {
            graph.get()->nodes[from] = shared_ptr<Node>(new Node(from));
        }
        if (graph.get()->nodes.find(to) == graph.get()->nodes.end())
        {
            graph.get()->nodes[to] = shared_ptr<Node>(new Node(to));
        }
        Node* fromNode = graph.get()->nodes[from].get();
        Node* toNode = graph.get()->nodes[to].get();
        shared_ptr<Edge> newEdge = shared_ptr<Edge>(new Edge(weight, fromNode, toNode));
        fromNode->nexts.emplace_back(toNode);
        fromNode->out++;
        toNode->in++;
        fromNode->edges.emplace_back(newEdge.get());
        graph.get()->edges.insert(newEdge);
    }
    // new int(1);
    // 0 内存泄漏！！！
    return graph;
}

测试

testGraph.cpp

#include "graph.hpp"

#include <iostream>
#include <stdlib.h>
#include <crtdbg.h>

int main()
{
    vector<vector<int>> matrix = { {3, 0, 2}, {7, 1, 2} };
    shared_ptr<Graph> graph = creatGraph(matrix);
    cout << graph.get()->nodes[1].use_count() << endl;

    graph.reset();

    cout << graph.get()->nodes[1].use_count() << endl;

    _CrtDumpMemoryLeaks();	//检测内存泄露

    system("pause");
    return 0;
}

graph

shared_ptr

使用 shared_ptr 可以避免许多内存泄漏的情况，但不是所有情况都能解决。shared_ptr 依赖于引用计数技术，它会记录指向对象的指针数量，当数量为 0 时自动删除对象。但是，在某些情况下仍然可能发生内存泄漏。以下是可能会导致内存泄漏的情况：

循环引用。如果你的对象存在循环引用，即使你使用 shared_ptr，也可能会发生内存泄漏。例如，如果对象A中包含一个 std::shared_ptr<B>，而对象B中包含一个 std::shared_ptr<A>，那么当你删除对象A和B时，它们之间互相持有的指针数量永远不会变成 0，从而导致内存泄漏。

基类和派生类之间的显式指针。如果你使用了基类和派生类之间的显式指针，可能会导致内存泄漏，因为引用计数技术无法追踪这些指针。例如，如果你使用了一个 std::shared_ptr<A>，并将其指向了派生类B的实例，那么当你删除该 shared_ptr 时，B 对象中的成员变量仍然可能包含指向 A 对象的指针，从而导致内存泄漏。

自定义删除器。 如果你使用 shared_ptr 自定义了删除器，那么你需要确保你的删除器适当地清理了指针持有的资源。否则，你可能会在删除对象时发生内存泄漏。

shared_ptr 和 new[] 的组合。 如果你使用了 std::shared_ptr 来管理一个使用 new[] 分配的数组，你需要使用 std::shared_ptr 提供的定制删除器，以避免内存泄漏。原因是 std::shared_ptr 并不知道它指向的是一个数组，而 delete 只能删除由 new 分配的单个对象。

总之，虽然 std::shared_ptr 可以减少内存泄漏的情况，但并不能完全避免。你需要注意以避免上述情况，从而减少内存泄漏的发生。如果你使用 _CrtDumpMemoryLeaks 或其他工具来检测内存泄漏，你应该注意该工具是否对 std::shared_ptr 的使用进行了正确的跟踪。

_CrtDumpMemoryLeaks

_CrtDumpMemoryLeaks 是 VC++ 提供用于检测内存泄漏的函数，它是定义在 crtdbg.h 头文件中的。

在 C/C++ 语言开发中，内存泄漏是一种很严重的问题。某些情况下，程序员开发的代码中申请了内存空间但没有释放，导致内存泄漏的情况出现。内存泄漏会导致程序运行变慢，有时还会引发崩溃、卡死等问题。

为了及时发现和解决内存泄漏问题，可以使用 _CrtDumpMemoryLeaks 函数来检测有没有内存泄漏。使用该函数时，需要包含 crtdbg.h 头文件，并将_CRTDBG_LEAK_CHECK_DF 宏设置为 _CrtSetDbgFlag 函数的参数，然后程序运行结束后就会在调试输出中显示内存泄漏的信息。如下所示：

#define _CRTDBG_MAP_ALLOC
#include <stdlib.h>
#include <crtdbg.h>

int main()
{
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
    // do something
    _CrtDumpMemoryLeaks();
    return 0;
}

最小生成树

k算法和p算法都是仅仅针对无向图的算法

kruskal 算法

算法思想和证明方式

k算法：每次选择权值最小的边，如果不存在环，则收集。否者进入下一次循环选择权值最小的边。直到所有的边都遍历过一遍。 那么如果判断是否存在环，用并集技巧。

prim 算法

K算法可能有一个集合被吞入另一个集合的情况，谁被吞不确定，但P算法只有一个大集合

就是k算法可能有一个一个点往集合里加的情况，也可能有一片一片的加的情况

Dijkstra

从规定的出发节点到所有节点的最短路径

适用范围：不能有累加和为负数的环