高阶数据结构-图

高阶数据结构-图

图的表示

图由顶点和边构成，可分为有向图和无向图

邻接表法

图的表示方法有邻接表法和邻接矩阵法，以上图中的有向图为例，邻接表法可以表示为

A->[(B,5),(C,10)]
B->[(D,100)]
C->[(B,3)]
D->[(E,7)]
E->[NULL]

邻接表法的特点：

• 为每一个顶点维护一个顺序表，顺序表中存储与这个顶点直接相连的顶点
• 可以快速得出与一个顶点直接相连的顶点个数，时间复杂度为O(1)
• 判断两个顶点是否直接相连需要进行遍历，时间复杂度为O(N)

邻接矩阵法

使用邻接矩阵法可以表示为

顶点(from)/顶点(to)	A	B	C	D	E
A	0	5	10	NONE	NONE
B	NONE	0	NONE	100	NONE
C	NONE	3	0	NONE	NONE
D	NONE	NONE	NONE	0	7
E	NONE	NONE	NONE	NONE	0

邻接矩阵法的特点：

• 维护一个二维数组，数组中的元素为顶点与顶点之间的距离
• 可以快速得出两个点之间是否存在直接相连的边，时间复杂度为O(1)
• 在判断一个顶点直接相连的顶点个数时，需要进行遍历，时间复杂度为O(N)
• 对于无向图，邻接矩阵沿对角线呈对称分布

图的结构

顶点的结构

图由顶点和边构成，顶点的结构如下

struct Edge;
struct Node {Node(string str = "") :value(str) {}string value;int in = 0;int out = 0;unordered_set<Node*> nodes;unordered_set<Edge*> edges;
};

• value，表示顶点对应的值
• in，表示顶点的入度，即存在多少个顶点指向自己
• out，表示顶点的出度，即该顶点指出的顶点个数
• nodes，哈希表结构，存储一个顶点指向的所有顶点
• edges，哈希表结构，存储从一个顶点出发的所有边

以图中的A点为例

其value=“A”，in=0，out=2，nodes为顶点B和C，edges为权值为5的边和权值为10的边

为什么需要使用哈希表存储顶点和边？

哈希表的增删查改时间复杂度均为O(1)，在实现图相关算法时具有较好的优势

边的结构

struct Edge {Edge(Node* f, Node* t, int w = 0) :from(f), to(t), weight(w) {}int weight = 0;Node* from = nullptr;Node* to = nullptr;
};

• weight，表示边的权值
• from，表示这条边从哪一个顶点出发
• to，表示这条边以哪一个顶点作为结束
• 如果是无向图，使用2条有向边表示即可

图的结构

struct Graph {unordered_map<string, Node*> nodes;unordered_set<Edge*> edges;
};

nodes中的key为顶点代表的值，value为具体的顶点

抽象表示转化为已知结构

以下图为例

该图可以使用一个二维数组表示

vector<vector<int>> matrixGraph = {{'A','B',5},{'A','C',10},{'B','D',100},{'C','B',3},{'D','E',7}
};

二维数组中每一个一维数组的第一个元素表示from点，第二个元素表示to点，最后一个元素表示边的权值，二维数组可以表示图，但是在实现图的相关算法不具备通用性，可以将其转化已知结构。

