前言

这一章,我们学习了图这种数据结构。本笔记主要完成了以下工作:

  • 总结了图的各种知识
  • 实现了邻接矩阵和邻接表定义的Graph类
  • 实现了IndexMapping 类,使得下面的泛型图算法成为可能(把元素内容和标记分开,下面的泛型图算法实现在整形标记上)
  • 实现了8个泛型图算法,并进行了简单测试,分别是
    • DFS 深度优先搜索
    • BFS 广度优先搜索
    • 通过深度优先搜索判断图中是否有环
    • 通过深度优先搜索进行拓扑排序
    • Prim最小生成树算法
    • Kruskal最小生成树算法
    • Dijskstra 最短路径算法
    • Floyd 最短路径算法
  • 实现了两个专用图算法,分别是
    • 邻接表上的堆优化Dijkstra算法
    • 邻接表上的堆优化Prim算法
  • 给出了几个简单的图论算法应用

图的定义

图的一般定义

一张图 $G$ 是一个二元组$(V,E)$,其中$V$称为顶点集,$E$称为边集。它们亦可写成$V(G)$和$E(G)$。 ${\displaystyle E}$的元素是一个二元组数对,用${\displaystyle (x,y)}$表示,其中${\displaystyle x,y\in V}x,y \in V$。

  • 从定义中可以看到,存储结构的设计主要在于表征此集合关系
  • 可以从边有无方向、是否允许重边(两条或多条边的起止点相同)、是否允许环、边是否带权将图分为多种
  • 值得一提的是,树是连通无回路的图

几种特殊的图

  • n-阶完全图(complete graph)$K_{n}$ − $n$个顶点两两之间都有一条边,每个顶点的度数都$n−1$ ◦ 边的总数目为$n(n−1)/2$.
  • 二部图 - 顶点集可以划分为两个集合$v_{i}, v_{j}$,且$v_{i}$与$v_{j}$之间没有边

连通性

无向图

  • 一个无向图是联通的,当且仅当每两个点都是联通的。
    • 两个点是联通的,当且仅当他们之间有路径。
  • 如果一个图不是联通的,那么它的最大联通子图就叫做联通分量。
  • 可以直观地看到,一个无向图联通的最小边数为$n - 1$

有向图

  • 一个有向图是弱联通的,当且仅当把它对应的无向图是联通的。
  • 一个有向图是强联通的,当且仅当每两个点都是联通的。
  • 可以直观地看到,一个有向图强联通的最小边数为$n$

生成树

  • 一般仅研究无向图的生成树(有向图的“生成树”实际上不能看作树,有术语“最小树形图”来描述此结构,这里不表)
  • 无向图$G(V, E)$的生成树是一颗含有所有顶点$V$的,边属于$E$的树。
  • 可以看作$G$的极小联通子图。
  • 生成树是STP协议的基础。STP 协议就是通过构造网络拓扑图中的生成树来解决环路问题,具体协议内容参见IEEE 802.1D

图的存储表示

图的存储结构主要分为三种:

  • (逆)邻接表
  • 邻接矩阵
  • 关联矩阵

教师还讲述了两种:

  • 有向图的十字链表
  • 无向图的邻接多重表

下面只研究(逆)邻接表和邻接矩阵, 并实现我们自己的Graph C++类。但在此之前,我们首先要知道一个Graph类需要有哪些方法。

ADT 与 抽象类接口

  • ADT Name: Graph
    • Description: …
    • Invariants:
      1. Empty graph: number of vertices is 0; number of edges is 0.
      2. Self-loops are not allowed.
    • Attributes:
      • number of vertices
      • number of edges.
    • Operations:
      • Graph() …
      • addVertex(Vertex v) …
      • addEdge(Vertex v_1, Vertex v_2) …
      • removeVertex(Vertex v) …
      • removeVertex(Vertex v) …
      • removeEdge(Vertex v_1, Vertex v_2) …
      • getNeighbors(Vertex v)
        • returns: a collection containing the Vertices incident on v
      • getNumberOfVertices()
      • getNumberOfEdges()

