数据结构——图

2022-02-27 18:22:56

1 基本术语

  • 有向图：图中的每条边都有方向的图叫有向图。此时，边的两个顶点有次序关系，有向边<u,v>成为从顶点u到顶点v的一条弧，u成为弧尾（始点），v成为弧头（终点），即有向图中弧<u,v>和弧<v,u>表示不同的两条边。
  • 无向图：图中的每条边没有方向的图。边的两个顶点没有次序关系，无向图用边(u,v)表示对称弧<u,v>和<v,u>。
  • 权：图中的边或弧上有附加的数量信息，这种可反映边或弧的某种特征的数据成为权。
  • 网：图上的边或弧带权则称为网。可分为有向网和无向网。
  • 邻接和关联：若边e=(u,v)或弧e=<u,v>，则称点u和v互为邻接顶点，并称边e或弧e关联于顶点u和v。
  • 度：在无向图中，与顶点v关联的边的条数成为顶点v的度。有向图中，则以顶点v为弧尾的弧的条数成为顶点v的出度，以顶点v为弧头的弧的条数成为顶点v的入度，而顶点v的度=出度+入度。图中各点度数之和是边（或弧）的条数的2倍。
  • 圈：图中联接同一个顶点的边叫圈。
  • 平行边：图中两个顶点之间若有两条或两条以上的边，称这些边为平行边。
  • 简单图：没有圈也没有平行边的图。
  • 有向完全图：有n个顶点，n(n-1)条弧的有向图。每两个顶点之间都有两条方向相反的边连接的图。
  • 完全图：有n个顶点，n(n-1)/2条边的无向图。若一个图的每一对不同顶点恰有一条边相连，则称为完全图。完全图是每对顶点之间都恰连有一条边的简单图。
  • 路径长度：路径上边或弧的数目。若路径上的各顶点均不相同，则称这条路经为简单路经（或路），除第一个和最后一个顶点相同外，其他各顶点均不相同的路径成为回路（或环）。
  • 连通图：在无向图G中，对与图中的任意两个顶点u、v都是连通的，则称图G为连通图。
  • 强连通图：在有向图G中，如果对于每一对Vi和Vj 属于顶点集V，Vi不等于Vj ，从Vi到Vj和从Vj到Vi都存在路径，则称G是强连通图。
  • 强连通分量：有向图中的极大强连通子图称做有向图的强连通分量。
  • 生成树：一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。
  • 有向树：如果一个有向图恰有一个顶点的入度为0，其余顶点的入度为1，则是一棵有向树。

2 图的存储结构

2.1 邻接矩阵表示法

    图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。

    设图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：

    数据结构——图

    看一个实例，下图左就是一个无向图。

    数据结构——图

    从上面可以看出，无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴，右上角的元和左下角相对应的元全都是相等的。

    从这个矩阵中，很容易知道图中的信息。

    （1）要判断任意两顶点是否有边无边就很容易了；

    （2）要知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行或（第i列）的元素之和；

    （3）求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1就是邻接点；

    而有向图讲究入度和出度，顶点vi的入度为1，正好是第i列各数之和。顶点vi的出度为2，即第i行的各数之和。

    若图G是网图，有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：

    数据结构——图

    这里的wij表示(vi,vj)上的权值。无穷大表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。下面左图就是一个有向网图，右图就是它的邻接矩阵。

    数据结构——图

