[C++]有向图（邻接数组描述）_c++有向图

基本概念

有向图主要包含两部分：顶点和有向边。本文顶点使用整数1~n表示，有向边使用邻接矩阵记录。
邻接矩阵a为(n+1)*(n+1)的二维数组，其中有效的横坐标x与纵坐标y的范围是1≤x≤n，1≤y≤n。当从顶点v1到顶点v2的有向边存在时，a[v1][v2]用于记录有向边的权值，而无权图相当于所有有向边权值都相等（都等于1）的加权图，无向图则相当于有向边v1->v2与v2->v1同时存在的有向图。对于不存在的有向边(noEdge)，通常记其权值为0或∞，本文均记为0。
当有向图初始化时，所有顶点之间都不存在有向边，于是邻接矩阵的所有项均可初始化为noEdge。之后向该有向图中添加或删除有向边时只需修改邻接矩阵对应位置。

顶点的入度（或出度）表示终点（或起点）为该顶点的有向边的个数。计算时只需在邻接矩阵中找到对应行（或列）根据有向边是否存在进行累加。

遍历：BFS与DFS

广度优先搜索(BFS)和深度优先搜索(DFS)为图的两种遍历方式。广度优先搜索类似于二叉树的层次遍历，借助队列，将起点的邻接顶点全部加入队列中，之后提取队列首项，然后再把提取出的首项的所有还未到达过的邻接顶点加入队列中，循环该操作，直到队列为空。深度优先搜索则是优先沿一个邻接顶点将一条路径走到尽头，然后转换到下一个邻接顶点，利用递归可以实现这种遍历。
这两种遍历方式都需要借助一个一维数组reach[n+1]用来记录每个顶点是否已经到达，若已经出现在其他路径上则不会进入循环或递归。

连通构件

从顶点i 可到达的顶点的集合C与连接C中顶点的边称为连通构件。
如果两个顶点之间找不到一条路径，说明这两个顶点属于不同的连通构件。
从第一个顶点开始，使用BFS或DFS确定与第一个顶点处在同一个连通构件的所有顶点，使用一维数组reach[n+1]记录下这些顶点。然后去找下一个未到达的顶点，进行循环，直到遍历完所有顶点。属于不同连通构件的顶点应当在reach中有不同的记号。
若从第一个顶点开始的BFS或DFS把所有顶点都遍历了，说明该有向图是连通图。

基于BFS寻找两顶点最短路径（无权重）

注意：此处所说的最短路径是指经过顶点个数最少的路径，而不是路径上有向边权重之和最小的路径（本文不介绍最小权值路径的求法，关于最小权值路径的求法，请见 Dijkstra算法 和 Floyd算法 ）。
广度优先搜索是先遍历起点的所有邻接顶点，然后遍历这些邻接顶点的未被遍历到的所有邻接顶点……所以对于遍历到的每个顶点，它们与起点的最短路径即为在这种遍历方式下所产生的路径。
设起点为v1，终点为v2。如果要确定v1v2最短路径上通过的顶点，则需要将reach[n+1]改为reach[2][n+1]，其中第一行既然记录每个顶点是否已经到达，而第二行则记录到达该顶点时，之前的顶点是谁。借助这个二维数组，既可以确定v1与v2是否连通，又可以在v1与v2连通后，从v2回溯到v1，从而确定这条路径上经过的顶点。

拓扑排序

一个复杂的工程通常可以分解成一组简单任务(活动)的集合，完成这些简单任务意味着整个工程的完成。而其中一些简单任务需要在完成其他一些任务的基础上才能开始进行。
于是可以使用有向图对这个工程进行抽象，有向图的每个顶点代表每个简单任务，而有向边则代表任务先后顺序的约束条件，例如进行任务k之前必须完成任务i和任务j，就可以用有向边(i,k)和(j,k)表示。
拓扑排序：给出一个任务的序列，使得对有向图中任意有向边(i,j)，在序列中都有i排在j之前。