基于以上的ADT,我们写一个抽象类Graph():

template<class Vertex>
class Graph {
public:
	virtual void addVertex(Vertex& v) = 0;
	virtual void addEdge(Vertex& v_1, Vertex& v_2) = 0;
	virtual void removeVertex(Vertex& v) = 0;
	virtual void removeEdge(Vertex& v_1, Vertex & v_2) = 0;
	virtual std::vector<Vertex> getNeighbors(Vertex& v) = 0;
	virtual uint32_t getNumberOfVertices() = 0;
	virtual uint32_t getNumberOfEdges() = 0;
	virtual void clearGraph() = 0;
};

(逆)邻接表

邻接表

邻接表是指把图存到一个线性表中,这个线性表的每一个元素都是一个链表,链表的第一个元素是一个图中的顶点,其他元素是和这个顶点相邻的顶点。线性表中的元素不重复地覆盖所有图中的顶点。 示意图:

从描述中可以看出,这个结构实际上用于有向图。 这个结构实现起来很简单,如下所示:

template<class value>
class stdVertex {
public:
	value val;
	stdVertex() { val = 0; }
	stdVertex(value val) {
		this->val = val;
	}
	bool operator ==(stdVertex<value> other) {
		return this->val == other.val;
	}
};

/*
 * here we use Vertex class as node,
 * to correctly implement this class, you should follow these rules:
 * 1. overload =(), or don't use anything could cause deep copy/shallow copy problem.
 * 2. implement these methods:
 *    1. getValue()
 */
template<class value, class Vertex = stdVertex<value>, class VertexInner = stdVertex<value>>
class ListGraph : public Graph<Vertex> {
public:
	void addVertex(Vertex& v) {
		std::list<VertexInner> vec_list;
		vec_list.push_back(VertexInner(v));
		this->adjList.push_back(vec_list);
	}

	void addEdge(Vertex& v_1, Vertex& v_2) {
		auto i = std::find_if(this->adjList.begin(), this->adjList.end(),
			[&](auto j) {if (j.front() == v_1) { return true; }});
		if (i == this->adjList.end()) {
			throw std::invalid_argument("v_1 is not a vertex in list!");
		}
		(*i).push_back(v_2);
	}

	void removeVertex(Vertex& v) {
		bool hit = false;
		for (auto i = this->adjList.begin(); i != this->adjList.end();) {
			if ((*i).front() == v) {
				i = this->adjList.erase(i);
				hit = true;
			}
			else {
				for (auto j = (*i).begin(); j != (*i).end();) {
					if (*j == v) {
						j = (*i).erase(j);
					}
					else { ++j; }
				}
				i++;
			}
		}
		if (!hit) {
			throw std::invalid_argument("can't find vertex!\n");
		}
	}

	void removeEdge(Vertex& v_1, Vertex& v_2) {
		for (auto i = adjList.begin(); i != adjList.end(); ++i) {
			/* find v_1 */
			if ((*i).front() == v_1) {
				for (auto j = (*i).begin(); j != (*i).end();) {
					if ((*j) == v_2) {
						/* find v_2 */
						j = (*i).erase(j);
						goto END;
					}
					else {
						j++;
					}
				}
			}
		}
		throw std::invalid_argument("can't find Edge!\n");
	END:
		return;
	}

	std::vector<Vertex> getNeighbors(Vertex& v_1) {
		auto i = adjList[0];
		std::for_each(this->adjList.begin(), this->adjList.end(),
			[&](auto list) {if (list.front() == v_1) { i = list; }});

		std::vector<Vertex> ret;
		std::for_each(i.begin(), i.end(), [&](auto j) {ret.push_back(j); });
		return ret;
	}

	uint32_t getNumberOfVertices() {
		return this->adjList.size();
	}
	