2.2 邻接表表示法

    邻接矩阵是不错的一种图存储结构，但是，对于边数相对顶点较少的图，这种结构存在对存储空间的极大浪费。因此，找到一种数组与链表相结合的存储方法称为邻接表。

    邻接表的处理方法是这样的：

    （1）图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过，数组可以较容易的读取顶点的信息，更加方便。

    （2）图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以，用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。

    例如，下图就是一个无向图的邻接表的结构。

    数据结构——图

    从图中可以看出，顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。

    对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可。如下图所示。

    数据结构——图

  • 若无向图（或网）中有n个顶点、e条边，则它的邻接表需n个头结点和2e个表结点。对于稀疏图而言，用邻接表表示法比邻接矩阵表示法节省存储空间。临街表中顶点vi的度恰为第i个链表中的结点数。
  • 若有向图（或网）中有n个顶点、e条弧，则它的邻接表需n个头结点和e个表结点。顶点vi的出度为第i个链表中的结点数，但要计算这个顶点的入度则需遍历所有邻接表。
  • 有时为了方便求一个顶点的入度，或者如果需要反复访问一个结点的直接前驱，可以建立一个有向图（或网）的逆邻接表，即对每个顶点vi建立一个链表，用以链接以顶点vi为头的弧。

2.3 邻接多重表表示法

    在无向图（或网）的邻接表表示法中，每一条边(u,v)需要两个表结点表示，一个在顶点u的链表中，另一个在定点v的链表中。如果每条边只用一个表结点表示，且同时位于这条边所关联的两个顶点的链表中，这样的存储结构成为邻接多重表。
    邻接表表示法不便于对已访问的边做标记，或者删除图中某一条边等。因此，在进行这类操作的无向图中用邻接多重表做存储结构更为适应。此外，除了在边结点中增加一个标志域外，邻接多重表所需的存储量和邻接表相同。

2.4 十字链表表示法

    对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才知道，反之，逆邻接表解决了入度却不了解出度情况。下面介绍的这种有向图的存储方法：十字链表，就是把邻接表和逆邻接表结合起来的。

    重新定义顶点表结点结构，如下所示。

    数据结构——图

    其中firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout表示出边表头指针，指向该顶点的出边表中的第一个结点。

    重新定义边表结构，如下所示。

    数据结构——图

    其中，tailvex是指弧起点在顶点表的下表，headvex是指弧终点在顶点表的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向起点相同的下一条边。如果是网，还可以增加一个weight域来存储权值。

    比如下图，顶点依然是存入一个一维数组，实线箭头指针的图示完全与邻接表相同。就以顶点v0来说，firstout指向的是出边表中的第一个结点v3。所以，v0边表结点hearvex = 3，而tailvex其实就是当前顶点v0的下标0，由于v0只有一个出边顶点，所有headlink和taillink都是空的。

    数据结构——图

    重点需要解释虚线箭头的含义。它其实就是此图的逆邻接表的表示。对于v0来说，它有两个顶点v1和v2的入边。因此的firstin指向顶点v1的边表结点中headvex为0的结点，如上图圆圈1。接着由入边结点的headlink指向下一个入边顶点v2，如上图圆圈2。对于顶点v1，它有一个入边顶点v2，所以它的firstin指向顶点v2的边表结点中headvex为1的结点，如上图圆圈3。

    十字链表的好处就是因为把邻接表和逆邻接表整合在一起，这样既容易找到以v为尾的弧，也容易找到以v为头的弧，因而比较容易求得顶点的出度和入度。

    而且除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图应用中，十字链表是非常好的数据结构模型。

3 图的邻接表表示法实现

#ifndef _ALGRAPH_H_
#define _ALGRAPH_H_

#include <Windows.h>
#define MAX_VERTEX_NUM 20

enum GraphStyle
{
	DG,     //有向图
	DN,     //有向网
	UDG,    //无向图
	UDN     //无向网
};

class EdgeNode
{
	EdgeNode(int = -1, int = 0);
	int adjVertex;
	int weight;
	EdgeNode* next;
};

EdgeNode::EdgeNode(int a, int w):adjVertex(a),weight(w),next(NULL)
{
}

template<class T> class VertexNode
{
public:
	void ClearEdgeList(); //删除该点的邻接表
	bool AppendEdge(int, int = 0);
	bool RemoveEdge(int);
	T data;
	EdgeNode* edgeList; //指向第一条依附于该顶点的边的指针
};

template<class T> void VertexNode<T>::ClearEdgeList()
{
	EdgeNode *p,*q;
	p = edgeList;
	while(p != NULL)
	{
		q = p->next;
		delete p;
		p = q;
	}
	edgeList = NULL;
}