Graph TransforGraph(const vector<vector<int>>& matrixGraph) {Graph ansGraph;for (auto& elemedge : matrixGraph) {string from, to;from += elemedge[0];to += elemedge[1];//获取from点与to点的值int weight = elemedge[2];//获取边的权值if (ansGraph.nodes.count(from) == 0) {ansGraph.nodes[from] = new Node(from);//点不存在就创建}if (ansGraph.nodes.count(to) == 0) {ansGraph.nodes[to] = new Node(to);}Edge* edge = new Edge(ansGraph.nodes[from], ansGraph.nodes[to], weight);ansGraph.nodes[from]->out++;//from点的出度++ansGraph.nodes[from]->edges.insert(edge);//将edge添加到from出发的边ansGraph.nodes[from]->nodes.insert(ansGraph.nodes[to]);//将to点添加到from出发的点ansGraph.nodes[to]->in++;//to点的入度++ansGraph.edges.insert(edge);}return ansGraph;
}

有关图的抽象表示，均可转化为已知结构，以便于实现图的相关算法

图的算法

宽度优先遍历

图结构中可能存在环，宽度优先遍历(bfs)时需要使用哈希表以避免顶点重复进入队列

void bfs(Node* start) {//从start开始进行宽度优先遍历queue<Node*> nodeQ;unordered_set<Node*> nodeSet;nodeQ.push(start);while (!nodeQ.empty()) {Node* cur = nodeQ.front();nodeQ.pop();if (nodeSet.count(cur) == 0) {//表示之前没有遍历过这个顶点cout << cur->value << endl;//访问该顶点nodeSet.insert(cur);//将该顶点加入set,防止重复遍历for (Node* node : cur->nodes) {if (nodeSet.count(node) == 0) {nodeQ.push(node);}}}}
}

深度优先遍历

图的深度优先遍历(dfs)：

1. 使用哈希表记录已经遍历过的顶点
2. 使用栈记录深度优先遍历的路径
3. 在出栈时，已经遍历过的顶点直接跳过

void dfs(Node* start) {stack<Node*> nodeStack;unordered_set<Node*> nodeSet;nodeStack.push(start);cout << start->value << endl;//深度优先遍历在入栈时对顶点进行处理nodeSet.insert(start);while (!nodeStack.empty()) {Node* Topnode = nodeStack.top();//取出栈顶元素nodeStack.pop();for (Node* node : Topnode->nodes) {if (nodeSet.count(node) == 0) {//判断是否已经遍历过cout << node->value << endl;//访问下一层的元素nodeSet.insert(node);nodeStack.push(Topnode);nodeStack.push(node);//将路径压入栈中break;//去往下一层}}}
}

拓扑排序

一个项目可能存在多个模块，模块之间存在一定的依赖关系，可以用图表示

例如上图，模块B依赖于模块A，模块C依赖于模块A和B，模块D依赖于模块A和C，该项目在进行编译时的顺序应该是A、B、C、D

拓扑排序可以用于确定各个模块之间的编译顺序：

1. 寻找入度(in)为0的模块，这些模块不依赖于任何模块，可以直接进行编译
2. 擦除入度为0的模块对整个项目的影响，入度为0的模块，其指向的模块入度减一
3. 重复步骤2，直到所有模块入度均为0
4. 项目中不能存在循环依赖

queue<Node*> TopologyAlgorithm(const Graph& graph) {queue<Node*> ansQ;unordered_map<Node*, int> inMap;//保存所有顶点的入度,不直接修改Nodequeue<Node*> zeroQ;//保存入度为0的顶点for (auto& [value, node] : graph.nodes) {inMap.insert(std::make_pair(node, node->in));if (node->in == 0) {zeroQ.push(node);}}while (!zeroQ.empty()) {Node* zeroNode = zeroQ.front();zeroQ.pop();ansQ.push(zeroNode);for (Node* node : zeroNode->nodes) {if (!--inMap[node]) {//在inMap中进行修改zeroQ.push(node);}}}return ansQ;
}

最小生成树

最小生成树指的是使用最小的代价使得一个图中的所有顶点连通，最小生成树仅适用于无向图。

生成最小生成树的算法有Kruskal算法和Prim算法，Kruskal算法侧重于从边的角度考虑，Prim算法侧重于从顶点的角度进行考虑

Kruskal算法

Kruskal算法生成最小生成树的流程如下：

1. 将所有的边按照权值由小到大放入小根堆
2. 从小根堆弹出权值最小的边，判断这条边的2个顶点是否在同一个集合，若不在，则将这两个顶点所在的集合合并为一个集合，并将这条边加入最终结果；若在，直接舍弃这条边
3. 重复步骤2，直到小根堆中没有元素

使用Kruskal算法生成最小生成树需要使用并查集结构，并查集结构可以快速判断2个元素是否在同一个集合，以及快速合并2个集合

并查集

1. 初始时，并查集中每一个元素各自为一个集合，其父节点均为自身
2. 进行集合合并时，只需将一个集合的父节点指向另外一个集合的父节点
3. 查看2个元素是否处于同一个集合时，只需检查它们最顶层的父节点是否一样
4. 在寻找一个节点最顶层的父节点时，可以将路径上所有节点的父修改为顶层父节点

并查集的实现

template<typename T>
class UnionFindSet {
public:template<class Iter>UnionFindSet(Iter first, Iter last) {for (auto it = first; it != last; it++) {fatherMap[*it] = *it;sizeMap[*it] = 1;}}bool IsSameSet(T left, T right) {if (fatherMap.count(left) == 0 || fatherMap.count(right) == 0) {return false;}return TopLevelNode(left) == TopLevelNode(right);//顶层父节点是否相同}void Union(T left, T right) {//合并集合if (fatherMap.count(left) == 0 || fatherMap.count(right) == 0) {return;}T ltop = TopLevelNode(left);T rtop = TopLevelNode(right);if (ltop != rtop) {size_t lsize = sizeMap[ltop];size_t rsize = sizeMap[rtop];T maxSet = lsize > rsize ? ltop : rtop;T minSet = lsize > rsize ? rtop : ltop;sizeMap[maxSet] += sizeMap[minSet];//将小集合合并到大集合fatherMap[minSet] = maxSet;sizeMap.erase(minSet);}}size_t SetSize(T node) {//获取一个元素所在集合的元素个数if (fatherMap.count(node) == 0) {return -1;}return sizeMap[fatherMap[node]];}
private:T TopLevelNode(T node) {//获取一个顶点最顶层的父节点vector<T> nodes;while (node != fatherMap[node]) {nodes.push_back(node);node = fatherMap[node];}for (auto& it : nodes) {fatherMap[it] = node;//压缩路径}return node;}
private:unordered_map<T, T> fatherMap;//记录每一个顶点的直接父节点unordered_map<T, size_t> sizeMap;//记录每一个大集合中元素的个数
};

使用并查集实现Kruskal算法

使用并查集实现Kruskal算法时，返回值为所有选中的边，根据边即可获取最小生成树的所有信息，需要注意的是，虽然Kruskal算法适用于无向图，但返回值为有向边，这并不影响最小生成树的结构，因为有向边中包含from点、to点、权值

vector<Edge*> Kruskal(const Graph& graph) {vector<Edge*> ans;vector<Node*> nodes;for (auto& [value, node] : graph.nodes) {nodes.push_back(node);}UnionFindSet<Node*> nodeUFS(nodes.begin(), nodes.end());auto EdgeCompare = [](const Edge* l, const Edge* r) {return l->weight > r->weight;};priority_queue<Edge*, deque<Edge*>, decltype(EdgeCompare)> edgeHeap(graph.edges.begin(), graph.edges.end(), EdgeCompare);//graph是无向图,edgeHeap中存在权值相同,方向相反的边while (!edgeHeap.empty()) {Edge* edge = edgeHeap.top();edgeHeap.pop();Node* from = edge->from;Node* to = edge->to;if (!nodeUFS.IsSameSet(from, to)) {//选择这条边ans.push_back(edge);nodeUFS.Union(from, to);}}return ans;
}

Prim算法

Prim算法生成最小生成树侧重于从顶点出发考虑问题，不需要使用并查集

Prim算法流程

1. 任意选取一个顶点作为起点，将该顶点出发的边加入小根堆，并将这个顶点添加到哈希表
2. 从小根堆中选取权值最小的边，若这条边的to点在哈希表中，跳过这条边，否则以to点作为中心，将与to点相连的边添加到小根堆
3. 将边向小根堆添加的过程中，应该检查这个边的to点是否在哈希表中，若不在，才可以添加

Prim算法的实现

vector<Edge*> Prim(const Graph& graph) {vector<Edge*> ans;Node* start = graph.nodes.begin()->second;//任选一个顶点作为起点unordered_set<Node*> nodeSet;nodeSet.insert(start);auto EdgeCompare = [](const Edge* l, const Edge* r) {return l->weight > r->weight;};priority_queue<Edge*, deque<Edge*>, decltype(EdgeCompare)> edgeHeap(EdgeCompare);for (Edge* edge : start->edges) {edgeHeap.push(edge);//将从顶点出发的边添加到小根堆}while (!edgeHeap.empty()) {Edge* edge = edgeHeap.top();Node* to = edge->to;edgeHeap.pop();if (nodeSet.count(to) == 0) {//to点没有被添加到哈希表nodeSet.insert(to);ans.push_back(edge);for (Edge* edge : to->edges) {edgeHeap.push(edge);}}}return ans;
}

Dijikstra算法

Dijikstra(迪杰斯特拉)算法用于寻找最短路径，采用动态规划的思想(本质是逐步尝试)

图中A到B的最短路径是5，A到C的最短路径是先通过B在达到C，为15。

Dijikstra寻找最短路径的的思想：每次寻找距离最近的点，以该点作为中心尝试进行更新

Dijikstra算法的实现

pair<unordered_map<Node*, list<Node*>>, unordered_map<Node*, int>> Dijikstra(Node* base) {//求base点到各个点的最短距离unordered_map<Node*, int> distanceMap;//distanceMap[a]表示base点到a点的距离,若a不在distanceMap中,表示base点与a点的距离为无穷unordered_map<Node*, list<Node*>> pathMap;//pathMap[a]表示base点到a点的路径unordered_set<Node*> lockedNode;//表示已经确定最短距离的点auto getMinAndUnlockedNode = [&]() {//找到distanceMap中距离最小的点,且这个点没有被锁定Node* ans = nullptr;for (auto& [node, distance] : distanceMap) {if (lockedNode.count(node) == 0) {ans = ans == nullptr ? node : (distanceMap[ans] > distance ? node : ans);}}return ans;};pathMap[base].push_back(base);distanceMap[base] = 0;//base->baseNode* cur;while (cur = getMinAndUnlockedNode()) {lockedNode.insert(cur);for (Edge* edge : cur->edges) {Node* to = edge->to;//状态转移方程if (distanceMap.count(to) == 0) {pathMap[to] = pathMap[cur];pathMap[to].push_back(to);distanceMap[to] = distanceMap[cur] + edge->weight;}else {if (distanceMap[cur] + edge->weight < distanceMap[to]) {pathMap[to] = pathMap[cur];pathMap[to].push_back(to);distanceMap[to] = distanceMap[cur] + edge->weight;}}}}return std::make_pair(pathMap, distanceMap);
}