	uint32_t getNumberOfEdges() {
		auto sum = 0;
		std::for_each(this->adjList.begin(), this->adjList.end(),
			[&sum](auto i) {sum += i.size() - 1; });
		return sum;
	}

	void clearGraph () {
		adjList.clear();
	}
protected:
	std::vector<std::list<VertexInner> > adjList;
};

这个时候问题来了,在这个设计下,我们如何实现带权图呢?

呵呵,这个问题我在设计之初就想到了。

首先我们考虑,只要将VertexInner类的参数改成下面这个类,实际上就实现了带权图:

template<class value>
class ValuedVertex : public stdVertex<value> {
	/* edge_value represents the value of edge 
	 * between the former vertex and that vertex
	 * if this vertex is the first vertex, 
	 * then edge_value MUST be INT_MAX
	 */
	uint32_t edge_value;
};

那么,我们只要继承一下ListGraph,再重载一个addEdge方法就可以了。

template<class value, class Vertex = stdVertex<value> >
class ValuedListGraph : public ListGraph<value, stdVertex<value>, ValuedVertex<value>> {
public:
	void addEdge(Vertex v_1, Vertex v_2, uint32_t _value) {
		auto i = std::find_if(this->adjList.begin(), this->adjList.end(),
			[&](auto j) {if (j.front() == v_1) { return true; }});
		if (i == this->adjList.end()) {
			throw std::invalid_argument("v_1 is not a vertex in list!");
		}
		ValuedVertex<value> vex(v_2);
		vex.edge_value = _value; 
		(*i).push_back(vex);
	}
};

这样邻接表就实现好了。邻接矩阵的实现其实更加简单:

由于邻接矩阵天生就适合带权图(矩阵的元素是数),所以我们直接实现为带权图。

#define UNCONNECTED INT_MAX
template <class value, class Vertex = stdVertex<value>>
class MatrixGraph : public IndexGraph<value, Vertex> {
public:
	MatrixGraph(){}
	void addVertex(Vertex& v) {
		/* add colunm */
		for (auto i = matrix.begin(); i < matrix.end(); ++i) {
			(*i).push_back(UNCONNECTED);
		}

		/* add row */
		size_t vec_size = matrix.size() + 1;
		std::vector<uint32_t> vec(vec_size, UNCONNECTED);
		vec[vec_size - 1] = 0;
		matrix.push_back(vec);

		this->addVertexToMap(v);
	}
	
	void addEdge(Vertex& v_1, Vertex& v_2) { addEdge(v_1, v_2, 1); }

	void addEdge(Vertex& v_1, Vertex& v_2, int value) {
		uint32_t i = this->getIndex(v_1);
		uint32_t j = this->getIndex(v_2);
		matrix[i][j] = value;
	}

	void removeVertex(Vertex& v) {
	}

	void removeEdge(Vertex& v_1, Vertex& v_2){}

	std::vector<Vertex> getNeighbors(Vertex& v) {
		std::vector<Vertex> ret;
		uint32_t i = this->getIndex(v);
		for (auto j = 0u; j < this->matrix.size();++j) {
			if (this->_if_connected(i, j)) {
				ret.push_back(Vertex(this->getValue(j)));
			}
		}
		return ret;
	}

	uint32_t getNumberOfVertices() {
		return matrix.size();
	}

	uint32_t getNumberOfEdges() {
		uint32_t ret = 0;
		for (auto i = 0u; i < matrix.size(); ++i) {
			for (auto j = 0u; j < matrix.size(); ++j) {
				if (_if_connected(i, j)) {
					ret++;
				}
			}
		}
		return ret;
	}

	void clearGraph() {
		matrix.clear();
	}

protected:
	std::vector<std::vector<uint32_t>> matrix;
	
	bool _if_connected(uint32_t index_1, uint32_t index_2) {
		return this->matrix[index_1][index_2] != UNCONNECTED && index_1 != index_2;
	}