算法：
所有的任务可以分为两类：一类是当前没有任何前提任务的任务，这类任务可以在任何时候加入拓扑序列，我们可以用栈对其进行临时储存；另一类是当前有前提任务的任务，这类在需要等待前提任务完成全部之后（全部加入拓扑序列之后），就会变成前一类任务。
首先计算所有节点的入度，用数组inDegree[n+1]存储。注意到一个顶点的入度即为一个任务的前提任务的数量，所以当入度为0的时候，这个任务就可以进入拓扑序列。把一开始就入度为0的顶点压入栈中，然后开始循环出栈：每次出栈都把出栈的顶点加入拓扑序列中，代表这个任务已经完成，然后将那些以这个任务为前提任务的任务顶点入度减1，如果这时这些顶点的入度变为0，则压入栈中。当栈为空时，表示拓扑序列已经生成。

加权无向图的最小生成树

算法详见[C++]Kruskal算法与Prim算法
最小生成树本应只出现在无向图中，不过可视无向图为特殊的有向图，所以生成树的函数也加入到了以下有向图类里面（事实上只是本菜鸡想摸鱼，不想再创建一个无向图类了）

代码

一、有向图代码

#include<iostream>
#include<queue>
#include<stack>
#include"graphChain.h"//链表
#include"minHeap.h"//小根堆
#include"unionFind.h"//并查集
using namespace std;
template<class T>
struct edge//定义有向边
{
	int vertex1;//起点
	int vertex2;//终点
	T weight;//权值，无权图所有边权值都为1
	edge()
	{
		vertex1 = 0;
		vertex2 = 0;
		weight = 0;
	}
	edge(const int& v1, const int& v2, const T& w)
	{
		vertex1 = v1;
		vertex2 = v2;
		weight = w;
	}
	bool operator == (const edge<T>& e) { return vertex1 == e.vertex1 && vertex2 == e.vertex2 && weight == e.weight; }//判断两条有向边是否相等
	operator T() const { return weight; }//类型转换函数，比较大小时强制转换为T类型，比较weight的值
};
template<class T>
class adjacencyWDigraph//邻接矩阵描述的加权有向图
{
protected:
	int n;//顶点个数
	int e;//边个数
	T** a;//邻接矩阵，二维数组,描述每两个顶点之间有向边的权值
	T noEdge;//边不存在
	
public:
	adjacencyWDigraph(int theNumber, T theNoEdge = 0)//初始化
	{
		n = theNumber;
		e = 0;
		noEdge = theNoEdge;
		//设顶点编号为1~n（不包括0）
		a = new T * [n + 1];
		for (int i = 0; i < n + 1; i++)//初始化二维数组，此时所有顶点之间都没有边
		{
			a[i] = new T[n + 1];
			fill(a[i], a[i] + n + 1, noEdge);
		}
	}
	~adjacencyWDigraph()
	{
		for (int i = 0; i < n + 1; i++)
		{
			delete[] a[i];
		}
		delete[] a;
	}
	int numberOfVertices()const { return n; }//顶点数(vertex的复数可以写成verties)
	int numberOfEdges()const { return e; }//有向边数，若为无向图则返回值时边数的2倍
	bool existsEdge(const int& v1,const int& v2) const//判断两点之间的有向边是否存在
	{
		if (v1<1 || v2<1 || v1>n || v2>n || a[v1][v2] == noEdge)
			return false;
		else
			return true;
	}
	void insertEdge(edge<T>* theEdge)//插入有向边
	{
		int v1 = theEdge->vertex1;
		int v2 = theEdge->vertex2;
		if (v1<1 || v2<1 || v1>n || v2>n || v1 == v2)
		{
			cout << "该有向边无效" << endl;
			return;
		}
		if (a[v1][v2] == noEdge)
			e++;
		a[v1][v2] = theEdge->weight;//若有向边已存在，则覆盖其权值
	}
	void eraseEdge(const int& v1, const int& v2)
	{
		if (existsEdge(v1, v2))//先判断该有向边是否存在
			a[v1][v2] = noEdge;
		else
			cout << "该有向边不存在" << endl;
	}
	int getOutDegree(int theVertex)//某一顶点的出度
	{
		int sum = 0;
		for (int i = 1; i <= n; i++)
		{
			if (a[theVertex][i] != noEdge)
				sum++;
		}
		return sum;
	}
	int getInDegree(int theVertex)//某一顶点的入度
	{
		int sum = 0;
		for (int i = 1; i <= n; i++)
		{
			if (a[i][theVertex] != noEdge)
				sum++;
		}
		return sum;
	}
	void bfs(int v, int reach[],int label)//由某一顶点出发的广度优先搜索（队列），reach[]用于记录该顶点是否已经到达；label为到达标记，用于区分连通构件
	{
		queue<int> q;
		reach[v] = label;
		q.push(v);
		while (!q.empty())
		{
			int w = q.front();
			cout << w << " ";//输出顶点
			q.pop();
			for (int i = 1; i <= n; i++)//把所有之前未到达的邻接点都加入队列
			{
				if (a[w][i] != noEdge && reach[i] == 0)
				{
					q.push(i);
					reach[i] = label;
				}
			}
		}
	}
	void bfs_path(int v1, int v2)//通过广度优先搜索确定v1，v2两个顶点之间的的最短路径（不考虑权值）
	{
		if (v1<1 || v1>n || v2<1 || v2>n)
		{
			cout << "无效顶点" << endl;
			return;
		}
		if (v1 == v2)//排除终点与起点重合的情况
		{
			cout << "起点与终点重合" << endl;
			return;
		}
		int** reach = new int* [2];//使用两行来记录顶点的到达情况，第一行记录该顶点是否到达，第二行记录到达该顶点之前的顶点是谁
		reach[0] = new int[n + 1];
		reach[1] = new int[n + 1];
		for (int i = 0; i <= n; i++)
		{
			reach[0][i] = 0;
			reach[1][i] = 0;
		}
		queue<int> q;//用于广度优先搜索的队列
		bool exist = false;//判断是否已经找到v2，即判断v1与v2是否连通
		reach[0][v1] = 1;
		q.push(v1);
		while (!(q.empty() || exist))//广度优先搜索
		{
			int w = q.front();
			q.pop();
			for (int i = 1; i <= n; i++)
			{
				if (a[w][i] != noEdge && reach[0][i] == 0)
				{
					reach[0][i] = 1;//标记该顶点已经到达
					reach[1][i] = w;//记录到达该顶点之前的顶点
					if (i == v2)//找到v2则直接停止搜索
					{
						exist = true;
						break;
					}
					q.push(i);
				}
			}
		}
		if (exist)//如果已经找到v2，则通过reach[][]的第二行回溯到v1，从而确定路径
		{
			stack<int> s;//借助栈将倒序转为正序
			int temp = v2;
			while (temp != 0)
			{
				s.push(temp);
				temp = reach[1][temp];
			}
			int pathLength = -1;//路径上有向边个数=路径上顶点个数-1
			while (!s.empty())
			{
				cout << s.top() << " ";
				s.pop();
				pathLength++;
			}
			cout << "\n路径通过有向边个数：" << pathLength << endl;
		}
		else
			cout << "两顶点不连通" << endl;

	}
	void dfs(int v, int reach[], int label)//由某一顶点出发的深度优先搜索（递归）
	{
		reach[v] = label;
		cout << v << " ";//输出顶点
		for (int i = 1; i <= n; i++)
		{
			if (a[v][i] != noEdge && reach[i] == 0)
			{
				dfs(i, reach, label);//递归
			}
		}
	}
	int labelComponents(int reach[])//获取连通构件的个数，并且在reach[]中作区分
	{
		int label = 0;
		for (int i = 1; i <= n; i++)
		{
			if (reach[i] == 0)
			{
				label++;
				bfs(i, reach, label);
				cout << endl;
			}
		}
		return label;
	}
	bool connected()//判断该图是否连通
	{
		int* reach = new int[n + 1];
		for (int i = 0; i <= n; i++)
			reach[i] = 0;
		dfs(1, reach, 1);
		for (int i = 1; i <= n; i++)
			if (reach[i] == 0)
				return false;
		return true;
	}


