图

Graph

#include <cstdio>
#include <iostream>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <vector>
class Graph {
public:
  struct Node;
  struct Edge;
  struct liteUFDS;
  std::set<Edge *> edges;
  std::set<Node *> nodes;
  bool directed = true;
  /* std::map<Node *, liteUFDS *> UFDS; */

  struct Edge {
  public:
    int weight = 1;
    Node *from = NULL;
    Node *to = NULL;
  };
  struct Node {
    int value = 0;
    int ind = 0;
    int outd = 0;
    std::vector<Edge *> edges;
    std::vector<Node *> nodes;
  };
  // w from to
  Graph(int arr[][3], int n, bool directed = true) : directed(directed) {
    if (directed) {
      for (int i = 0; i < n; i++) {
        int w = arr[i][0], from = arr[i][1], to = arr[i][2];
        // if node not existed then new node
        Node *FNode = NULL;
        Node *TNode = NULL;
        for (auto it : nodes) {
          if (it->value == from) {
            FNode = it;
          }
          if (it->value == to) {
            TNode = it;
          }
          if (FNode && TNode) {
            break;
          }
        }
        if (!FNode) {
          FNode = new Node();
          FNode->value = from;
          nodes.insert(FNode);
        }
        if (!TNode) {
          TNode = new Node();
          TNode->value = to;
          nodes.insert(TNode);
        }
        // new edge
        Edge *edge = new Edge{w, FNode, TNode};
        edges.insert(edge);
        // update node
        FNode->outd++;
        FNode->nodes.push_back(TNode);
        FNode->edges.push_back(edge);
        TNode->ind++;
      }

    } else {
      for (int i = 0; i < n; i++) {
        int w = arr[i][0], from = arr[i][1], to = arr[i][2];
        // if node not existed then new node
        Node *FNode = NULL;
        Node *TNode = NULL;
        for (auto it : nodes) {
          if (it->value == from) {
            FNode = it;
          }
          if (it->value == to) {
            TNode = it;
          }
          if (FNode && TNode) {
            break;
          }
        }
        if (!FNode) {
          FNode = new Node();
          FNode->value = from;
          nodes.insert(FNode);
        }
        if (!TNode) {
          TNode = new Node();
          TNode->value = to;
          nodes.insert(TNode);
        }
        // new edge
        Edge *edge = new Edge{w, FNode, TNode};
        edges.insert(edge);
        // update node
        FNode->outd++;
        FNode->ind++;
        FNode->nodes.push_back(TNode);
        TNode->nodes.push_back(FNode);
        FNode->edges.push_back(edge);
        TNode->edges.push_back(edge);
        TNode->ind++;
        TNode->outd++;
      }
    }
  }
  void PrintEdges() {
    for (auto it : edges) {
      printf("%d----(%d)--->%d\n", it->from->value, it->weight, it->to->value);
    }
  }
  void BFS(Node *n) {
    // TODO 不连通图
    std::queue<Node *> q;
    std::set<Node *> s;
    q.push(n);
    s.insert(n);
    while (!q.empty()) {
      auto fn = q.front();
      /*Operation*/
      std::cout << "Value: " << fn->value << " Edges:";
      q.pop();
      for (auto it : fn->nodes) {
        std::cout << " " << it->value << " ";
        if (s.find(it) == s.end()) {
          s.insert(it);
          q.push(it);
        }
      }
      std::cout << std::endl;
    }
  }
  // TODO
  void DFS(Node *n) {}
  // 拓扑排序 如:编译依赖问题 栈/队列均可?
  void TPsort() {
    std::map<Node *, int> inMap;
    std::queue<Node *> q;
    for (auto it : nodes) {
      inMap.insert(std::pair<Node *, int>(it, it->ind));
      if (!it->ind) {
        q.push(it);
      }
    }
    while (!q.empty()) {
      Node *fq = q.front();
      q.pop();
      std::cout << fq->value << std::endl;
      for (auto it : fq->nodes) {
        if (!--inMap.find(it)->second) {
          q.push(it);
        }
      }
    }
  }
  // TODO 最小生成树,无向连通图,权最小,并查集简化
  // kruskal
  void kruskalMST() {
    for (auto it : nodes) {
      new liteUFDS(it);
    }
    /* liteUFDS::PrintUFDS(); */
    struct CompareByWeight {
      bool operator()(Edge *a, Edge *b) { return a->weight > b->weight; }
    };
    std::vector<Edge *> edgesv =
        std::vector<Edge *>(this->edges.begin(), this->edges.end());
    std::priority_queue<Edge *, std::vector<Edge *>, CompareByWeight> pq(
        edgesv.begin(), edgesv.end());
    while (!pq.empty()) {
      auto front = pq.top();
      pq.pop();
      if (liteUFDS::isInTheSameUFDS(front->to, front->from)) {
        continue;
      } else {
        liteUFDS::Union(front->to, front->from);
        /* std::cout << "UNION: " << front->to->value << " " <<
           front->from->value
                  << std::endl; */
        /* liteUFDS::PrintUFDS(); */
        std::cout << front->from->value << "----(" << front->weight << ")---->"
                  << front->to->value << std::endl;
      }
    }
  }
  struct liteUFDS {
    static std::map<Node *, liteUFDS *> UFDS;
    std::set<Node *> *nodes;
    liteUFDS(Node *n) : nodes(new std::set<Node *>{n}) {
      UFDS.insert(std::pair<Node *, liteUFDS *>(n, this));
      /* std::cout << "new UFDS: " << n->value << " " << this << std::endl; */
    }
    static bool isInTheSameUFDS(Node *a, Node *b) {
      return UFDS.find(a)->second == UFDS.find(b)->second;
    }
    static void Union(Node *a, Node *b) {
      auto s1 = UFDS.find(a)->second;
      auto s2 = UFDS.find(b)->second;
      auto min = s1->nodes->size() < s2->nodes->size() ? s1 : s2;
      auto max = s1->nodes->size() < s2->nodes->size() ? s2 : s1;
      for (auto it : *min->nodes) {
        max->nodes->insert(it);
        UFDS.find(it)->second = max;
      }
    }
    static void PrintUFDS() {
      for (auto it : UFDS) {
        std::cout << it.first->value << " " << it.second << std::endl;
      }
    }
  };
};
std::map<Graph::Node *, Graph::liteUFDS *> Graph::liteUFDS::UFDS;

int main() {
  int arr[][3] = {{1, 1, 2}, {1, 1, 3}, {1, 3, 2}, {1, 4, 2}};
  auto g = new Graph(arr, 4, false);
  /* g->PrintEdges(); */
  /* g->BFS(*g->nodes.begin()); */
  /* g->TPsort(); */
  g->kruskalMST();
}