【数据结构】拓扑网络（AOE算法举例+源码）

这篇具有很好参考价值的文章主要介绍了【数据结构】拓扑网络（AOE算法举例+源码）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

博主介绍：✌专研于前后端领域优质创作者、本质互联网精神开源贡献答疑解惑、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战，深受全网粉丝喜爱与支持✌有需要可以联系作者我哦！

🍅文末获取源码联系🍅

👇🏻 精彩专栏推荐订阅👇🏻 不然下次找不到哟

一、拓扑网络定义

拓扑网络是计算机网络中的一个重要概念，指的是连接在一起的网络设备之间的物理或逻辑结构。拓扑结构决定了网络中各个节点之间的连接方式，对网络的性能、可靠性和扩展性都有重要影响。

1. 什么是拓扑网络？

拓扑网络描述了计算机网络中设备之间的连接方式，包括它们之间的物理布局或逻辑结构。这种结构定义了网络中数据流动的路径，以及各个节点之间的关系。拓扑网络的选择直接影响了网络的性能、可靠性和维护难度。

2. 常见的拓扑结构

网络拓扑算法,数据结构,网络,算法

2.1 星型拓扑

星型拓扑所有设备都连接到一个中心节点（如交换机或集线器）。这种结构简单易于维护，但如果中心节点故障，整个网络可能受到影响。

2.2 总线拓扑

总线拓扑中，所有设备都连接到一根共享的传输介质，如一根电缆。数据通过总线传输，但当设备数量增加时，总线可能成为瓶颈。

2.3 环形拓扑

环形拓扑中，设备通过连接成一个环形。数据沿着环路传输，但如果某个设备出现故障，可能会导致整个网络中断。

2.4 网状拓扑

网状拓扑中，每个设备都连接到网络中的其他设备，形成多条路径。这种结构具有高度的冗余和可靠性，但是布线复杂，成本较高。

2.5 混合拓扑

混合拓扑是以上拓扑的组合形式，可以根据网络的需求和规模选择不同的结构。

二、拓扑网络的应用

拓扑网络广泛应用于各种领域，包括企业网络、数据中心、云计算等。在实际应用中，需要根据具体情况权衡各种因素，选择最合适的拓扑结构来构建网络。

三、AOE算法

AOE（Activity On Edge）算法是一种用于求解工程网络中最早开始时间和最晚开始时间的算法。工程网络是一种用图表示的项目计划，其中节点表示活动，有向边表示活动之间的依赖关系。AOE算法通常用于项目管理，帮助确定项目中各个活动的最早和最晚开始时间，以及关键路径。

以下是AOE算法的主要步骤：

绘制工程网络图： 根据项目计划，绘制工程网络图，其中节点表示活动，有向边表示活动之间的依赖关系。

确定活动持续时间： 为每个活动确定其持续时间，并将这些信息标记在相应的节点上。

确定事件的最早开始时间（ES）： 从网络的起始节点开始，按照拓扑排序的顺序，计算每个事件（节点）的最早开始时间。对于每个活动，最早开始时间等于其所有前驱活动的最早完成时间的最大值。

确定活动的最早开始时间和最早完成时间（EF）： 根据最早开始时间，计算每个活动的最早开始时间和最早完成时间。最早完成时间等于最早开始时间加上活动持续时间。

确定事件的最晚完成时间（LF）： 从网络的终点节点开始，按照逆拓扑排序的顺序，计算每个事件的最晚完成时间。对于每个活动，最晚完成时间等于其所有后继活动的最晚开始时间的最小值。

确定活动的最晚开始时间和最晚完成时间（LS）： 根据最晚完成时间，计算每个活动的最晚开始时间和最晚完成时间。最晚开始时间等于最晚完成时间减去活动持续时间。

计算活动的浮动时间： 活动的浮动时间是指活动可以推迟的时间，而不影响整个项目的完成时间。浮动时间等于最晚开始时间减去最早开始时间。

找到关键路径： 关键路径是指总浮动时间为零的路径，即对整个项目的完成时间有最大影响的路径。关键路径上的活动是项目的关键活动。

#include<iostream>
#include<string.h> 
using namespace std;
 
#define pointMax 100
 
