图的建立 顶点类
class Node{ public: int value; //顶点的值value int in; //顶点的入度in（也就是指向该顶点的边数） int out; //顶点的出度out（也就是从该顶点出发的边数） list<Node*> nexts; // 当前节点为from，所有to节点的集合 list<Edge*> edges; //从该节点出发边的集合edges Node(int value){ this->value = value; in = 0; out = 0; } };边类
class Edge{ public: int weight; //边的权重weight Node* from; //from节点 Node* to; //to节点 Edge(int weight, Node* from, Node* to){ this->weight = weight; this->from = from; this->to = to; } };Graph类
一张图其实质就是一个点的集合+一个边的集合，并且这些元素都是无序的，因此为了更加便捷的访问，所以我们在这里都是用基于哈希函数的无序容器结构来储存！ 注意：如果使用自定义类型，需要重写哈希函数。
class Graph{ public: unordered_map<int, Node*> nodes; //存储所有Node以及它的下标编号 unordered_set<Edge*> edges; //存储所有边 };当我们准备好了这些类之后，我们就可以建立整个图了，我们使用邻接矩阵的形式，只需要输入一个边的权重、from节点的值和to节点的值就可以创建两个节点和一条边，然后添加入整个图中！
建立过程中，一定要注意，当加入一条边时，我们一定要将from节点的出度+1，to节点的入度+1，然后将to节点添加到from节点的nexts中，并将这个边添加到from节点的边集edges。
class GraphGenerator{ // 三列分别是权重，from， to public: Graph createGraph(vector<vector<int>>& matrix, int rows, int cols){ Graph graph; for(int i=0;i < rows;i ++){ //每一行就是三个数：权重，from，to int weight = matrix[i][0]; int from = matrix[i][1]; int to = matrix[i][2]; //看看节点是否已经添加 if(graph.nodes.find(from) == graph.nodes.end()){ graph.nodes[from] = new Node(from); } if(graph.nodes.find(to) == graph.nodes.end()){ graph.nodes[to] = new Node(to); } //创建节点 Node* fromNode = graph.nodes.find(from)->second; Node* toNode = graph.nodes.find(to)->second; Edge* newEdge = new Edge(weight, fromNode, toNode); // 新增一条边，则to节点的入度增加 toNode->in++; // from节点的出度增加 fromNode->out++; fromNode->nexts.push_back(toNode); fromNode->edges.push_back(newEdge); graph.edges.insert(newEdge); } return graph; } private： vector<vector<int>> matrix = {{6, 1, 2}, {5, 1, 4}, {2, 6, 4}, {6, 6, 5}, {3, 2, 5}, {1, 3, 1}, {5, 3, 2}, {6, 3, 5}, {4, 3, 6}, {5, 3, 4}, // 只到这里为一个有向图，from和to再反过来一遍就是无向的了 {6, 2, 1}, {5, 4, 1}, {2, 4, 6}, {6, 5, 6}, {3, 5, 2}, {1, 1, 3}, {5, 2, 3}, {6, 5, 3}, {4, 6, 3}, {5, 4, 3}}; };BFS（广度优先遍历）
// 广度优先遍历图节点 void BFS(Node* node){ if(node == nullptr){ return; } queue<Node*> que; unordered_set<Node*> set; // 用来标示是否访问过 Node* help; que.push(node); set.insert(node); while(!que.empty()){ help = que.front(); que.pop(); cout << help->value << " "; // 使用出队的当前节点来找 for(auto node: help->nexts){ if(set.find(node) == set.end()){ que.push(node); set.insert(node); } } } cout << endl; }DFS（深度优先遍历）
深度优先遍历算法同样也需要一个容器用来标记是否被访问过，但是与BFS不同的是其使用的是栈结构，原因是对于DFS来说是从一个点一直遍历到最后节点，然后还要返回到上一节点判断，如果其nexts中的节点都标记访问过了，那么就再向上回溯，如果有没有访问过的节点，那么就访问，一直重复这个过程！而栈结构可以维护我们的访问节点顺序，便于回溯！
##迭代 void DFS(Node* node){ stack<Node*> sta; unordered_set<Node*> set; // 用来标示是否被访问过 Node* help; // 辅助节点 // 入栈的同时并打印信息 sta.push(node); set.insert(node); cout << node->value << " "; while(!sta.empty()){ help = sta.top(); sta.pop(); // 对出栈的元素判断，如果被打印过，则不会被压栈，说明访问过了 for(auto node: help->nexts){ if(set.find(node) == set.end()){ cout << node->value << " "; sta.push(help); // 将访问的节点入栈，由于当前节点可能还有的分支没有访问 sta.push(node); set.insert(node); break; // 每次只访问某个节点的一个分支，一直深入下去访问 } } } cout << endl; } ##递归 std::unordered_set<Node*> set; void DFS(Node* node) { if (node == nullptr) return; set.insert(node); std::cout << node->value << std::endl; for (auto& item : node->nexts) { if(set.find(item)==set.end()) DFS(item); } }注：本文参考了：开启图结构，非常棒的一篇文章