    //1.拓扑排序
	bool topologicalOrder(int theOrder[])//把拓扑序列存入theOrder[]中，返回值判断能否产生拓扑序列
	{
		int* inDegree = new int[n + 1];//用于统计每个顶点的入度
		inDegree[0] = 0;
		for (int i = 1; i <= n; i++)
			inDegree[i] = getInDegree(i);
		stack<int> stack;//用于储存可以进入拓扑序列的顶点（相对入度为0）
		for (int i = 1; i <= n; i++)//先把所有入度为0的顶点压入栈中
			if (inDegree[i] == 0)
				stack.push(i);
		int j = 0;//用于记录拓扑序列元素个数
		while (!stack.empty())
		{
			int nextVertex = stack.top();//将栈顶元素加入到拓扑序列中
			stack.pop();
			j++;
			theOrder[j] = nextVertex;
			for (int i = 1; i <= n; i++)//进入拓扑序列之后，说明nextVertex任务已完成，于是“删除”从nextVertex出发的所有有向边，即把它的所有邻接顶点的入度全部减1
			{
				if (a[nextVertex][i] != noEdge)
				{
					inDegree[i]--;
					if (inDegree[i] == 0)//如果减去从nextVertex发来的有向边之后，该顶点的入度变为0，则该顶点也有资格进入拓扑序列，于是进栈
						stack.push(i);
				}
			}
		}
		return (j == n);//判断拓扑序列里顶点个数是否等于图的顶点个数
	}