	std::vector<uint32_t> _get_neighbors(uint32_t index) {
		std::vector<uint32_t> ret;
		for (auto i = 0u; i < matrix[index].size(); ++i) {
			if (_if_connected(index, i)) {
				ret.push_back(i);
			}
		}
		return ret;
	}
	int _get_value(uint32_t pos_1, uint32_t pos_2) {
		return matrix[pos_1][pos_2];
	}
	std::vector<IndexEdge> _get_all_edges() {
		std::vector<IndexEdge> ret;
		for (auto i = 0u; i < this->matrix.size(); ++i) {
			for (auto j = i + 1; j < this->matrix.size(); ++j) {
				if (matrix[i][j] != UNCONNECTED) {
					ret.push_back(IndexEdge(i, j, matrix[i][j]));
				}
			}
		}
		return ret;
	}
};

图上的8种泛型算法

前言

我们实现了8种泛型图算法。“泛型”一词的意思是,这算法不与特定具体实现相关。只要特定具体实现实现了我们在算法中用到的各种函数,就可以使用该算法。

这是怎么做到的呢?这里采用了继承的方法。

我们首先将图中的每个元素与序号(一个整数)建立映射关系,下面的算法就都使用序号进行操作。这个行为被封装为IndexMapping类:

template<class value, class Vertex = stdVertex<value>>
class IndexMapping {
public:
	uint32_t getIndex(Vertex& v) {
		return this->valueToIndex.at(v.val);
	}
	value getValue(uint32_t index) {
		return this->indexToValue.at(index);
	}
	uint32_t addVertexToMap(Vertex& v) {
		this->indexToValue.push_back(v.val);
		this->valueToIndex.insert(
			std::pair<value, uint32_t>(v.val, this->indexToValue.size() - 1));
		return this->indexToValue.size() - 1;
	}
	uint32_t removeVertexFromMap(Vertex& v) {
		int index_v = this->getIndex(v);
		this->indexToValue.erase(indexToValue.begin() + index_v);
		for (auto i = valueToIndex.begin(); i != valueToIndex.end();) {
			if ((*i).second == index_v) {
				i = valueToIndex.erase(i);
			}
			else {
				if ((*i).second > index_v) {
					(*i).second--;
				}
				i++;
			}
		}
		return index_v;
	}
private:
	std::map<value, uint32_t> valueToIndex;
	std::vector<value> indexToValue;
};

然后,用IndexGraph继承IndexMapping类和Graph类:

template<class value, class Vertex = stdVertex<value> >
class IndexGraph : public Graph<Vertex>, public IndexMapping<value, Vertex> 

最后,用一个具体类继承IndexGraph类:

template<class value, class Vertex = stdVertex<value>, class VertexInner = stdVertex<uint32_t>>
class ListGraph : public IndexGraph<value, Vertex>

有开发经验的人恐怕立刻就会想到我要做什么了。现在只要在IndexGraph类中实现基于整形标记的各种图上算法,各个具体子类就会自动地获得运行这些算法的能力!

下面,我们就来实际地看一下这些算法。

注:所有算法都是IndexGraph的成员函数,public, private, protected是c++成员函数可见性的声明。

图的深度优先搜索算法

深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。 我们实现如下:

public:
	/* Depth First Search */
	void DFS(std::function<void(Vertex)> do_something, Vertex start) {
		this->help_vec_8 = std::vector<uint8_t>(this->getNumberOfVertices(), false);
		uint32_t start_index = this->getIndex(start);
		this->STD_DFS(do_something, start_index);
	}
private:
	void STD_DFS(std::function<void(Vertex)> do_something, uint32_t vertex) {
		do_something(Vertex(this->getValue(vertex)));
		help_vec_8[vertex] = true;
		std::vector<uint32_t> list = this->_get_neighbors(vertex);
		for (auto i : list) {
			if (help_vec_8[i] == false) {
				STD_DFS(do_something, i);
			}
		}
	}

