程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 圖的拓撲排序、關鍵路徑、最短路徑算法

圖的拓撲排序、關鍵路徑、最短路徑算法

編輯：關於C++

一：拓撲排序

對一個有向無環圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u,v)∈E(G)，則u在線性序列中出現在v之前。通常，這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列，簡稱拓撲序列。

拓撲排序就是要找到入度為0的頂點，並依次壓棧。首先將棧頂頂點輸出，刪除以此頂點為弧尾的頂點，並更新其他頂點的入度。若入度為0，則繼續壓棧。更新完畢繼續出棧，直至棧空。元素出棧並輸出的順序即為拓撲排序結果。我們代碼中會利用數組模擬一個棧空間。如圖所示：

該圖所得到拓撲排序結果為：F A D C E B。算法如下：

template 
void graph_mtx::topological_sort()
{
	int num = this->get_numvertices();
	assert(num != -1);

	int *count = new int[num];
	assert(count != nullptr);

	for(int i=0; i

二：關鍵路徑

關鍵路徑：從源點到匯點的路徑長度最長的路徑叫關鍵路徑。圖中a(1..n)表示兩活動之間花費的時間。如圖所示：

圖中所求關鍵路徑為A B E G I 或 A B E H I。兩個重要概念： 1.最早開始時間如圖E，從A到E所花費的時間在兩條路徑上飛別為7和5，那麼E活動什麼時候開始呢？毫無疑問，由於E活動開始存在B、C時間兩個前提，所以在工程起始時間一定的情況下，A到E最少需要花費時間取決於ABE這條較長分支，這條分支如果未完成，那麼C就算完成了也只能等待另一分支完成，此時E不能開始。由此可見，最早開始時間即為從源點到目標頂點最長的路徑花費的時間。 2.最晚開始時間同理，最晚開始時間是從匯點倒著往前計算的。與上面情況相同，最晚開始時間取決於從後往前經過的路徑長度最長的分支。由圖易知，最早開始時間和最晚開始時間相等的頂點，即為關鍵路徑頂點。算法如下：

template 
void graph_mtx::critical_path(const T& vert)
{
	int num = this->get_numvertices();
	
	int *early_start = new int[num];   //最早開始時間數組
	int *late_start = new int[num];    //最晚開始時間數組
	assert(early_start != nullptr && late_start != nullptr);

	int index = get_vertex_index(vert);
	assert(index != -1);

	for(int i=0; i early_start[neighbor_index]) //如果某點最早開始時間加上某點到其鄰接點的權值大於該鄰接點之前的權值，說明新路徑長，更新該鄰接點權值
				early_start[neighbor_index] = early_start[i]+weight;

			neighbor_index = get_nextneighbor(get_vertex_symbol(i),
										      get_vertex_symbol(neighbor_index));
		}
	}

	for(int i=0; i=0; --i){    //除開匯點，從num-2開始
		int neighbor_index = get_firstneighbor(get_vertex_symbol(i));
		while(neighbor_index != -1){
			int weight = edge[i][neighbor_index];  
			if(late_start[neighbor_index]-weight < late_start[i])//某點的鄰接點的最晚開始時間減去權值小於某點之前的最晚開始時間，說明現有從後往前的路徑長，則更新為最晚開始時間
				late_start[i] = late_start[neighbor_index]-weight;

			neighbor_index = get_nextneighbor(get_vertex_symbol(i),
				                              get_vertex_symbol(neighbor_index));
		}
	}

	for(int i=0; i

三：最短路徑（迪傑斯特拉算法）

最短路徑問題是圖論研究中的一個經典算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。迪傑斯特拉算法用一個dist[]數組存儲到達某點的花費，以其下標對應，並用一個path[]數組來存儲到達該點前經過的某個頂點的下標。其中lable_incorporated[]數組用來標記已並入路徑的頂點。如圖所示：

該圖的最短路徑為A D C E。代碼如下：

template 
void graph_mtx::shortest_path(const T& vert)
{
	int num = this->get_numvertices();
	
	int *dist = new int[num];
	int *path = new int[num];
	int *lable_incorporated = new int[num];
	assert(dist != nullptr && path != nullptr 
						   && lable_incorporated != nullptr);

	int index = get_vertex_index(vert);
	assert(index != -1);

	for(int i=0; i

四：全部代碼及測試

通用圖頭文件：

#ifndef _GRAPH_H
#define _GRAPH_H

#include 
#include 
#include 
#include 
#include 
using namespace::std;

#define MAX_COST 0x7FFFFFFF

///////////////////////////////////////////////////////////////////////////////////////////
//通用圖結構
template 
class graph{
public:
	bool is_empty()const;
	bool is_full()const;
	
	int get_numvertices()const;    //當前頂點數
	int get_numedges()const;       //當前邊數
public:
	virtual bool insert_vertex(const T&) = 0;            //插入頂點
	virtual bool insert_edge(const T&, const T&, E) = 0;    //插入邊

	virtual int get_firstneighbor(const T&)const = 0;    //得到第一個鄰接頂點
	virtual int get_nextneighbor(const T&, const T&)const = 0;    //某鄰接頂點的下一個鄰接頂點
	
	virtual void print_graph()const = 0;
	virtual int get_vertex_index(const T&)const = 0;     //得到頂點序號
protected:
	static const int VERTICES_DEFAULT_SIZE = 10;         //默認圖頂點數
	int max_vertices;
	int num_vertices;
	int num_edges;
};

template 
bool graph::is_empty()const
{
	return num_edges == 0;
}

template 
bool graph::is_full()const
{
	return num_vertices >= max_vertices 
		   || num_edges >= max_vertices*(max_vertices-1)/2;    //判滿，分為頂點滿和邊滿
}

template 
int graph::get_numvertices()const
{
	return num_vertices;
}

template 
int graph::get_numedges()const
{
	return num_edges;
}

///////////////////////////////////////////////////////////////////////////////////////////

#define VERTICES_DEFAULT_SIZE graph::VERTICES_DEFAULT_SIZE
#define num_vertices          graph::num_vertices   
#define num_edges             graph::num_edges
#define max_vertices          graph::max_vertices         

///////////////////////////////////////////////////////////////////////////////////////////

#endif /*graph.h*/

實現文件：

#pragma once

#include "graph.h"

//圖的鄰接矩陣表示法
template 
class graph_mtx : public graph{
public:
	graph_mtx(int);                   
	~graph_mtx();                             
public:
	bool insert_vertex(const T&);
	bool insert_edge(const T&, const T&, E);  

	int get_firstneighbor(const T&)const;
	int get_nextneighbor(const T&, const T&)const;
	
	int get_vertex_index(const T&)const;
	T& get_vertex_symbol(const int)const;
	void print_graph()const;

	void topological_sort();
	void shortest_path(const T&);
	void critical_path(const T&);
private:
	T* vertices_list;                        //頂點線性表
	E **edge;                              //內部矩陣
};

template 
graph_mtx::graph_mtx(int sz = VERTICES_DEFAULT_SIZE)
{
	max_vertices = sz > VERTICES_DEFAULT_SIZE ? sz 
									: VERTICES_DEFAULT_SIZE;
	vertices_list = new T[max_vertices];

	edge = new int*[max_vertices];                    //動態申請二維數組
	for(int i=0; i
graph_mtx::~graph_mtx()
{
	for(int i=0; i
bool graph_mtx::insert_vertex(const T& vert)
{
	if(this->is_full())                       //派生類函數調用父類函數，用this或加作用域
		return false;
	vertices_list[num_vertices++] = vert;
	return true;
}

template 
bool graph_mtx::insert_edge(const T& vert1, const T& vert2, E cost = MAX_COST)
{
	if(this->is_full())                       //判滿
		return false;

	int index_v1 = get_vertex_index(vert1);   //得到頂點序號
	int index_v2 = get_vertex_index(vert2);

	if(index_v1 == -1 || index_v2 == -1 )
		return false;
	
	edge[index_v1][index_v2] = cost;    //無向圖
	++num_edges;	
	
	return true;
}

template 
int graph_mtx::get_firstneighbor(const T& vert)const
{
	int index = get_vertex_index(vert);

	if(index != -1){
		for(int i=0; i
int graph_mtx::get_nextneighbor(const T& vert1, const T& vert2)const
{
	int index_v1 = get_vertex_index(vert1);
	int index_v2 = get_vertex_index(vert2);

	if(index_v1 != -1 && index_v2 != -1){
		for(int i=index_v2+1; i
int graph_mtx::get_vertex_index(const T& vert)const
{
	for(int i=0; i
T& graph_mtx::get_vertex_symbol(const int index)const
{
	assert(index >= 0 && index < this->get_numvertices());
	return vertices_list[index];
}

template 
void graph_mtx::print_graph()const
{
	if(this->is_empty()){
		cout << "nil graph" << endl;                      //空圖輸出nil
		return;
	}
	
	for(int i=0; i
void graph_mtx::topological_sort()
{
	int num = this->get_numvertices();
	assert(num != -1);

	int *count = new int[num];
	assert(count != nullptr);

	for(int i=0; i
void graph_mtx::shortest_path(const T& vert)
{
	int num = this->get_numvertices();
	
	int *dist = new int[num];
	int *path = new int[num];
	int *lable_incorporated = new int[num];
	assert(dist != nullptr && path != nullptr 
						   && lable_incorporated != nullptr);

	int index = get_vertex_index(vert);
	assert(index != -1);

	for(int i=0; i
void graph_mtx::critical_path(const T& vert)
{
	int num = this->get_numvertices();
	
	int *early_start = new int[num];
	int *late_start = new int[num];
	assert(early_start != nullptr && late_start != nullptr);

	int index = get_vertex_index(vert);
	assert(index != -1);

	for(int i=0; i early_start[neighbor_index])
				early_start[neighbor_index] = early_start[i]+weight;

			neighbor_index = get_nextneighbor(get_vertex_symbol(i),
										      get_vertex_symbol(neighbor_index));
		}
	}

	for(int i=0; i=0; --i){
		int neighbor_index = get_firstneighbor(get_vertex_symbol(i));
		while(neighbor_index != -1){
			int weight = edge[i][neighbor_index];
			if(late_start[neighbor_index]-weight < late_start[i])
				late_start[i] = late_start[neighbor_index]-weight;

			neighbor_index = get_nextneighbor(get_vertex_symbol(i),
				                              get_vertex_symbol(neighbor_index));
		}
	}

	for(int i=0; i測試文件：#include "graph.h"
#include "graph_mtx.h"

int main()
{
	graph_mtx gm;

//critical_path
	gm.insert_vertex('A');	
	gm.insert_vertex('B');	
	gm.insert_vertex('C');	
	gm.insert_vertex('D');	
	gm.insert_vertex('E');	
	gm.insert_vertex('F');	
	gm.insert_vertex('G');	
	gm.insert_vertex('H');	
	gm.insert_vertex('I');

	gm.insert_edge('A', 'B', 6);
	gm.insert_edge('A', 'C', 4);
	gm.insert_edge('A', 'D', 5);
	gm.insert_edge('B', 'E', 1);
	gm.insert_edge('C', 'E', 1);
	gm.insert_edge('D', 'F', 2);
	gm.insert_edge('E', 'G', 9);
	gm.insert_edge('E', 'H', 7);
	gm.insert_edge('G', 'I', 2);
	gm.insert_edge('H', 'I', 5);
	gm.insert_edge('F', 'H', 4);

	gm.critical_path('A');
	cout << endl;
#if 0
//shortest_path
	gm.insert_vertex('A');
	gm.insert_vertex('B');
	gm.insert_vertex('C');
	gm.insert_vertex('D');
	gm.insert_vertex('E');

	gm.insert_edge('A', 'B', 10);
	gm.insert_edge('A', 'D', 30);
	gm.insert_edge('A', 'E', 100);
	gm.insert_edge('B', 'C', 50);
	gm.insert_edge('C', 'E', 10);
	gm.insert_edge('D', 'C', 20);
	gm.insert_edge('D', 'E', 60);

	cout << "shortest_path:" << endl;
	gm.shortest_path('A');
	cout << endl;
#endif
#if 0
//topological_sort
	gm.insert_vertex('A');
	gm.insert_vertex('B');
	gm.insert_vertex('C');
	gm.insert_vertex('D');
	gm.insert_vertex('E');
	gm.insert_vertex('F');
	
	gm.insert_edge('A', 'B', 6);
	gm.insert_edge('A', 'C', 1);
	gm.insert_edge('A', 'D', 5);
	gm.insert_edge('C', 'B', 5);
	gm.insert_edge('C', 'E', 3);
	gm.insert_edge('D', 'E', 5);
	gm.insert_edge('F', 'E', 4);
	gm.insert_edge('F', 'D', 2);
	
	cout << "topological_sort:" << endl;
	gm.topological_sort();
	cout << endl;

#endif

	return 0;
}


部分測試結果：