    //2.Dijkstra算法
	void Dijkstra(int sourceVertex, int targetVertex)//计算两顶点之间最小加权路径
	{
		//以下为初始化，可简化
		T* distanceFromSource = new T[n + 1];//用于记录每一个顶点与源顶点的加权最小总距离
		for (int i = 0; i <= n; i++)//初始化，暂定源顶点到每个顶点有向边的加权距离（若源顶点与某定点不存在有向边，则这段距离是noEdge）
			distanceFromSource[i] = a[sourceVertex][i];

		int* predecessor = new int[n + 1];//用于记录到达该顶点之前经过的顶点是谁
		for (int i = 0; i <= n; i++)//初始化，源顶点的前一个顶点是0，源顶点所有邻接顶点的前一个顶点暂定为源顶点，其他顶点的前一个顶点暂定为-1
			predecessor[i] = -1;
		predecessor[sourceVertex] = 0;
		for (int i = 1; i <= n; i++)
			if (a[sourceVertex][i] != noEdge)
				predecessor[i] = sourceVertex;

		graphChain<int> newReachableVertices;//用于临时储存自身与源顶点最短路径发生了改变的顶点
		for (int i = 1; i <= n; i++)//初始化，先将源顶点的所有邻接顶点存入其中
			if (predecessor[i] > 0)
				newReachableVertices.insert(i);

		//以下开始计算源顶点到所有顶点的最小加权路径
		while (!newReachableVertices.empty())
		{
			//首先找到在newReachableVertices中找出目前与源顶点最近的顶点，然后将其从链表中取出
			chainNode<int>* currentNode = newReachableVertices.firstNode;
			int minDistanceVertex = currentNode->element;//minDistanceVertex表示链表中与源顶点最近的顶点
			while (currentNode->next != NULL)//遍历一遍链表，确定最小值
			{
				currentNode = currentNode->next;
				int temp = currentNode->element;
				if (distanceFromSource[minDistanceVertex] > distanceFromSource[temp])
					minDistanceVertex = temp;
			}
			newReachableVertices.erase(minDistanceVertex);//将其从链表中移除

			for (int i = 1; i <= n; i++)//遍历minDistanceVertex的除了源顶点以外的所有邻接顶点，判断他们与源顶点的最小距离是否要发生改变，如果发生了改变则修改该顶点的predecessor，并将该顶点加入链表中（如果之前不存在于链表中）
			{
				if (a[minDistanceVertex][i] != noEdge && i != sourceVertex)
				{
					if (distanceFromSource[i] == noEdge || distanceFromSource[i] > distanceFromSource[minDistanceVertex] + a[minDistanceVertex][i])
					{
						distanceFromSource[i] = distanceFromSource[minDistanceVertex] + a[minDistanceVertex][i];
						predecessor[i] = minDistanceVertex;
						if (newReachableVertices.indexOf(i) == -1)
							newReachableVertices.insert(i);
					}
				}
			}
		}

		//然后输出需要的最小加权路径信息
		if (distanceFromSource[targetVertex] != noEdge)//源顶点与目标顶点连通
		{
			stack<int> stack;//利用栈，从终点回溯到源顶点
			stack.push(targetVertex);
			int temp = predecessor[targetVertex];
			while (temp != 0)//一直找到源顶点
			{
				stack.push(temp);
				temp = predecessor[temp];
			}
			cout << "最小加权路径经过的顶点：";
			while (!stack.empty())
			{
				cout << stack.top()<<" ";
				stack.pop();
			}
			cout << "\n最小加权路径长度：" << distanceFromSource[targetVertex]<<endl;
		}
		else
		{
			cout << "两顶点不连通" << endl;
		}

	}
	