这里用到了一个函数_get_neighbors(uint32_t v)这个函数会返所有与v相邻的点。声明为:

	virtual std::vector<uint32_t> _get_neighbors(uint32_t index) = 0;

图的广度优先搜索算法

广度优先搜索算法(英语:Breadth-First-Search,缩写为BFS),又译作宽度优先搜索,或横向优先搜索,是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。 我们实现如下:

public:
	void BFS(std::function<void(Vertex)> do_something, Vertex start) {
		auto _start = this->getIndex(start);
		this->help_vec_8 = std::vector<uint8_t>(this->getNumberOfVertices(), 0);
		std::queue<uint32_t> help_quene;
		help_quene.push(_start);
		for (;!help_quene.empty();) {
			uint32_t now = help_quene.front();
			help_quene.pop();
			help_vec_8[now] = true;
			do_something(Vertex(this->getValue(now)));
			auto neighbors = this->_get_neighbors(now);
			for (auto i : neighbors) {
				if (help_vec_8[i] != true) {
					help_quene.push(i);
				}
			}
		}
	}

用深度优先搜索判断是否有环

这个算法很简单,大意是将每个点分为三种状态:

{已遍历,未遍历,遍历中}

如果出现了一个{遍历中}的点被再次遍历的情况,那么有环,反之无环。

实现如下:

public:
#define RED 1
#define WHITE 0
#define GREEN -1
	/* if the graph have a ring */
	bool ifRing() {
		this->help_vec_8 = std::vector<uint8_t>(this->getNumberOfVertices(), WHITE);
		uint32_t index = 0;
		this->RING_DFS(index);
		return this->ring_hit;
	}
private:
	void RING_DFS(uint32_t index) {
		if (ring_hit == true) {
			return;
		}
		if (help_vec_8[index] == RED) {
			ring_hit = true;
			return;
		}
		else {
			help_vec_8[index] = RED;
			std::vector<uint32_t> list = this->_get_neighbors(index);
			for (auto i : list) {
				if (help_vec_8[i] != GREEN)
				{
					RING_DFS(i);
				}
			}
			help_vec_8[index] = GREEN;
		}
	}
	bool ring_hit;

用深度优先搜索进行拓扑排序

拓扑排序有一种不使用深度优先搜索、基于引用计数的算法,这里没有实现。我们实现的是稍微不太好理解的基于深度优先搜索的算法。

这算法简单来说,就是基于这样一个事实

在深度优先搜索中,如果一个点的搜索完成,那么它后继的所有点的搜索必定已经完成。

这个事实告诉我们,如果在一个点搜索完成时将这个点压入结果栈中,那么这个结果栈的顺序必然是一个拓扑排序序列的反序列 实现如下:

public:
/* Topological Sort */
	std::vector<Vertex> TopoSort() {
		if (ifRing()) { throw std::runtime_error("can't sort because of ring!"); }
		this->help_vec_8 = std::vector<uint8_t>(this->getNumberOfVertices(), 0);
		for (auto i = 0u; i < this->getNumberOfVertices(); ++i) {
			if (help_vec_8[i] != 1) {
				SORT_DFS(i);
			}
		}
		std::reverse(this->sort_result_vec.begin(), this->sort_result_vec.end());
		std::vector<Vertex> result_vec;
		for (auto i : sort_result_vec) {
			result_vec.push_back(Vertex(this->getValue(i)));
		}
		return result_vec;
	}
private:
		void SORT_DFS(uint32_t index){
		this->help_vec_8[index] = 1;
		std::vector<uint32_t> neighbor = this->_get_neighbors(index);
		for (auto i : neighbor) {
			if (help_vec_8[i] != 1) {
				SORT_DFS(i);
			}
		}
		sort_result_vec.push_back(index);
	}
	std::vector<int> sort_result_vec;

最小生成树–Prim算法

Prim 算法和Dijkstra 算法有些相似,其基本思想是选点,也就是将整个图划分为两个集合

  • 已选出的点
  • 未选出的点

