苗火 Nicholas

[Data structures]Critical path (Active on edge)

2019-7-26 萧 写技术

#include <stdio.h>
#include <stdlib.h>

#define MAX 20
#define INFINIT	65535

typedef struct _ArcCell{
	int adj; // Weight or flag about connection
	int *info; // Other information
}ArcCell;

typedef char VertexType;

typedef enum{
	DG,
	DN,
	UDG,
	UDN
}GraphKind;

typedef struct _MGraph{
	VertexType vexs[MAX];
	ArcCell arcs[MAX][MAX];
	int vexnum;
	int arcnum;
	GraphKind kind;
}MGraph;

int visited[MAX];
int ve[MAX];
int vl[MAX];
int e[MAX];
int l[MAX];

int LocateVex(MGraph *G, VertexType v)
{
	int i=0;
	while(i<G->vexnum && G->vexs[i] != v){
		i++;
	}
	if(i<G->vexnum){
		return i;
	}else{
		return -1;
	}
}

int CreateUDN(MGraph *G)
{
	int i,j,k;
	char v1,v2;
	int cost;

	scanf(" %d %d", &G->vexnum, &G->arcnum);	
	for(i=0; i<G->vexnum; i++){
		scanf(" %c", &G->vexs[i] );
	}
	for(i=0; i<G->vexnum; i++){
		for(j=0; j<G->vexnum; j++){
			G->arcs[i][j].adj = INFINIT;
		}
	}
	for(k=0; k<G->arcnum; k++){
		scanf(" %c %c %d", &v1, &v2, &cost);
		i=LocateVex(G, v1);
		j=LocateVex(G, v2);	
		G->arcs[i][j].adj = cost;
	}
	return 1;
}

int FirstAdjvex(MGraph *G, int v)
{
	int i=0;
	while(i<G->vexnum && G->arcs[v][i].adj == INFINIT){
		i++;
	}	
	if(i<G->vexnum){
		return i;
	}else{
		return -1;
	}
}

int NextAdjvex(MGraph *G, int v, int w)
{
	int i=w+1;
	while(i<G->vexnum && G->arcs[v][i].adj == INFINIT){
		i++;
	}
	if(i<G->vexnum){
		return i;
	}else{
		return -1;
	}

}

void FindInDegree(MGraph *G, int *indegree)
{
	int i;
	int j;
	for(i=0; i<G->vexnum; i++){
		indegree[i]=0;
		for(j=0; j<G->vexnum; j++){
			if(G->arcs[j][i].adj != INFINIT){
				indegree[i]++;
			}
		}	
	}	
}

int TopologicalSort(MGraph *G, int *stackT, int *topT)
{
	int indegree[MAX];
	int stack[MAX];
	int top = -1;
	int w;
	int i;
	int count;

	FindInDegree(G, indegree);
	for(i=0; i<G->vexnum; i++){
		if(!indegree[i]){
			stack[++top] = i;
		}
		ve[i] = 0;
	}
	
	count = 0;

	while(top>=0){
		w = stack[top--];
		stackT[++(*topT)] = w;
		//printf(" %c->", G->vexs[w]);
		++count;
		
		for(i=0; i<G->vexnum; i++){
			if(G->arcs[w][i].adj != INFINIT){
				indegree[i]--;
				if(indegree[i] == 0){
					stack[++top] = i;
				}

				if(ve[w] + G->arcs[w][i].adj > ve[i]){
					ve[i] = ve[w] + G->arcs[w][i].adj;
				}
			}		
		}
	}
	if(count < G->vexnum){
		return 0;
	}else{
		return 1;
	}

}

int CriticalPath(MGraph *G)
{
	int i;
	int j;
	int stackT[MAX];
	int topT = -1;
	int tag;
	int ee, el;

	if(!TopologicalSort(G, stackT, &topT) ){
		return 0;
	}

	for(i=0; i<G->vexnum; i++){
		vl[i] = ve[G->vexnum-1];
	}

	while(topT>=0){
		j = stackT[topT--];

		for(i=0; i<G->vexnum; i++){
			if(G->arcs[i][j].adj != INFINIT){
				if( vl[j] - G->arcs[i][j].adj < vl[i] ){
					vl[i] = vl[j] - G->arcs[i][j].adj;
				}
			}
		}

	}

	for(j=0; j<G->vexnum; j++){
		for(i=0; i<G->vexnum; i++){
			if(G->arcs[j][i].adj != INFINIT){
				ee = ve[j];
				el = vl[i] - G->arcs[j][i].adj;
				tag = (ee == el)? '*':' ';
				printf("%c->%c len=%d ee=%d el=%d %c\n",
					G->vexs[j], G->vexs[i], 
					G->arcs[j][i].adj, ee, el, tag);
			}
		}
	}

}

void main()
{
	MGraph G;	

	printf("log.anycle.com\n\n");
	printf("Create graph:\n");
	CreateUDN(&G);
	printf("\n");

	printf("Find critical path:\n");
	CriticalPath(&G);
	printf("\n");

}

标签: Data Structures data_structures