template<class T> bool VertexNode<T>::AppendEdge(int v, int wgh)
{
	EdgeNode* p = edgeList;
	EdgeNode* q = NULL;
	while (p != NULL)
	{
		if (p->adjVertex == v)
		{
			return false;
		}
		q = p;
		p = p->next;
	}

	p = new EdgeNode(v,wgh);
	if (q == NULL)
	{
		edgeList = p;
	}
	else
	{
		q->next = p;
	}
	return true;
}

template<class T> bool VertexNode<T>::RemoveEdge(int v)
{
	ASSERT(edgeList);
	EdgeNode* p = edgeList;
	EdgeNode* q = NULL;
	while(p != NULL)
	{
		if (p->adjVertex == v)
		{
			if (p == edgeList)
			{
				edgeList = p->next;
			}
			else
			{
				q->next = p->next;
			}
			delete p;
			return true;
		}
		q = p;
		p = p->next;
	}
	return false;
}

template<class T> class ALGraph
{
public:
	ALGraph(int = 0, GraphStyle = UDG);
	~ALGraph();
	int LocateVertex(const T&);
	inline int GetNumVertices(){return numVertices;}
	bool GetVertex(int, T&);
	bool SetVertex(int, const T&);
	bool InsertVertex(const T&);
	bool DeleteVertex(const T&);
	bool InsertEdge(const T&,const T&,int = 0);
	bool DeleteEdge(const T&,const T&);
	int GetFirstAdjVex(int);
	int GetNextAdjVex(int v, int w);
	bool GetEdge(int, int, EdgeNode*&);
	inline int GetNumEdges();
	void DFSTraverse(void (*Visit)(const T&));
	void BFSTraverse(void (*Visit)(const T&));
private:
	void DFS(void (*Visit)(const T&),int); //深度优先遍历
	VertexNode<T>* vertices;
	int numVertices;
	int numEdges;
	int maxVertices;
	GraphStyle style;
	bool *visited;
};

template<class T> bool ALGraph<T>::GetVertex(int v, T& vex)
{
	if (v < 0 || v >= numVertices)
	{
		return false;
	}
	vex = vertices[v].data;
	return true;
}

template<class T> bool ALGraph<T>::SetVertex(int v, const T& vex)
{
	if (v < 0 || v >= numVertices)
	{
		return false;
	}
	vertices[v].data = vex;
	return true;
}

template<class T> ALGraph<T>::ALGraph(int s, GraphStyle gs):numVertices(0),numEdges(0),
	maxVertices(s),style(s)
{
	if (s > 0)
	{
		vertices = new VertexNode<T>[s];
	}
}

template<class T> ALGraph<T>::~ALGraph()
{
	for (int i = 0; i < numVertices; i++)
	{
		vertices[i].ClearEdgeList();
	}
	if (maxVertices != 0)
	{
		delete [] vertices;
	}
}

template<class T> bool ALGraph<T>::InsertVertex(const T& vex)
{
	if (numVertices >= maxVertices)
	{
		return false;
	}
	for (int i = 0; i < numVertices; i++)
	{
		if (vertices[i].data == vex)
		{
			return false;
		}
	}
	vertices[numVertices].data = vex;
	vertices[numVertices++].edgeList = NULL;
	return true;
}

template<class T> bool ALGraph<T>::DeleteVertex(const T& vex)
{
	int i, v;
	if ((v = LocateVertex(vex)) == -1)
	{
		return false;
	}

	for (int i = 0; i < numVertices; i++)
	{
		if (i != v)
		{
			if (vertices[i].RemoveEdge(v))
			{
				numEdges--;
			}
		}
	}
	vertices[v].ClearEdgeList();
	for (i = v; i < numVertices - 1; i++)
	{
		vertices[i] = vertices[i + 1];
	}
	numVertices--;

	EdgeNode* p;
	for(int i = 0; i < numVertices; i++)
	{
		p = vertices[i].edgeList;
		while(p != NULL)
		{
			if (p->adjVertex >= v) //判断邻接顶点号是否大于要删除的顶点号
			{
				p->adjVertex--;
			}
			p = p->next;
		}
	}
	return true;
}