struct VtNode                 //权值信息
{
	VtNode *nextVt;           //入度链表下一个结点
	int peace;                //入度下一顶点的值
 
	VtNode *nextVtt;          //出度链表下一个结点
	int peaceE;               //出度下一顶点的值
 
	int len;
};
struct PoNode                  //顶点信息
{
	char data;
	VtNode *firstPo;          //入度
	VtNode *Out;              //出度
};
 
struct ATgroup
{
	PoNode vertices[pointMax];     //每一个verticse代表一个顶点
	int point, vert;               //point顶点数，vert弧数
};
 
struct Node
{
	int data;
	Node *next;
};
 
struct SqStack          //栈
{
	Node *base;          //栈底
	Node *top;           //栈顶
	int data;
};
 
void Push(SqStack &S, int i)       //入栈
{
	Node *m = new Node;
	m->data = i;
	m->next = S.top;             //入栈过程
	S.top = m;
}
 
int Pop(SqStack &S)              //出栈
{
	int n = S.top->data;
	S.top = S.top->next;         //出栈过程
	return n;
}
 
 
int ATlocate(ATgroup A, char x)             //找到位置
{
	for (int i = 0; i < A.point; i++)       //依次遍历点的信息
	{
		if (A.vertices[i].data == x)        //找到x的位置
		{
			return i;
		}
	}
}
 
void show(ATgroup &A)                      //显示当前所有点入度出度的顶点
{
	//cout << endl;
	for (int i = 0; i < A.point; i++)
	{
		//cout << i;
		if (A.vertices[i].firstPo != NULL)          //入度位置
		{
		//	cout << "    " << A.vertices[i].firstPo->peace << "   ";
		}
		//else
		//	cout << "    -1" << "    ";
 
		if (A.vertices[i].Out != NULL)             //出度位置
		{
		//	cout << A.vertices[i].Out->peaceE << endl;
		}
		//else
		//	cout << "    -1" << endl;
	}
}
 
void CreatAT(ATgroup &A)
{
	cout << "输入邻接矩阵顶点数：";
	cin >> A.point;
	cout << "输入邻接矩阵边数：";
	cin >> A.vert;
	getchar();
	char q[100];
	cout << "输入顶点信息：";
	gets(q);
//	这里作了一个修改 
	for (int i = 0; i < A.point; i++)
	{
		A.vertices[i].data = q[i];               //输入顶点值
		A.vertices[i].firstPo = NULL;            //初始化头结点为空
		A.vertices[i].Out = NULL;
	}
	char v1, v2; int m, n; int len;
	for (int i = 0; i < A.vert; i++)            //输入各边，构造邻接表
	{
		cout << "输入第" << i << "条边的依附的两个顶点：";
		int Q;
		cin >> v1 >> v2 >> Q;
		m = ATlocate(A, v1);                  //确定位置
		n = ATlocate(A, v2);
		//第一个
		VtNode *p1 = new VtNode;
		VtNode *p2 = new VtNode;
		p1->peace = m;                             //入度
		p1->nextVt = A.vertices[n].firstPo;
		A.vertices[n].firstPo = p1;
 
		p2->peaceE = n;                            //出度
		p2->nextVtt = A.vertices[m].Out;
		p2->len = Q;
		A.vertices[m].Out = p2;
	}
	//show(A);
}
 
void FindIn(ATgroup *A, int *in)           //统计所有点的入度数并存入到in数组中
{
	int n = 0;
	for (int i = 0; i < A->point; i++)     //遍历每一个点
	{
		VtNode *p = new VtNode;
		p = A->vertices[i].firstPo;
		while (p != NULL)                  //将入度链表进行遍历
		{
			n++;
			p = p->nextVt;          //下一结点
		}
		in[i] = n;          //存入in数组
		n = 0;
	}
}
 
void SHOW(int *a, ATgroup *A)           //显示当前所有顶点入度数量还有几个
{
	for (int i = 0; i < A->point; i++)
	{
		//cout << a[i] << "  ";
	}
	//cout << endl;
}
 
int M[pointMax] = { 0 };
int topo[pointMax];           //拓扑遍历存入
 