然后每次都在未选出点集合中选出与已选出的点集合距离最近的点。选择n次后,算法结束。

	std::vector<std::pair<Vertex, Vertex>> Prim() {
		std::vector<bool> add_list(this->getNumberOfVertices(), false);
		std::vector<uint32_t> father(this->getNumberOfVertices(), INT32_MAX);
		std::vector<int> distance(this->getNumberOfVertices(), INT32_MAX);
		std::vector<std::pair<int, int>> result_vec;

		distance[0] = 0;
		father[0] = 0;
		for (auto i = 0u; i < this->getNumberOfVertices(); ++i) {
			auto pos = 0u;
			auto min = INT32_MAX;
			for (auto j = 0u; j < distance.size(); ++j) {
				if ((distance[j] < min)&& !add_list[j]) {
					pos = j;
					min = distance[j];
				}
			}
			add_list[pos] = true;
			for (auto j = 0u; j < distance.size(); ++j) {
				if ((distance[j] > _get_value(pos, j)) && !add_list[j]) {
					father[j] = pos;
					distance[j] = _get_value(pos, j);
				}
			}
		}

		std::vector<std::pair<Vertex, Vertex>> ret;
		for (auto i = 1u; i < add_list.size();++i) {
			Vertex v_1(this->getValue(i));
			Vertex v_2(this->getValue(father[i]));
			std::pair<Vertex, Vertex> pair(v_1, v_2);
			ret.push_back(pair);
		}
		return ret;
	}

最小生成树 – Kruskal算法

这个算法的基本思想是选边。将这个图中所有的边划分为两个集合:

  • 已选出
  • 未选出

然后每一次选择时,选择未选出集合中边权最小的边加入已选出集合,然后测试,若加入后形成了环,则删掉这个边,再选择次小边,直到加入后不形成环为止。 这样选择N - 1次后,算法结束。

	std::vector<std::pair<Vertex, Vertex>> Kruskal() {
		std::vector<IndexEdge> vec = this->_get_all_edges();
		std::sort(vec.begin(), vec.end());
		auto i = vec.begin();
		auto count = 0U;
		std::vector<std::pair<Vertex, Vertex>> ret;
		IndexDSet<> set(this->getNumberOfVertices());
		for (; count < this->getNumberOfVertices() - 1;) {
			auto v_1 = (*i).edge.first;
			auto v_2 = (*i).edge.second;
			/* retrun true means we don't have a ring after merge */
			if (set.mergeTwoSet(v_1, v_2)) {
				ret.push_back(std::pair<Vertex, Vertex>( 
					Vertex(this->getValue(v_1)), Vertex(this->getValue(v_2))));
				count++;
			}
			i++;
		}
		return ret;
	}

这里使用了并查集这种数据结构来判断是否有环。

#define IndexType uint32_t
class DSNode {
public:
	IndexType getParent() {
		return parent;
	}
	void setParent(IndexType& index) {
		this->parent = index;
	}
protected:
	IndexType parent;
};

template <class Node = DSNode>
class IndexDSet {
public:
	IndexDSet(){}
	IndexDSet(IndexType count) {
		vec = std::vector<Node>(count);
		for (auto i = 0u; i < vec.size(); ++i) {
			this->vec[i].setParent(i);
		}
	}
	IndexType getParent(IndexType target) {
		if (this->vec[target].getParent() == target) {
			return target;
		}
		else {
			return getParent(this->vec[target].getParent());
		}
	}
	bool ifSame(IndexType ele_a, IndexType ele_b) {
		IndexType parent_a = getParent(ele_a);
		IndexType parent_b = getParent(ele_b);
		
		return parent_a == parent_b;
	}
	bool mergeTwoSet(IndexType ele_a, IndexType ele_b){
		IndexType parent_a = getParent(ele_a);
		IndexType parent_b = getParent(ele_b);
		if (parent_a == parent_b) {
			return false;
		}
		else {
			this->vec[parent_a].setParent(parent_b);
			return true;
		}
	}
protected:
	std::vector<Node> vec;
};