template<class T> int ALGraph<T>::LocateVertex(const T& vex)
{
	for (int i = 0; i < numVertices; i++)
	{
		if (vertices[i].data == vex)
		{
			return i;
		}
	}
	return -1;
}

template<class T> bool ALGraph<T>::InsertEdge(const T& vex1,const T& vex2,int wgh)
{
	int v1 = LocateVertex(vex1);
	int v2 = LocateVertex(vex2);
	if (v1 = -1 || v2 == -1)
	{
		return false;
	}

	vertices[v1].AppendEdge(v2,wgh);
	if (style === UDG || style == UDN)
	{
		vertices[v2].AppendEdge(v1,wgh);
	}
	numEdges++;

	return true;
}

template<class T> bool ALGraph<T>::DeleteEdge(const T& vex1,const T& vex2)
{
	int v1 = LocateVertex(vex1);
	int v2 = LocateVertex(vex2);
	if (v1 == -1 || v2 == -1)
	{
		return false;
	}

	vertices[v1].RemoveEdge(v2);
	if (style == UDG || style == UDN)
	{
		vertices[v2].RemoveEdge(v1);
	}
	numEdges--;
	return true;
}

template<class T> void ALGraph<T>::DFSTraverse(void (*Visit)(const T&))
{
	int v;
	visited = new bool[numVertices];
	for (v = 0; v < numVertices; v++)
	{
		visited[v] = false;
	}
	
	for (v = 0; v < numVertices; v++)
	{
		if (!visited[v])
		{
			DFS(Visit,v);
		}
	}
	delete [] visited;
}

template<class T> void ALGraph<T>::DFS(void (*Visit)(const T&), int v)
{
	visited[v] = true;
	Visit(vertices[v].data);
	EdgeNode* p = vertices[v].edgeList;
	while(p != NULL)
	{
		int w = p->adjVertex;
		if (!visited[v])
		{
			DFS(Visit,w);
		}
		p = p->next;
	}
}

template<class T> void ALGraph<T>::BFSTraverse(void (*Visit)(const T&))
{
	int v;
	queue<int> vertexQueue;
	EdgeNode* p;
	visited = new bool[numVertices];
	for (v = 0; v < numVertices; v++)
	{
		visited[v] = false;
	}

	for (v = 0; v < numVertices; v++)
	{
		if (visited[v])
		{
			continue;
		}
		visited[v] = true;
		Visit(vertices[v].data);
		vertexQueue.push(v);

		while (!vertexQueue.empty())
		{
			int u = vertexQueue.front();
			vertexQueue.pop();
			p = vertices[v].edgeList;
			while (p != NULL)
			{
				int w = p->adjVertex;
				if (!visited[w])
				{
					visited[w] = true;
					Visit(vertices[w].data);
					vertexQueue.push(w);
				}
				p = p->next;
			}
		}
	}
	delete [] visited;
}
#endif


4 图的遍历

        图的遍历操作方法有两种：一种是深度优先搜索，简称DFS（Depth First Search）算法；另一种是广度优先搜索，简称BFS（Breadth First Search）算法。它们对有向图和无向图均使用。

4.1 深度优先搜索

        深度优先搜索首先选择图中某个顶点u作为起始点进行访问，然后依次从u的未被访问的邻接点v出发深度优先搜索遍历图，直至图中所有和u有路径相通的顶点都被访问到；若图中还有顶点未被访问到，则另选图中一个未被访问的顶点作为起始点，重复上述过程，直到所有顶点都被访问到。
        对于深度优先搜索算法，遍历图的过程实质上是对每个顶点查找其邻接点的过程，耗费的时间取决于所采用的存储结构。当用邻接表来表示图进行DFS时，需要访问表头向量时间为O(n)，访问边或弧的时间为O(e)，因此DFS算法的时间复杂度是O(n+e)。