	//3.Floyd算法
	void Floyd(T** minDistance, int** passBy)//计算任两顶点之间的最短距离。将最短距离存入二维数组minDistance中，将最后一次经过的顶点存入二维数组passBy中（用于记录具体最短路径）
	{
		for (int i = 0; i <= n; i++)//当k=0时，任两点的路径都不允许经过任何其他顶点，minDistance此时就是有向图的邻接矩阵
		{
			for (int j = 0; j <= n; j++)
			{
				minDistance[i][j] = a[i][j];
				passBy[i][j] = 0;
			}
		}

		for (int k = 1; k <= n; k++)
		{
			for (int i = 1; i <= n; i++)
			{
				for (int j = 1; j <= n; j++)
				{
					//当k增加了一个的时候，检查两顶点的最短路径是否因为加入的新顶点而发生改变，即最短路径是否因经过新顶点而变短
					if (i!=j && minDistance[i][k] != noEdge && minDistance[k][j] != noEdge && (minDistance[i][j] == noEdge || minDistance[i][j] > minDistance[i][k] + minDistance[k][j]))
					{
						minDistance[i][j] = minDistance[i][k] + minDistance[k][j];
						passBy[i][j] = k;//每经过一个新顶点，就用新顶点覆盖一次
					}
				}
			}
		}
		//循环结束之后，minDistance所存数据即为两顶点之间有向最短路径的长度
	}
	void Floyd_getPath(int** passBy, int start, int end)//利用passBy[][]，递归输出两顶点最短路径上经过的顶点（不输出起点）
	{
		if (start == end)
			return;
		if (passBy[start][end] == 0)//等于0说明这两点之间的最短路径没有经过其他任何顶点
			cout << end << " ";
		else//若经过了其他顶点，则分两半递归
		{
			Floyd_getPath(passBy, start, passBy[start][end]);
			Floyd_getPath(passBy, passBy[start][end], end);
		}
	}

    //4.Kruskal算法
	bool Kruskal(edge<T> spanningTreeEdges[])//最小生成树，生成树的所有边存放到spanningTreeEdges[]中
	{
		edge<T>* edgeArray = new edge<T>[e + 1];//用于存放图的所有边
		edgeArray[0] = edge<T>(0, 0, 0);
		int k = 0;
		int numberOfEdge = e;
		for (int i = 1; i <= n; i++)//将图的所有边存入数组
		{
			for (int j = 1; j <= n; j++)
			{
				if (a[i][j] != noEdge)
				{
					k++;
					edgeArray[k] = edge<T>(i, j, a[i][j]);
				}
			}
		}
		minHeap<edge<T>> heap(edgeArray, e, e + 1);//将边的数组放入小根堆
		unionFind uf(n);//并查集
		k = 0;
		while (numberOfEdge > 0 && k < n - 1)
		{
			edge<T> x = heap.front();//取出堆中的最小边
			heap.pop();
			numberOfEdge--;
			int a = uf.find(x.vertex1);//比较取出边的两顶点是否在同一子图中，从而判断加入这条边后是否会成环
			int b = uf.find(x.vertex2);
			if (a != b)//如果不成环就将这条边加入到生成树中
			{
				spanningTreeEdges[k] = x;
				k++;
				uf.unite(a, b);//此时这两个顶点已经连通，所以要将它们在并查集中的根节点合并
			}
		}
		return k == n - 1;//返回是否能够产生最小生成树
	}
	