最短路径算法 – Dijkstra算法

Dijkstra 算法的基本思想是,将所有的点分为两类:

  • 已选出
  • 未选出

使用一个集合存储所有点与源点的距离;

每次都选出未选出集合中,距离源点(Prim算法中是已选出点的集合)最近的点,然后更新和这个点邻接的所有点与源点的距离。

std::vector<PathNode<value>> Dijkstra(Vertex& start) {
		std::vector<uint32_t> father(this->getNumberOfVertices(), 0xffffffff);
		std::vector<int> shortest(this->getNumberOfVertices(), INT_MAX);
		std::vector<bool> mark(this->getNumberOfVertices(), false);
		auto v = this->getIndex(start);
		bool end = false;
		shortest[v] = 0;
		father[v] = v;
		auto pos = 0;
		for (; !end;) {
			auto min = INT_MAX;
			end = true;
			for (auto i = 0u; i < shortest.size(); ++i) {
				if (mark[i] == false && shortest[i] != INT_MAX) {
					end = false;
				}
				if (shortest[i] < min && mark[i] == false) {
					pos = i;
					min = shortest[i];
				}
			}
			mark[pos] = true;
			for (auto i = 0u; i < shortest.size(); ++i) {
				if (_get_value(pos, i) == INT_MAX) {
					continue;
				}
				if (shortest[i] > shortest[pos] + _get_value(pos, i) && mark[i] == false) {
					father[i] = pos;
					shortest[i] = shortest[pos] + _get_value(pos, i);
				}
			}
		}
		std::vector<PathNode<value>> ret;
		for (auto i = 0u; i < this->getNumberOfVertices();++i) {
			PathNode<value> p(Vertex(this->getValue(father[i])), Vertex(this->getValue(i)), shortest[i]);
			ret.push_back(p);
		}
		return ret;
	}

最短路径算法 – Flyod算法

这是一个很有趣的算法,也可以用来求传递闭包,这里不过多解释:

	std::vector<PathNode<value>> Floyd(Vertex v_1) {
		auto temp = std::vector<std::vector<int>>(this->getNumberOfVertices(), 
			std::vector<int>(this->getNumberOfVertices(), INT_MAX));
		
		for (auto i = 0u; i < this->getNumberOfVertices(); ++i) {
			for (auto j = 0u; j < this->getNumberOfVertices(); ++j) {
				temp[i][j] = this->_get_value(i, j);
			}
		}

		for (auto k = 0u; k < this->getNumberOfVertices(); ++k) {
			for (auto i = 0u; i < this->getNumberOfVertices(); ++i) {
				for (auto j = 0u; j < this->getNumberOfVertices(); ++j) {
					if (temp[i][k] == INT_MAX || temp[k][j] == INT_MAX) {
						continue;
					}
					if (temp[i][j] > temp[i][k] + temp[k][j]) {
						temp[i][j] = temp[i][k] + temp[k][j];
					}
				}
			}
		}

		auto v = this->getIndex(v_1);
		std::vector<PathNode<value>> ret;
		for (auto i = 0u; i < this->getNumberOfVertices(); ++i) {
			PathNode<value> temp_node(Vertex(this->getValue(v)), Vertex(this->getValue(i)), temp[v][i]);
			ret.push_back(temp_node);
		}
		return ret;
	}

两个专用算法 – 邻接表上的堆优化Dijkstra算法和Prim算法

为什么要进行堆优化?可能有人会说是因为要实现$Elog(V)$的复杂度,但对我们这种算法初学者来说,速度不是学习的重点。

实际上,这是来源于我们对Dijkstra算法的实现很不自然:

我们使用了一个vector来存储最短路径,又用了一个vector来存储标记,如果一个点被选出了,就打上标记,下一次就不选择它。

这实际上是把已选出和未选出的点都放在一起,然后用标记来区分它们。这样很不自然而且很容易出错。