4.2 广度优先搜索

        广度优先搜索类似于树的层次遍历。
        首先访问起始点u，依次访问u的每个未曾访问到的邻接点，然后按被访问的顺序分别从这些邻接点出发，依次访问它们的邻接点，直至图中所有已被访问的邻接点都被访问到。若此时图中还有顶点未被访问到，则另选一个未被访问的顶点作为起始点，重复上述过程，直到图中所有顶点全部被访问到。
        对于广度优先搜索算法，每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接点的过程，当以邻接表做存储结构时，BFS算法的时间复杂度是O(n+e)。

5 求强连通分量

Kosaraju算法描述：
step1：对原图G进行深度优先遍历，记录每个节点的离开时间。
step2：选择具有最晚离开时间的顶点，对反图GT进行遍历，删除能够遍历到的顶点，这些顶点构成一个强连通分量。
step3：如果还有顶点没有删除，继续step2，否则算法结束。

6 最小生成树

        MST（Minimum Spanning Tree）性质：设G=(V，E)是一个连通网络，U是顶点集V的一个非空子集。若(u，v)是G中一条一个端点在U中(例如：u∈U)，另一个端点不在U中的边(例如：v∈V-U)，且(u，v)具有最小权值，则一定存在G的一棵最小生成树包括此边(u，v)。
        求最小生成树主要有Prim算法和Kruskal算法等，其中大多数算法都是基于最小生成树的性质。

6.1 Prim算法

算法描述如下：
1) 输入：一个加权连通图，其中顶点集合为V，边集合为E；
2) 初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
3) 重复下列操作，直到Vnew = V：
    a 在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
    b 将v加入集合Vnew中，将<u, v>边加入集合Enew中；
4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。
实现代码：
#pragma region Prim算法
//返回给定数组中，非0最小元素的下标值
int Minimum(int arr[], int n)
{
	int i;
	int min = 0;
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > 0)
		{
			min = i;
			break;
		}
	}
	for (i = min; i < n; i++)
	{
		if (arr[i] > 0 && arr[i] < arr[min])
		{
			min = i;
		}
	}

	return min;
}

//从第0个顶点出发，计算并打印网g的最小生成树
template<class T> void Prim(ALGraph<T>& g)
{
	if (g.GetNumVertices() == 0)
	{
		cout<<"图中无顶点"<<endl;
		return;
	}

	int i, j, k = 0;
	T vex;
	EdgeNode* edge = NULL;
	int* lowcost = new int[g.GetNumVertices()];
	T* U = new T[g.GetNumEdges()];

	for (i = 0; i < g.GetNumVertices(); i++)
	{
		lowcost[i] = INT_MAX;
	}

	for (i = 0; i <　g.GetNumVertices(); i++)
	{
		if (i != k && g.GetEdge(k,i,edge))
		{
			lowcost[i] = edge->weight;
			g.GetVertex(k,U[i]);
		}
	}

	g.GetVertex(k, U[k]);
	lowcost[k] = 0;

	for (i = 1; i < g.GetNumVertices(); i++)
	{
		k = Minimum(lowcost,g.GetNumVertices());
		g.GetVertex(k,vex);
		cout<<U[k]<<"-->"<<vex<<":"<<lowcost[k]<<endl;
		lowcost[k] = 0;

		for (j = 0; j < g.GetNumVertices(); j++)
		{
			if (g.GetEdge(k,j,edge) && edge->weight < lowcost[j]))
			{
				lowcost[j] = edge->weight;
				g.GetVertex(k,U[j]);
			}
		}
	}

	delete [] lowcost;
	delete [] U;
}
#pragma endregion
Prim算法时间复杂度是O(n^2)，与网中边的数目无关，因此适合于求边稠密的网的最小生成树。