	//5.Prim算法
	bool Prim(edge<T> spanningTreeEdges[])//最小生成树，生成树的所有边存放到spanningTreeEdges[]中
	{
		graphChain<edge<T>> edgeChain;//用链表存放所有边
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (a[i][j] != noEdge)
				{
					edge<T> newEdge(i, j, a[i][j]);
					edgeChain.insert(newEdge);//此处insert方法确保链表按照从小到大排序
				}
			}
		}
		int* treeVertex = new int[n + 1];//记录已经存在于树中的顶点，0代表不存在，1代表存在
		for (int i = 0; i <= n; i++)
			treeVertex[i] = 0;
		treeVertex[1] = 1;//此算法默认从1开始生成树
		int k = 0;//k记录生成树的边数，生成树的边存放在spanningTreeEdges[]中

		while ((!edgeChain.empty()) && k < n - 1)
		{
			chainNode<edge<T>>* currentNode = edgeChain.firstNode;
			//以下表示用currentNode找到有序链表中的一条边，这条边满足一个顶点在树中，另一个顶点不在树中
			while (currentNode!=NULL&&(!((treeVertex[currentNode->element.vertex1] == 1 && treeVertex[currentNode->element.vertex2] == 0) || (treeVertex[currentNode->element.vertex1] == 0 && treeVertex[currentNode->element.vertex2] == 1))))
			{
				currentNode = currentNode->next;
			}
			if (currentNode == NULL)//如果没找到这种边则直接退出循环
				break;
			edge<T> theNode(currentNode->element.vertex1, currentNode->element.vertex2, currentNode->element.weight);
			edgeChain.erase(theNode);
			spanningTreeEdges[k] = theNode;
			treeVertex[theNode.vertex1] = 1;
			treeVertex[theNode.vertex2] = 1;
			k++;
		}
		return k == n - 1;
	}
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463

二、头文件代码
1.链表graphChain.h