void TPsort(ATgroup *A, SqStack &S)           //拓扑排序过程
{
	int Indegree[pointMax];
	FindIn(A, Indegree);             //将入度赋值给数组
 
	for (int i = 0; i < A->point; i++)
	{
		if (Indegree[i] == 0)         //将所有入度等于0的入栈
		{
			//cout << "Push=" << i << endl;
			Push(S, i);
		}
	}
 
	int m = 0;                //统计入度的顶点数
	int n, k;
 
	while (S.base != S.top)       //判断是否遍历完
	{
		//cout << endl;
		n = Pop(S);         //栈顶出栈
		//cout << "Pop=" << n << endl;
		topo[m] = n;        //存入topo
		m++;
		VtNode* p = new VtNode;
		p = A->vertices[n].Out;             //出度链表的结点
		while (p != NULL)            //遍历出度链表
		{
			k = p->peaceE;          //某结点的位置
			//cout << "出度下一结点k=" << k << endl;
			Indegree[k]--;          //将该结点顶点位置入度减一
			//SHOW(Indegree, A);       //显示当前所有点的入度
			if (Indegree[k] == 0)      //当等于0时，入栈
			{
				//cout << "Push=" << k << endl;
				Push(S, k);
			}
			p = p->nextVtt;     //下一个
		}
	}
}
 
 
 
int ve[pointMax];      //最早发生时间
int vl[pointMax];      //最晚发生时间
 
void CritPath(ATgroup *A)
{
	int n = A->point;          //n为顶点个数
	for (int i = 0; i < n; i++)        //将每个事件的最早事件为0
		ve[i] = 0;
 
	//---按拓扑次序求每个事件的最早发生时间---//
	int k, j;
	for (int i = 0; i < n; i++)
	{
		k = topo[i];                 //取的拓扑排序中的顶点序号
		cout <<"K=F"<< k << "  "<<endl;
		VtNode *p = A->vertices[k].Out;     //指向K的第一个邻接结点
		while (p != NULL)
		{
			j = p->peaceE;
			if (ve[j] < ve[k] + p->len)
			{
				ve[j] = ve[k] + p->len;
				cout << ve[j] << "  " << ve[k] << "   " << p->len << endl;
			}
			p = p->nextVtt;
		}
		cout << ve[j] << endl;
	}
	for (int i = 0; i < A->point; i++)
	{
		cout << ve[i] << "   ";
	}
	cout << endl;
	cout << endl;
 
	for (int i = 0; i < n; i++)       //初始化
	{
		vl[i] = ve[topo[n - 1]];
	}
	//---按逆拓扑排序求每个事件的最迟发生时间----//
	for (int i = n - 1; i >= 0; i--)
	{
		k = topo[i];                 //取的拓扑排序中的顶点序号
		VtNode *p = A->vertices[k].Out;     //指向K的第一个邻接结点
		//cout << k << endl;
		while (p != NULL)
		{
			j = p->peaceE;
			if (vl[k] > vl[j] - p->len)
			{
				vl[k] = vl[j] - p->len;
				//cout << vl[k] << "  " << vl[j] << "   " << p->len << endl;
			}
			p = p->nextVtt;
		}
		//cout << vl[j] << endl;
	}
 
	for (int i = 0; i < A->point; i++)
	{
		cout << vl[i] << "   ";
	}
	cout << endl;
	cout << endl;
 
	//----判断每一活动是否为关键活动-----//
	int e, l;
	for (int i = 0; i < n; i++)
	{
		VtNode *p = A->vertices[i].Out;
		while (p != NULL)
		{
			j = p->peaceE;
			e = ve[i];
			l = vl[j] - p->len;
			if (e == l)
			{
				cout << A->vertices[i].data << "   " << A->vertices[j].data << endl;
			}
			p = p->nextVtt;
		}
	}
}
 
int main()
{
	ATgroup *A = new ATgroup;
	SqStack *S = new SqStack;
	S->top = S->base;
	S->data = pointMax;
	CreatAT(*A);
	TPsort(A, *S);
	CritPath(A);
	system("pause");
}

文章来源地址https://www.toymoban.com/news/detail-834595.html

到了这里，关于【数据结构】拓扑网络（AOE算法举例+源码）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！