6.2 Kruskal算法

       Prim算法是一种“步步为营”的算法，每一步生成的结果均为最终结果的一部分。它虽然每次都是从连接集合V-U和U中选最小的边，但选出的边的权值不一定为所有的尚未选出的属于最小生成树的边的权值最小者，换言之，Prim算法不是按边的权值非递减的次序生成最小生成树的。
       Kruskal算法与Prim算法不同，它按边的权值非递减的次序生成最小生成树，即若某边是最小生成树中第i小的边，则它在第1~i-1小的边全部选出后才加入到部分结果中。但是Kruskal算法并不保证每步生成的结果是连通的。
算法描述：
1) 记Graph中有v个顶点，e个边
2) 新建图Graphnew，Graphnew中拥有原图中相同的e个顶点，但没有边
3) 将原图Graph中所有e个边按权值从小到大排序
4) 循环：从权值最小的边开始遍历每条边，直至图Graph中所有的节点都在同一个连通分量中
                if 这条边连接的两个节点于图Graphnew中不在同一个连通分量中
                          添加这条边到图Graphnew中

7 拓扑排序

       对一个有向无环图(Directed Acyclic Graph，简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
       顶点活动网：顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。
拓扑排序基本算法：
1) 从有向图中选取一个没有前驱的顶点，并输出。
2) 从有向图中删去此顶点以及所有以它为尾的弧。
重复上述步骤，直到图空，或者图不空但找不到无前驱的顶点为止。
#pragma region 拓扑排序
//对图中的顶点求入度，存入inArr
template<class T> void FindInDegree(ALGraph<T>& g, int inArr[])
{
	int i,v;
	for (i = 0; i < g.GetNumVertices(); i++)
	{
		inArr[i] = 0;
	}
	for (i = 0; i < g.GetNumVertices(); i++)
	{
		v = g.GetFirstAdjVex(i);
		while(v != -1)
		{
			inArr[v]++;
			v = g.GetNextAdjVex(i,v);
		}
	}
}

template<class T> bool TopologicalSort(ALGraph<T>& g, int* topoArr)
{
	queue<int> q; //存放度为0的顶点的序号
	T vex;
	int count = 0;
	int i;
	int w;
	int* inDegree = new int[g.GetNumVertices()];

	FindInDegree(g,inDegree);
	for (i = 0; i < g.GetNumVertices(); i++)
	{
		if (inDegree[i] == 0)
		{
			q.push(i)
		}
	}

	i = 0;
	while(!q.empty())
	{
		topoArr[i++] = q.front();
		for (w = g.GetFirstAdjVex(q.front()); w != -1;
			w = g.GetNextAdjVex(q.front(),w))
		{
			if (--inDegree[w] == 0)
			{
				q.push(w);
			}
		}
		q.pop();
		count++;
	}

	delete [] inDegree;
	return count == g.GetNumVertices();
}
#pragma endregion
分析上述程序，对于有n个顶点和e条弧的有向图来说，建立各顶点的入度的时间复杂度为O(n+e)，建立入度为0的顶点队列的时间复杂度为O(n)。在拓扑过程中，若有向图无环，则每个顶点入队列和出队列一次，入度减1的操作执行e此，所以拓扑排序总的时间复杂度为O(n+e)。

8 关键路径

        在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在带权有向图中若以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间，这样的图简称为AOE网。

8.1 相关概念

1．关键路径
AOE网中，从事件i到j的路径中，加权长度最大者称为i到j的关键路径（Critical Path），记为cp(i,j)。特别地，始点0到终点n的关键路径cp(0,n)是整个AOE的关键路径。
显然，关键路径决定着AOE网的工期，关键路径的长度就是AOE网代表的工程所需的最小工期。
2．事件最早/晚发生时间
事件vi的最早发生时间ve(i)定义为：从始点到vi的最长（加权）路径长度，即cp(0,i)
事件vi的最晚发生时间vl(i)定义为：在不拖延整个工期的条件下，vi的可能的最晚发生时间。即vl(i) = ve(n) - cp(i, n)
3．活动最早/晚开始时间
活动ak=<vi, vj>的最早开始时间e(k)：等于事件vi的最早发生时间，即
     e(k) = ve(i) = cp(0, i)