#pragma once
template<class T>
struct chainNode//定义链表节点
{
	T element;
	chainNode<T>* next;
	chainNode() {}
	chainNode(const T& element)
	{
		this->element = element;
	}
	chainNode(const T& element, chainNode<T>* next)
	{
		this->element = element;
		this->next = next;
	}
};
template<class T>
class graphChain//定义链表
{
public:
	chainNode<T>* firstNode;
	int listSize;
	graphChain()
	{
		firstNode = NULL;
		listSize = 0;
	}
	bool empty() const { return listSize == 0; }
	int indexOf(const T& theElement)const//获取指定节点在链表中的坐标，若该节点不存在则返回-1
	{
		chainNode<T>* currentNode = firstNode;
		int index = 0;
		while (currentNode != NULL && currentNode->element != theElement)
		{
			currentNode = currentNode->next;
			index++;
		}
		if (currentNode == NULL)
			return -1;
		else
			return index;
	}
	void insert(const T& theElement)//插入需要保证链表从小到大有序
	{
		if (firstNode == NULL || theElement < firstNode->element)
			firstNode = new chainNode<T>(theElement, firstNode);
		else
		{
			chainNode<T>* currentNode = firstNode;
			while (currentNode->next != NULL && theElement >= currentNode->next->element)
				currentNode = currentNode->next;
			chainNode<T>* newNode = new chainNode<T>(theElement, currentNode->next);
			currentNode->next = newNode;
		}
		listSize++;
	}
	bool erase(const T& theElement)//删除某节点，返回值表示删除是否成功（删除节点是否存在）
	{
		chainNode<T>* deleteNode;
		if (theElement == firstNode->element)//删除首项
		{
			deleteNode = firstNode;
			firstNode = firstNode->next;
		}
		else
		{
			chainNode<T>* currentNode = firstNode;
			while (currentNode->next != NULL && currentNode->next->element != theElement)
				currentNode = currentNode->next;
			if (currentNode->next == NULL)//没找到该节点则返回false
				return false;
			deleteNode = currentNode->next;
			currentNode->next = currentNode->next->next;
		}
		listSize--;
		delete deleteNode;
		return true;//删除成功返回true
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

2.小根堆minHeap.h

#pragma once
using namespace std;
template<class T>
class minHeap//小根堆类
{
public:
	minHeap(int initlength = 100)
	{
		arrayLength = initlength;
		heap = new T[arrayLength];
		heap[0] = NULL;
		heapSize = 0;
	}
	minHeap(T* theHeap, int theSize, int theLength)//利用已知数组创建小根堆
	{
		heap = theHeap;
		heapSize = theSize;
		arrayLength = theLength;
		//将传入的数组堆化
		for (int root = heapSize / 2; root >= 1; root--)//heap[heapSize/2]是堆中最后一个有子节点的节点，从该节点开始向前遍历
		{
			T rootElement = heap[root];
			int child = root * 2;//左子节点的下标
			while (child <= heapSize)
			{
				if (child<heapSize && heap[child]>heap[child + 1])//从左子节点和右子节点中找出较小的
					child++;
				if (rootElement <= heap[child])//若根节点比两个子节点都小，则不再需要交换，又因为子节点以下都已经排好顺序，所以直接退出循环
					break;
				heap[child / 2] = heap[child];//若根节点大于其中一个子节点，则交换，然后在交换完之后的位置上继续向下考察
				child *= 2;
			}
			heap[child / 2] = rootElement;
		}

	}
	T front()//获取堆中首项，即最小值
	{
		return heap[1];
	}
	bool empty()
	{
		return heapSize == 0;
	}
	void push(const T& theElement)//插入元素
	{
		if (heapSize == arrayLength - 1)//数组若满长度加倍
		{
			T* newHeap = new T[arrayLength * 2];
			for (int i = 0; i < arrayLength; i++)
				newHeap[i] = heap[i];
			delete[]heap;
			heap = newHeap;
			arrayLength *= 2;
		}
		heapSize++;
		int currentNode = heapSize;//新节点是最后一个节点
		while (currentNode != 1 && heap[currentNode / 2] > theElement)//从新节点开始向上考察其父节点，若父节点比当前节点大，则交换位置
		{
			heap[currentNode] = heap[currentNode / 2];
			currentNode /= 2;
		}
		heap[currentNode] = theElement;
	}
	void pop()//删除最小元素，即删除heap[1]
	{
		if (heapSize == 0)//当前堆为空，则直接退出
		{
			cout << "空堆" << endl;
			return;
		}
		heap[1].~T();
		//重建小根堆，由于需要保持完全二叉树的性质，所以在尽可能调用堆的最后一个节点来补足空位
		T lastElement = heap[heapSize];
		heapSize--;
		int currentNode = 1;//此时该位为空，需要由最后一个节点或子节点来补足
		int child = 2;
		while (child <= heapSize)
		{
			if (child<heapSize && heap[child]>heap[child + 1])//选择子节点中较小的一个
				child++;
			if (lastElement <= heap[child])//若最后一个结点比子节点小，则结束循环，由最后一个节点来补足空位
				break;
			heap[currentNode] = heap[child];//否则由子节点来补足空位，然后继续向下考察
			currentNode = child;
			child *= 2;
		}
		heap[currentNode] = lastElement;
	}
private:
	T* heap;//堆中元素存放在数组中
	int arrayLength;//数组容量
	int heapSize;//堆中元素个数
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

3.并查集unionFind.h

#pragma once
using namespace std;
class unionFind//定义并查集
{
public:
	unionFind(int numberOfElements)//初始化，所有节点都是根节点
	{
		parent = new int[numberOfElements + 1];
		for (int i = 1; i <= numberOfElements; i++)
			parent[i] = 0;
	}
	int find(int theElement)//查询theElement的根节点是谁
	{
		while (parent[theElement] != 0)
			theElement = parent[theElement];
		return theElement;
	}
	void unite(int a, int b)//让a成为b的父节点
	{
		parent[b] = a;
	}
private:
	int* parent;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24