php 学院网站,房地产公司排名前十,英文都不懂 学网站建设维护难吗,WordPress自带写文章way#xff1a;找入度为0的节点删除#xff0c;减少其他节点的入度#xff0c;继续找入度为0的节点#xff0c;直到删除完所有的图节点。#xff08;遍历node的neighbors就能得到neighbors的入度信息#xff09;
#includeiostream
#includevector
#incl… way找入度为0的节点删除减少其他节点的入度继续找入度为0的节点直到删除完所有的图节点。遍历node的neighbors就能得到neighbors的入度信息
#includeiostream
#includevector
#includemap
#includeset
#includequeue
using namespace std;//边结构的描述
class Edge
{
public://边的起始节点Node *from;//边的终点节点Node *to;//边的权重int weight;
public:Edge(Node *from, Node *to, int weight){this-from from;this-to to;this-weight weight;}
};//点结构的描述
class Node
{
public://编号值int value;//入度int in;//出度int out;//邻接的点vectorNode* nexts;//邻接的边vectorEdge* edges;
public:Node(){}Node(int value){this-value value;in 0;out 0;}
};//图结构的描述
class Graph
{
public:mapint, Node* nodes;setEdge* edges;Graph(){}
};//利用边结构描述的图来构建图结构
//[0,7,5] [from,to,weight]
//[0,1,3] [from,to,weight]
Graph* createGraph(vectorvectorint matrix)
{Graph *graph new Graph();int m matrix.size();for(int i0; im; i){int from matrix[i][0];int to matrix[i][1];int weight matrix[i][2];//将起点结构放到图里面if(!graph-nodes.count(from)){Node *fromNode new Node(from);graph-nodes[from] fromNode;}//将终点结构放到图里面if(!graph-nodes.count(to)){Node *toNodenew Node(to);graph-nodes[to] toNode;}//将起点和终点的边结构也放到图里面(点可能已经存在过,边一定是新的)Node *fromNode graph-nodes[from];Node *toNode graph-nodes[to];Edge *newEdge new Edge(fromNode, toNode, weight);fromNode-nexts.push_back(toNode);fromNode-edges.push_back(newEdge);fromNode-out;toNode-in;graph-edges.insert(newEdge);}return graph;
}vectorNode* topSort(Graph *graph)
{//收集节点入度映射将0入度放入que中mapNode*,intindegreeMap;queueNode*zeroQue;for(auto pa:graph-nodes){indegreeMap[pa.second]pa.second-in;if(indegreeMap[pa.second]0){zeroQue.push(pa.second);}}vectorNode*result;//开始按入度为0删除节点同时减少其他节点入度删除入度为0...while(!zeroQue.empty()){Node *curzeroQue.front();zeroQue.pop();result.push_back(cur);for(auto next: cur-nexts){indegreeMap[next]indegreeMap[next]-1;if(indegreeMap[next]0){zeroQue.push(next);}}}return result;
}
