16关键路径算法

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define MVNum 100
typedef int Status;
typedef char VerTexType;
typedef char OtherInfo;

//创建栈 
typedef struct StackNode {
	int data;
	struct StackNode* next;
}StackNode, * StackList;
//出栈函数 
StackList Pop(StackList S, int* e)
{
	StackList p;
	p = S;
	if (!p)
		return ERROR;
	*e = p->data;
	S = S->next;
	free(p);
	return S;
}
//入栈函数： 
StackList Push(StackList S, int e)
{
	StackList p;
	p = (StackNode*)malloc(sizeof(StackNode));
	p->data = e;
	p->next = S;
	S = p;
	return S;
}

//边结点 
typedef struct ArcNode {    //链表结点
	int adjvex;           //邻接表创建无向网的实现
	struct ArcNode* nextarc;    //指向下一条边的指针
	OtherInfo info;       //和边相关的信息
}ArcNode;

//顶点信息 
typedef struct VNode {   //头结点
	VerTexType data;   //顶点信息
	ArcNode* firstarc;//指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum];//AdjList 表示邻接表类型

typedef struct {
	AdjList vertices;     //邻接表头结点数组
	int vexnum, arcnum;   //图的顶点数和弧数
}ALGraph;


int indegree[100] = { 0 };//结点入度的个数
//这里大家自行解决入度的问题 你可以创建图的时候直接创建相对应的数组

int TopoSort(ALGraph G, int* topo,int *etv)
{
	StackList S = NULL;
	ArcNode* p;
	//先检查所有入度为0的结点并且入栈
	for (int i = 0; i < G.vexnum; i++)
	{
		if (!indegree[i]) {
			S = Push(S, i);
		}
	}
	int m = 0;//记录拓扑序列的个数 
	for (int i = 0; i < G.vexnum; i++)
	{
		etv[i] = 0;
	}
	int index = 0;
	while (S)
	{
		S = Pop(S, &index);
		//紧接着跟一个进栈
		topo[m] = index;
		m++;
		while (p != NULL)
		{
			int k = p->adjvex;
			indegree[k]--;
			if (indegree[k] == 0)
			{
				S = Push(S, k);
			}
			//求事件的最早发生时间
			if (etv[index] + (p->info) > etv[k])
			{
				etv[k] = etv[index] + (p->info);
			}
			p = p->nextarc;
		}
	}
	topo[m] = -1;
	if (m < G.vexnum)
	{
		//有环
		return 0;
	}
	else
	{
		//输出拓扑序列
		return 1;
	}
}


void CriticalPath(ALGraph G, int* etv, int* ltv)
{
	int ete, lte;//活动的最早和最晚
	ArcNode* p;
	int topo[99] = { 0 };
	if (TopoSort(G,topo,etv))
	{
		for (int i = 0; i < G.vexnum; i++)
		{
			ltv[i] = etv[G.vexnum - 1];//初始化ltv
		}
	}
	int count = G.vexnum;
	while (count)
	{
		int gettopo = topo[--count];//将拓扑序列从后往前拿出来
		for (p = G.vertices[gettopo].firstarc; p ;p = p->nextarc)
		{
			int k = p->adjvex;
			if (ltv[k] - (p->info) < ltv[gettopo])
			{
				ltv[gettopo] = ltv[k] - (p->info);//求事件的最晚
			}
		}
	}
	//求活动的最早和最晚
	for (int i = 0; i < G.vexnum; i++)
	{
		for (p = G.vertices[i].firstarc; p; p = p->nextarc)
		{
			int k = p->adjvex;
			ete = etv[i];
			lte = ltv[k] - p->info;
			if (ete == lte)
			{
				//输出相对应的点和边 加入到最短路径当中
			}
		}
	}
}

int main() 
{
	int[n] a;
	int count = 0;//下标
}

void insert(int val)
{
	//摊还分析
	//每进行一次O(n)的操作 都会跟着N-1次的O(1)
	//O(1)
	if (count == a.length)
	{
		int sum = 0;
		for (int  i = 0; i < a.length; i++)
		{
			sum = sum + a[i];
		}
		a[0] = sum;
		count = 1;
	}
	a[count] = val;
	count++;
}

int find(int[] a, int n, int x)
{
	int pos;
	for (int i = 0; i < n; i++)
	{
		if (a[i] == x)
		{
			pos = i;
			break;
		}
	}
	return pos;
}