那么可不可以专门建立一个未选出点的集合,一开始有所有点,每选出一个点就删除它呢?这是可以的,但需要二叉搜索树等数据结构的支持,可以用std::set实现这个想法。

但这里不用这种办法,而是使用另一种办法:令未选出集合一开始为空,然后动态地添加和删除。

也就是说,首先把源点加入集合中,然后使用一个循环:

当集合非空时,每次取出集合中距离源点最小的元素,然后用与这个元素相接的元素更新结果集,同时将这些元素加入这个集合。

其中“取出距离最小的元素”恰恰就是一个小顶堆的操作。所以这里使用 std::priority_queue 作为这个集合的实现。

但是这里还有一个问题,如何更新堆中的元素呢?我们无法用std::priority_queue更新,因为它没有顺序迭代器。

这个问题的答案是不需要做任何更新,而是无脑地加入。因为 距离源点最小的元素会被最先选出 所以即使有两个重复的元素,也是我们需要的、距离源点较近的元素先被选出,而当距离源点较远的点被选出时,结果集已经被距离源点较近的点更新过了,对所有与它邻接的点,都不会触发更新条件,也就对结果没有影响了。 实现代码如下:

typedef std::pair<uint32_t, int> P;
	/* only when use listGraph, fastDijkstra is faster than normal Dijkstra */
	std::vector<PathNode<value>> fastDijkstra(Vertex& start) {
		std::vector<uint32_t> father(this->getNumberOfVertices(), 0xffffffff);
		std::vector<int> shortest(this->getNumberOfVertices(), INT_MAX);

		// pair.first means index, pair.second means distance
		auto cmp = [](auto i, auto j) { return i.second > j.second; };
		std::priority_queue < P, std::vector<P>, std::function<bool(P, P)>> que(cmp);

		auto start_index = this->getIndex(start);
		que.push(P(start_index, 0));
		shortest[start_index] = 0;
		father[start_index] = start_index;

		while (!que.empty())
		{
			auto now = que.top();
			que.pop();

			int distance_now = now.second;
			for (auto i : this->adjList[now.first]) {
				if (shortest[i.val] > i.edge_value + distance_now) {
					shortest[i.val] = i.edge_value + distance_now;
					father[i.val] = now.first;
					que.push(P(i.val, shortest[i.val]));
				}
			}
		}
		std::vector<PathNode<value>> ret;
		for (auto i = 0u; i < this->getNumberOfVertices(); ++i) {
			PathNode<value> p(Vertex(this->getValue(father[i])), Vertex(this->getValue(i)), shortest[i]);
			ret.push_back(p);
		}
		return ret;
	}

Prim算法同理,只不过这时需要打上标记(因为是无向图,不打上标记的话会重复选择):

	std::vector<std::pair<Vertex, Vertex>> fastPrim() {
		std::vector<temp_edge> vec(this->getNumberOfVertices(), temp_edge(0xfffffff, INT32_MAX));
		auto begin = 0;
		
		auto cmp = [](auto i, auto j) { return i.second > j.second; };
		std::priority_queue<P, std::vector<P>, std::function<bool(P, P)> > pq(cmp);

		pq.push(P(begin, 0));
		while (!pq.empty()) {
			auto now = pq.top();
			pq.pop();
			vec[now.first].mark = true;
			for (auto i : this->adjList[now.first]) {
				if (vec[i.val].value > i.edge_value && vec[i.val].mark == false) {
					vec[i.val].father = now.first;
					vec[i.val].value = i.edge_value;
					pq.push(P(i.val, i.edge_value));
				}
			}
		}

		std::vector<std::pair<Vertex, Vertex>> ret;
		for (auto i = 1u; i < vec.size(); ++i) {
			Vertex v_1(this->getValue(i));
			Vertex v_2(this->getValue(vec[i].father));
			std::pair<Vertex, Vertex> pair(v_1, v_2);
			ret.push_back(pair);
		}
		return ret;
	}