活动ak=<vi, vj>的最晚开始时间l(k)定义为：在不拖延整个工期的条件下，该活动的允许的最迟开始时间，即
        l(k) = vl(j) – len(i, j)
这里，vl(j)是事件j的允许的最晚发生时间，len(i, j)是ak的权。
活动ak的最大可利用时间：定义为l(k)-e(k)
 4．关键活动
若活动ak的最大可利用时间等于0（即(l(k)=e(k)），则称ak 为关键活动，否则为非关键活动。
显然，关键活动的延期，会使整个工程延期。但非关键活动不然，只要它的延期量不超过它的最大可利用时间，就不会影响整个工期。

8.2 相关算法

为了求得AOE网中活动的e(i)和e(j)，首先应求得事件的最早开始时间和ve(j)和最迟发生时间vl(j)。
假设第i个活动ai的弧尾<j,k>，其持续时间为dut(<j,k>)，则有：
e(i) = ve(j);
l(i) = vl(k) - dut(<j,k>)
事件（顶点）发生时间的计算公式为：
ve(1) = 0
ve(k) = Max{ve(j) + dut(<j,k>)}     k为弧头
vl(n) = vl(n)
vl(j) = Min{vl(k) - dut(<j,k>)}          j为弧尾
求关键路径算法描述：
（1） 输入e条弧<j,k>；，建立AOE网的存储结构。
（2） 从源点v1出发，令ve（1）=0，求 ve(j) 2<=j<=n。
（3） 从汇点vn出发，令vl(n)=ve(n），求 vl(i) 1<=i<=n-1。
（4） 根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s）和最晚开始时间l(s），其中e(s)=l(s）的为关键活动。
求关键路径是在拓扑排序的前提下进行的，不能进行拓扑排序，自然也不能求关键路径。

8.3 程序实现

template<class T> void PrintCriticalPath(ALGraph<T>& g)
{
	int i, j;
	T vex, start, end;
	int w;
	EdgeNode* edge;
	int* ve;
	int* vl;
	int* pArr = new int[g.GetNumVertices()];
	if (!TopologicalSort(g, pArr))
	{
		cout<<"Graph has a circle!"<<endl;
		delete [] pArr;
		return;
	}

	ve = new int[g.GetNumVertices()];
	vl = new int[g.GetNumVertices()];
	for (i = 0; i < g.GetNumVertices(); i++)
	{
		ve[i] = 0;
	}
	for (i = 0; i < g.GetNumVertices(); i++)
	{
		for (w = g.GetFirstAdjVex(pArr[i]); w != -1; w = g.GetNextAdjVex(pArr[i],w))
		{
			g.GetEdge(pArr[i], w, edge);
			ve[w] = max(ve[w], ve[pArr[i]] + edge->weight);
		}
	}

	for (i = 0; i < g.GetNumVertices(); i++)
	{
		vl[i] = ve[g.GetNumVertices()-1];
	}

	for (i = g.GetNumVertices() - 1; i >= 0; i--)
	{
		for (w = g.GetFirstAdjVex(pArr[i]); w != -1; w = g.GetNextAdjVex(pArr[i], w))
		{
			g.GetEdge(pArr[i], w, edge);
			vl[pArr[i]] = min(vl[pArr[i]], vl[w] - edge->weight);
		}
	}
	cout<<"| 起点 | 终点 | 最早开始时间 | 最晚开始时间 | 差值 | 备注 |"<<endl;
	for (i = 0, j = 0; i < g.GetNumVertices(); i++)
	{
		for (w = g.GetFirstAdjVex(i); w != -1; w = g.GetNumVertices(i,w), j++)
		{
			g.GetEdge(i,w,edge);
			g.GetVertex(i,start);
			g.GetVertex(w,end);

			cout<<setiosflags(ios::right)
				<<setw(6)<<start
				<<setw(9)<<end
				<<setw(14)<<ve[i]
			<<setw(19)<<vl[i]
			<<setw(14)<<edge->weight
				<<setw(12)<<(ve[i] == vl[w] - edge->weight ? "关键路径":"")<<endl;
		}
	}
	delete [] ve;
	delete [] vl;
	delete [] pArr;
}
上述程序时间复杂度为O(n+1)。

9 最短路径

9.1 单元最短路径

为了求得最短路径，荷兰籍计算机科学家Dijkstra提出一个按路径长度递增次序产生最短路径的方法，称之为Dijkstra（迪杰斯特拉算法）单源最短路径算法。

在具体实现Dijkstra算法时，可设计一个结构体TableEntry:

struct TableEntry
{
	bool known;
	int dist;
	int preVertex;
};
Dijkstra算法的具体描述：
（1）设table为TableEntry类型数组。初始时，设每个顶点的table[i].known = false，table[i].dist = INT_MAX，table[i].preVertex = -1，源点的table[start].dist = 0.
（2）选取一个离源点距离最小的顶点v，将该顶点known标识为true，若v无邻接点（该选定的距离就是源点到v的最短路径长度，中间不经过其他顶点），则退出本次循环。（3）若v有邻接点w，且顶点w的known标识为false时，如果table[v].dist + edge->weight < table[w].dist（edge为弧<v,w>），则table[w].dist = table[v].dist + edge->weight，w的前驱preVertex设为v，然后依次修改v的所有邻接点的对应的值。
重复步骤（2）和（3），直到所有顶点known标识为true。
程序实现：
//返回table中known为false且dist最小的元素的位置，n是table的数组程度
int SmallestUnknownDistIndex(TableEntry table[], int n)
{
	int min = INT_MAX;
	int i;
	int index = -1;
	for (i = 0; i < n; i++)
	{
		if (table[i].known)
		{
			continue;
		}
		if (table[i].dist < min)
		{
			min = table[i].dist;
			index = i;
		}
	}

	return index;
}

//用Dijkstra算法求有向图g的顶点vex到其余各顶点的最短路径。
template<class T> TableEntry* ShortestPath_DIJ(ALGraph<T>& g, T vex)
{
	int i, v, w;
	int start = g.LocateVertex(vex);
	EdgeNode* edge;
	TableEntry* table = new TableEntry[g.GetNumVertices()];

	//init table
	for (i = 0; i < g.GetNumVertices(); i++)
	{
		table[i].known = false;
		table[i].dist = INT_MAX;
		table[i].preVertex = -1;
	}
	table[start].dist = 0;

	while(true)
	{
		v = SmallestUnknownDistIndex(table,g.GetNumVertices());
		if (v == -1)
		{
			break;
		}
		table[v].known = true;

		for (w = g.GetFirstAdjVex(v); w != -1; w = g.GetNumVertices(v,w))
		{
			if (!table[w].known)
			{
				g.GetEdge(v,w,edge);
				if (table[v].dist + edge->weight < table[w].dist)
				{
					table[w].dist = table[v].dist + edge->weight;
					table[w].preVertex = v;
				}
			}
		}
	}

	return true;
}
上述程序时间复杂度为O(n^2)。

9.2 每对顶点间的最短路径

常用的有Floyd算法，基本思想如下：
从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点X到B。所以，我们假设Dis(AB)为节点A到节点B的最短路径的距离，对于每一个节点X，我们检查Dis(AX) + Dis(XB) < Dis(AB)是否成立，如果成立，证明从A到X再到B的路径比A直接到B的路径短，我们便设置Dis(AB) = Dis(AX) + Dis(XB)，这样一来，当我们遍历完所有节点X，Dis(AB)中记录的便是A到B的最短路径的距离。

转载：http://blog.csdn.net/foreverling/article/details/43340677
上一篇：Spring Boot 2.X(十八)：集成 Spring Security-登录认证和权限控制


下一篇：电商小程序开发的关键在哪里？