graph
图的基本算法主要有四个：BFS、DFS、最短路径、最小生成树算法、拓扑排序算法。算法比较多，并且图的表达形式也非常多，所以我们可以维护一种常用的图结构来作为构成图的模板，将不熟悉的图结构转化为我们常用的图结构。
图结构模板
``` c++ "图的总体结构" struct Graph{ unordered_map nodes; unordered_set edges; };
图主要有点集`nodes`和边集`edges`构成，这里选用unordered结构的原因是因为hashmap比普通的map查询更快。`Node`是基本点的wrapper，这么做是为了方便算法编写。
``` c++ "node的基本结构"
struct Node{
int value;//基本点的序号，即点1、点2...
int in;//该点的入度
int out;//该店的出度
unordered_set<Node*,HashNodeptr,EqualNodeptr> nexts;//该set表示由该点出发可以到达的第一个邻居节点
unordered_set<Edge*,HashEdgePtr,EqualEdgePtr> edges;//该set表示属于该点的边,即从该点出发的边
Node (int v):value(v){
in=0;
out=0;
}
}``` c++ "Edge的基本结构" struct Edge{ int weight;//该边的权重 Node from;//该边的出发节点 Node to；//改边的目的节点 Edge(int w,Node f,Node t):weight(w),from(f),to(t){} }
因为结构体相互嵌套的原因，所以必须使用指针。
使用上面的图结构，只需要写一个转换接口就可以使用。假设采用这样一种图接口：一个二维数组：每一行表示一个节点：`[Node from,Node to,int weight]`,下面是一个栗子。
``` c++ "转化函数"
Graph* Transform(vector<vecotr<int>>& nums){
Graph* graph=new Graph;
for(auto elem:nums){
int from=elem[0];
int to=elem[1];
int weight=elem[2];
//没有构造过该节点，将该节点加入nodes
//比如[1,2,0]和[2,3,0]，在处理第一个边时节点2已经构造好了，只需要更新节点相关信息即可
if(graph->nodes.find(from)==graph->nodes.end()){
graph->nodes.insert(pair<int,Node>(from,*new Node(from)));
}
if(graph->nodes.find(to)==graph->nodes.end()){
graph->nodes.insert(pair<int,Node>(to,*new Node(to)));
}
//这里不能使用at,因为返回值copy，除非对应的value是指针，无所谓copy与否，使用find返回迭代器直接修改
auto from_iter=graph->nodes.find(from);
auto to_iter=graph->nodes.find(to);
//更新入度出度
from_iter->second.out++;
to_iter->second.in++;
//更新邻居节点
from_iter->second.nexts.insert(&to_iter.second);
Edge* edge=new Edge(weight,&from_iter.second,&to_iter.second);
from_iter->second.edges.insert(edge);
graph->edges.insert(*edge);
//一个节点处理完毕
}
return graph;
}使用时只需要稍微修改上述模板即可使用该结构。
图结构java模板
``` java "图结构" public class Graph { HashMap nodes; HashSet edges; Graph(){ this.nodes=new HashMap<>(); this.edges=new HashSet<>(); } }
class Node{
public int value;
public int in;
public int out;
public ArrayList<Node> nexts;
public ArrayList<Edge> edges;
public Node(int value) {
// TODO Auto-generated constructor stub
this.value=value;
this.in=0;
this.out=0;
this.nexts=new ArrayList<>();
this.edges=new ArrayList<>();
}
}
class Edge{
int weight;
Node from;
Node to;
public Edge(int weight, Node from, Node to) {
super();
this.weight = weight;
this.from = from;
this.to = to;
}}
``` java "转换函数"
Graph transfoGraphTemp(int[][] data) {
Graph graph=new Graph();
for(int i=0;i<data.length;++i) {
Integer from=data[i][1];
Integer to=data[i][0];
//查询是否加入过这两个点
if(!graph.nodes.containsKey(from)) {
graph.nodes.put(from, new Node(from));
}
if(!graph.nodes.containsKey(to)) {
graph.nodes.put(to, new Node(to));
}
//更新点的入度和出度
Node fromNode=graph.nodes.get(from);
Node toNode=graph.nodes.get(to);
Edge newEdge=new Edge(0, fromNode, toNode);
//更新所属边和邻居节点
fromNode.nexts.add(toNode);
fromNode.out++;
toNode.in++;
fromNode.edges.add(newEdge);
graph.edges.add(newEdge);
}
return graph;
}图遍历
图遍历两种常用的方法是DFS和BFS,含义就不细说了，主要讲讲实现代码。
BFS
顾名思义，按照广度遍历，这里需要使用一个队列结构，以及一个hashset结构(防止重复将邻居节点放入队列中)
void BFS(Node* head){
if(head =nullptr){
return;
}
queue<Node*> que;
unordered_set<Node*,HashNodePtr,EqualNodePtr> sets;
//入队列和入set操作是配套的
que.push(head);
sets.insert(head);
while(!que.empty()){
Node* current=que.front();
que.pop();
//do operation
cout<<"value: "<<current->value<<endl;
//处理该节点的所有邻居节点
for(auto elem:current->nexts){
//如果该邻居节点没有注册过，那么进行注册并放入队列
if(sets.find(elem)==sets.end()){
que.push(elem);
sets.insert(elem);
}
}
}
return;
}void DFS(Node* head){
if(head==nullptr){
return;
}
stack<Node*> stacks;
unordered_set<Node*,HashNodePtr,EqualNodeptr> sets;
stacks.push(head);
sets.insert(head);
cout<<"value: "<<head->value<<endl;
while(!stacks.empty()){
Node* current=stacks.top();
stacks.pop();
//处理current的邻居节点
for(auto elem:current->nexts){
//如果next中的一个节点没有注册过，那么就注册，并入栈
//在入栈前必须先将current先入栈，原因如下：
//如果current的next节点elem没能遍历完所有节点，
//那么退栈时退到current会发现其的next节点没有全部注册
//说明还没遍历完，需要使用下一个next继续遍历；
//那么如果next全部注册，就直接退栈
//所以需要在第一次入栈的时候打印；如果不是第一次，一个节点可能入栈出栈多次
//比如current节点，需要亲自处理所有next节点，即current入栈，next1入栈，next1出栈，current出栈，
//然后current的next2入栈，current入栈，到底哪次打印？
if(sets.find(elem)==sets.end()){
stacks.push(current);
stacks.push(elem);
sets.insert(elem);
cout<<"value: "<<elem->value<<endl;
break;
}
}
}
return;
}拓扑排序
这个有啥用？有一个典型应用场景：编译项目时，子项目的依赖问题，需要决定先后顺序，这时候就能用到拓扑排序了。解决该问题时需要用到节点的入度与出度。
list<Node*> SortTopo(cosnt Graph* graph){
list<Node*> results;
queue<Node*> zero_in_nodes;
unordered_map<Node*,int HashNodePtr,EqualNodeptr> in_maps;
//先找到所有入度为0的节点
for(auto elem:graph->nodes){
if(elem.second.in == 0){
zero_in_nodes.push(&elem.second);
}
}
while(!zero_in_nodes.empty()){
Node* current=zero_in_nodes.front();
zero_in_nodes.pop();
results.emplace_back(current);
//消除该节点对所有邻居节点的影响
for(auto every_node:current->nexts){
//这样写就破坏图结构了，不好，应使用hashmap维护节点的入读
/*
every_nodes->in--;
if(every_nodes->in == 0){
zero_in_nodes.push(every_nodes);
}
*/
in_map[every_node]=--every_nodes->in;
if(in_map[every_node]== 0){
zero_in_nodes.push(every_node);
}
}
}
}写代码时应考虑是否应该更改参数的相关数据，所以不希望更改时应加const，那么如何表示常量指针呢？ 答案：const写在
*前面就是常量指针，写在后面就是指针常量，比如const Graph* graph,graph是一个常量指针。
java版本：
``` java "拓扑排序java版" static List TopoSort(GraphTemp graph,int numCourse) { HashMap inMap=new HashMap<>(); Queue zeroInQueue=new LinkedList<>();
for(Node elem:graph.nodes.values()) {
inMap.put(elem, elem.in);
if(elem.in==0) {
zeroInQueue.add(elem);
}
}
if(zeroInQueue.isEmpty()) {
return false;
}
List<Node> results=new ArrayList<>();
while(!zeroInQueue.isEmpty()) {
Node cur=zeroInQueue.poll();
results.add(cur);
for(Node elem:cur.nexts) {
inMap.put(elem, inMap.get(elem)-1);
if(inMap.get(elem)==0) {
zeroInQueue.add(elem);
}
}
}
return resullts;}
## 最小生成树(无向图算法)
最小生成树有两种算法：
- p算法：在不构造环的前提下，依次选取权重最小的边，当所有边都选完了，最小生成树也构造好了。
- k算法
### p算法
就一个重点：**不构造环的前提下**，那么如何判断会不会构造环？这里提供一种判断方法：如果两个点在一个集合中时，就会构成环。所以问题转化成了如何判断两个点是否属于同一个集合。一般采用**并查集**的方法快速判断，这里先实现一种简单的结构。
``` c++
struct Mysets{
//需要维护一个hashmap，key为node，value为对应的集合
//这里如果直接存放set，不好判断两个点是否在同一个集合啊
unordered_map<Node*,set<Node*,HashNodePtr,EqualNodeptr>*,HashNodePtr,EqualNodePtr> sets_map;
//进行初始化
Mysets(const unordered_map<int,Node,HashNode,EqualNode>& nodes){
for(auto elem:nodes){
sets_map.insert(pair<Node*,set<Node*,HashNodePtr,EqualNodePtr>>(&elem.second,new set{&elem}));
}
}
//需要为用户提供两个方法
//判断两个点是否属于同一个集合
bool isSameSet(const Node* lhs,const Node* rhs){
//判断两个node对应的set内存地址是否相同
return sets_map[lhs]==sets_map[rhs];
}
//合并两个点至同一集合
void Union(Node* lhs,Node* rhs){
auto left_iter=sets_map.find(lhs);
auto right_iter=sets_map.find(rhs);
auto address=right_iter->second;
for(auto elem:*right_iter->second){
left_iter->second->insert(elem);
//需要更新每个节点对应的集合
Mysets[elem]=right_iter->second;
}
//而不是在最后只更新rhs对应的集合
//sets_map[right_iter.first]=left_iter->second;
delete address;
}
};
list<Edge*> Kruskal(Graph* graph){
list<Edge*> results;
//首先需要对所有边构造一个小根堆
auto cmp=[](const Node* lhs,const Node* rhs)->bool{return lhs->weight>rhs->weight};
priority_queue<Node*,vector<Node*>,decltype(cmp)> pri_queue(cmp);
//初始化节点与集合
Mysets myset(graph->nodes);
for(auto elem:graph->edges){
pri_queue.push(&elem);
}
//由小到大处理每条边
while(!pri_queue.empty()){
Edge* current_edge=pri_queue.top();
pri_queue.pop();
Node* from=current_edge->from;
Node* to=current_edge->to;
//如果新选取的边首尾两点不在同一集合，那么就选它
if(myset.isSameSet(from,to)){
results.emplace_back(current_edge);
myset.Union(from,to);
}
}
return std::move(results);
}p算法
p算法就是首先随便选取一个点，然后选取该点权值最小的边，查看该边的to节点是否已经处理过，如果没有处理，将该点的所有边加入小根堆，继续选取最小的边
注意：map中的每个元素是一个pair，而不是一个pair迭代器，这一点不要弄混了
list<Edge*> Prim(const Graph* graph){
list<Edge*> results;
unordered_set<Node*,HashNodePtr,EqualNodePtr> selected_nodes;
auto cmp=[](const Edge* lhs,const Edge* rhs)->bool{return lhs->weight>rhs->weight;};
priority_queue<Edge*,vector<Edge*>,decltype(cmp)> pri_queue(cmp);
//for循环是为了处理森林问题，有可能图是不连通的，但是这又是按点选取，不像k算法按照边构造最小生成树
for(auto every_node_pair:graph->nodes){
//随便选一个点
if(selected_nodes.find(&every_node_iter.second)==selected_nodes.end()){
selected_nodes.(&every_node_iter.second);
}
for(auto elem:every_node_pair.second.edges){
pri_queue.push(elem);
}
while(!pri_queue.empty()){
Edge* current_edge=pri_queue.top();
pri_queue.pop();
Node* current_to=current_edge->to;
//如果没有处理to节点
//每次选取的最小边就是最小生成树的一部分，当然只有边的to节点未处理才行
results.emplace_back(current_edge);
if(selected_nodes.find(current_to)==selected_nodes.end()){
selected_nodes.insert(current_to);
for(auto elem:current_to->edges){
pri_queue.push(elem);
}
}
}
}
return std::move(results);
}简单来说p算法就是按点选，先随便选一个点，选取属于该点并且权值最小的边
然后再看该边的to节点是否已经处理过，如果没有处理过，就将属于to节点的边加入候选边组，并且将该变加入结果集,不是是个最小边就要加入哦(只有边的to节点没处理才会加入，这是为了防止形成环，)
然后再从候选边组选最小的边
最短路径
这里使用迪杰斯特拉算法，求一个节点到所有节点的路径
unordered_map<Node*,int,HashNodePtr,EqualNodePtr> djstla(Node* head){
if(head ==nullptr){
return unordered_map<Node*,int,HashNodePtr,EqualNodePtr>{};
}
unordered_map<Node*,int,HashNodePtr,EqualNodePr> distance_map;
//同样需要对点实行一种注册机制
unordered_set<Node*,HashNodePtr,EqualNodeptr> selected_nodes;
//选取距离源节点距离最短并且没有注册过的节点
distance_map[head]=0;
Node* current=GetMinDistanceAndUnused(distance_map,selected_nodes);
//当所有节点都注册后，表示源点对所有节点的最短距离已经求出
//current距离源点的最短距离已经求出，下面操作为了求出下一层的邻居节点的最短距离
while(current != nullptr){
//取得当前距离源点的最短距离
int current_dis=distance_map.at(current);
//更新源点经过current节点到下一邻居节点的距离
for(auto edge_to:current->edges){
//如果to节点没有加入distance_map,直接加入即可，因为一定可以到达，因为是不断通过next到达node_to的
Node* node_to=edge_to->to;
if(distance_map.find(node_to)==distance_map.end()){
distance_map[node_to]=current_dis+edge_to->weight;
}
//加入过node_to节点，需要比较源点到node_to的距离和经过current后距离源点的距离
distance_map[node_to]=min(current_dis+edge_to->weight,distance_map[node_to]);
}
//所有current节点的边都已处理完成
selected_nodes.inert(current);
current=GetMinDistanceAndUnused(distance_map,selected_nodes);
}
return std::move(distance_map);
}
Node* GetMinDistanceAndUnused(const unordered_map<Node*,int,HashNodePtr,EqualNodePtr>& distance_map,const unordered_set<Node*,HashNodePtr,EqualNodePtr>& selected_nodes){
//选取距离源点最小并且没有注册过的点
Node* result{nullptr};
int distance=INT_MAX;
//遍历map，通过set过滤
for(auto elem:distance_map){
if(selected_nodes.find(elem.first)==selected_nodes.end()
&& elem,second<distance){
result=elem.first;
distance=elem.second;
}
}
return result;
}这个注册过的点表示源点至该点的最小距离已经确定，无需更改。
hash table相关的自定义hash function
struct HashNode {
std::size_t operator()(const Node& nodes) const
{
using std::size_t;
using std::hash;
return ((hash<int>()(nodes.value)
^ (hash<int>()(nodes.in) << 1)) >> 1)
^ (hash<int>()(nodes.out) << 1);
}
};
struct EqualNode
{
bool operator () (const Node& lhs, const Node& rhs) const
{
return lhs.value == rhs.value
&& lhs.in == rhs.in
&& lhs.out == rhs.out
&&lhs.nexts==rhs.nexts
&&lhs.edges==rhs.edges;
}
};
struct HashNodePtr {
std::size_t operator()(const Node* nodes) const
{
using std::size_t;
using std::hash;
return ((hash<int>()(nodes->value)
^ (hash<int>()(nodes->in) << 1)) >> 1)
^ (hash<int>()(nodes->out) << 1);
}
};
struct EqualNodePtr
{
bool operator () (const Node* lhs, const Node* rhs) const
{
return lhs->value == rhs->value
&& lhs->in == rhs->in
&& lhs->out == rhs->out
&& lhs->nexts == rhs->nexts
&& lhs->edges == rhs->edges;
}
};
struct HashEdge {
std::size_t operator()(const Edge& edges) const
{
using std::size_t;
using std::hash;
return ((hash<int>()(edges.weight)
^ (hash<int>()(edges.from->value) << 1)) >> 1)
^ (hash<int>()(edges.to->value) << 1);
}
};
struct EqualEdge
{
bool operator () (const Edge& lhs, const Edge& rhs) const
{
//权重、首尾节点相同，边就相同
return lhs.weight == rhs.weight
&& lhs.from->value == rhs.from->value
&& lhs.to->value == rhs.to->value;
}
};Last updated
Was this helpful?