【データ構造】図の隣接表は、DFS、BFS、キーパスとトポロジ順序を表しています.

これは私が以前書いたコードです.参考書は「大話データ構造」です.隣接表を使って図を表します.同時に深さ優先検索と広さ優先検索を集めました.重要な経路とトポロジ並べ替えで、コードがちょっと長いです.windowsヘッダファイルは一時停止に使うだけのようです.

#include 
#include 
#include 
#define MAXVEX 100
#define ERROR 0
#define OK 1

//   DAT//
typedef int Elemtype; //BFS            
typedef int Status;
typedef struct QNode {
	Elemtype data;
	struct QNode *next;
}*QuenePrt;
typedef struct {
	QuenePrt front, rear;    //            
}*LinkQuene;

//      //
Status InitQuene(LinkQuene q) {
	q->front = q->rear = (QNode *)malloc(sizeof(QNode));   //      
	if (!q->front) {
		exit(ERROR);
	}
	q->front->next = NULL;
	return OK;
}

//      //
Status InsertQuene(LinkQuene q, Elemtype e) {
	// e         
	//          
	//   e         
	//    next     
	//           
	QuenePrt p;
	p = (QNode *)malloc(sizeof(QNode));//           
	p->data = e;
	p->next = NULL;
	q->rear->next = p;
	q->rear = p;
	return OK;
}

//    //
Status DeleteQuene(LinkQuene q, Elemtype *e) {
	//     
	//   ，     ，    
	//   ，      ，   front  rear
	//   ，    ，  ERROE
	QuenePrt p;
	if (q->front == q->rear)
		return ERROR;
	p = q->front->next;
	*e = p->data;
	q->front->next = p->next;
	if (q->rear == p)
		q->rear = q->front;//                  
	free(p);
	return OK;
}
//    //
Status QueneEmpty(LinkQuene Q) {
	//        1，    0
	if (Q->front == Q->rear)
		return true;
	else
		return false;
}

typedef int Vertextype;
typedef int Edgetype;

//    //
typedef struct EdgeNode {
	int adjvex;    //         
	Edgetype weight; //     
	struct EdgeNode *next;
}EdgeNode;

//     //
typedef struct VertexNode {
	int in;
	Vertextype data;  //      
	EdgeNode *firstedge;  //   
}VertexNode,AdjList[MAXVEX];

//     //
typedef struct {
	AdjList adjlist;  //     
	int Vex_num, Edge_num;//      
}AdjGraph;

//     ,   //
void CreateGraph(AdjGraph *G) {
	int i, j, k, weight,none;//none          
	EdgeNode *e;//        
	printf("         :");
	scanf_s("%d", &G->Vex_num);
	getchar();
	printf("         :");
	scanf_s("%d", &G->Edge_num);
	getchar();
	//     ,        
	for (i = 0; i < G->Vex_num; i++) {
		printf("    %d     :",i+1);
		scanf_s("%d", &G->adjlist[i].data);
		getchar();
		printf("    %d      ：",i+1);
		scanf_s("%d", &G->adjlist[i].in);
		getchar();
		G->adjlist[i].firstedge = NULL;
	}
	//    
	for (k =0 ; k < G->Edge_num; k++) {
		printf("    %d  （vi，vj）  vi    :", k + 1);
		scanf_s("%d", &i);
		getchar();
		printf("       （vi，vj）  vj    :");
		scanf_s("%d", &j);
		getchar();
		printf("         :");
		scanf_s("%d", &weight);
		getchar();
		printf("      ？（0    ，1   ）:");
		scanf_s("%d", &none);
		getchar();
		//      ,     
		e = (EdgeNode *)malloc(sizeof(EdgeNode));
		e->adjvex = j;
		e->next = G->adjlist[i].firstedge;
		G->adjlist[i].firstedge = e;
		e->weight = weight;
		e = (EdgeNode *)malloc(sizeof(EdgeNode));
		if (none == 0) {
			//              
			e->adjvex = i;
			e->next = G->adjlist[j].firstedge;
			G->adjlist[j].firstedge = e;
			e->weight = weight;
		}
	}
}

//     //
void printAdjGraph(AdjGraph *G) {
	printf("in   data   adjvex  weight
");
	EdgeNode *a = NULL;
	for (int i = 0; i < G->Vex_num; i++) {
		printf("%d", G->adjlist[i].in);
		printf("   V%d", G->adjlist[i].data);
		if (G->adjlist[i].firstedge != NULL) {
			//        
			printf(" -->  ");
			printf("   %d      %d", G->adjlist[i].firstedge->adjvex, G->adjlist[i].firstedge->weight);
			a = G->adjlist[i].firstedge;//a         
		}
		else {
			printf("  NULL");
		}
		if (a != NULL) {
			while (a->next != NULL) {
				a = a->next;//       
				printf("\t-->");
				printf("   %d	    %d", a->adjvex, a->weight);
			}
		}
		printf("
");
	}
}

//          //
boolean visited[MAXVEX];//      
void DFS(AdjGraph *G, int i) {
	EdgeNode *p;  //      
	visited[i] = true; //        
	printf("%c\t", G->adjlist[i].data);//    
	p = G->adjlist[i].firstedge;
	while (p != NULL) {
		if (visited[p->adjvex] == false) {
			//          
			DFS(G, p->adjvex);//    
		}
		p = p->next;
	}
}
//    
void AdjGraphTraverse(AdjGraph *G) {
	int i;
	for (i = 0; i < G->Vex_num; i++) {
		visited[i] = false;//          
	}
	for (i = 0; i < G->Vex_num; i++) {
		if (visited[i] == false) {
			DFS(G, i);//            
		}
	}
}

//          //
//        
void BFSTraverse(AdjGraph *G) {
	int i;
	EdgeNode *p = NULL;
	LinkQuene Q;//    
	Q = (LinkQuene)malloc(sizeof(LinkQuene));
	InitQuene(Q);//        
	for (i = 0; i < G->Vex_num; i++) {
		visited[i] = false;//       
	}
	//      
	for (i = 0; i < G->Vex_num; i++) {
		if (visited[i] == false) {
			//        
			visited[i] = true;
			printf("%c\t", G->adjlist[i].data);//       
			InsertQuene(Q, i);//       
			while (QueneEmpty(Q) != 1) {
				//         
				DeleteQuene(Q, &i);//      
				p = G->adjlist[i].firstedge;
				while (p != NULL) {
					if (visited[p->adjvex] == false) {
						//              
						visited[p->adjvex] = true;
						printf("%d\t", G->adjlist[p->adjvex].data);
						InsertQuene(Q, p->adjvex);//       
					}
					p = p->next;
				}
			}
		}
	}
}

//    //
void TopologicalSort(AdjGraph *G) {
	EdgeNode *e;
	int i, k, gettop;
	int top = 0;//    
	int count = 0;//   
	int *stack;
	stack = (int *)malloc(G->Vex_num * sizeof(int));//          
	for (i = 0; i < G->Vex_num; i++) {
		//    0      
		if (G->adjlist[i].in == 0) {
			stack[++top] = i;//  
		}
	}
	printf("        ：
");
	gettop = stack[top--];//      
	printf("%d", G->adjlist[gettop].data);
	count++;//    
	for (e = G->adjlist[gettop].firstedge; e; e = e->next) {
		//              
		k = e->adjvex;
		G->adjlist[k].in--;
		if (G->adjlist[k].in == 0) {
			//     0   
			stack[++top] = k;
		}
	}
	while (top != 0) {
		//     
		gettop = stack[top--];//      
		printf(" -> %d", G->adjlist[gettop].data);
		count++;//    
		for (e = G->adjlist[gettop].firstedge; e; e = e->next) {
			//              
			k = e->adjvex;
			G->adjlist[k].in--;
			if (G->adjlist[k].in == 0) {
				//     0   
				stack[++top] = k;
			}
		}
	}
	printf("
");
	if (count == G->Vex_num) {
		printf("     ，      
");
	}
	else {
		printf("      ，      
");
	}
}

//    //
int *etv, *ltv;//                   
int *stack2;//             
int top2;//stack2     

//        
void TopologiaclSortPro(AdjGraph *G) {
	EdgeNode *e;
	int i, k, gettop;
	int top = 0;
	int count = 0;
	int *stack1;//      
	stack1 = (int *)malloc(G->Vex_num * sizeof(int));
	for (i = 0; i < G->Vex_num; i++) {
		//   stack1  
		if(G->adjlist[i].in == 0)
		stack1[++top] = i;
	}
	top2 = 0;
	etv = (int *)malloc(G->Vex_num * sizeof(int));//        
	for (i = 0; i < G->Vex_num; i++) {
		etv[i] = 0;//           
	}
	stack2 = (int *)malloc(G->Vex_num * sizeof(int));
	printf("        ：
");
	gettop = stack1[top--];
	count++;
	stack2[++top2] = gettop;//      stack2，             
	printf(" %d", G->adjlist[gettop].data);
	for (e = G->adjlist[gettop].firstedge; e; e = e->next) {
		//             0       
		k = e->adjvex;
		G->adjlist[k].in--;
		if (G->adjlist[k].in == 0) {
			//  
			stack1[++top] = k;
		}
		if (etv[gettop] + e->weight > etv[k]) {
			//                ，              
			etv[k] = etv[gettop] + e->weight;
		}
	}
	while (top != 0) {
		// stack1     
		gettop = stack1[top--];
		count++;
		stack2[++top2] = gettop;//      stack2，             
		printf(" -> %d",G->adjlist[gettop].data);
		for (e = G->adjlist[gettop].firstedge; e; e = e->next) {
			//             0       
			k = e->adjvex;
			G->adjlist[k].in--;
			if (G->adjlist[k].in == 0) {
				//  
				stack1[++top] = k;
			}
			if (etv[gettop] + e->weight > etv[k]) {
				//                ，              
				etv[k] = etv[gettop] + e->weight;
			}
		}
	}
	if (count == G->Vex_num) {
		printf("
    ，    
");
	}
	else {
		printf("
    ，    
");
	}
	printf("         ：
");
	for (int i = 0; i < G->Vex_num; i++) {
		printf("V%d\t", i);
	}
	printf("
");
	for (int i = 0; i < G->Vex_num; i++) {
		printf("%d\t", etv[i]);
	}
	printf("
");
}

//    
void CriticalPath(AdjGraph *G) {
	EdgeNode *e;
	int i, gettop, k, j, count = 0;
	int ete, lte;//                 
	TopologiaclSortPro(G);//  ，  stack2  
	ltv = (int *)malloc(G->Vex_num * sizeof(int));//        
	for (i = 0; i < G->Vex_num; i++) {
		//             ltv
		ltv[i] = etv[G->Vex_num - 1];
	}
	printf("     ：
");
	while (top2 != 0) {
		//   stack2       
		gettop = stack2[top2--];
		for (e = G->adjlist[gettop].firstedge; e; e = e->next) {
			//                
			k = e->adjvex;
			if (ltv[k] - e->weight < ltv[gettop]) {
				//k         
				ltv[gettop] = ltv[k] - e->weight;
			}
		}
		//  ete lte       
		//         		
		for (j = 0; j < G->Vex_num; j++) {
			//       
			for (e = G->adjlist[j].firstedge; e; e = e->next) {
				k = e->adjvex;
				ete = etv[j];//                   
				lte = ltv[k] - e->weight;
				count++;
				//              
				if (ete == lte) {
					printf("V%d -> V%d  length：%d
", G->adjlist[j].data, G->adjlist[k].data, e->weight);
				}
			}
		}
	}
	printf("
");
	printf("         ：
");
	for (int i = 0; i < G->Vex_num; i++) {
		printf("V%d\t", i);
	}
	printf("
");
	for (int i = 0; i < G->Vex_num; i++) {
		printf("%d\t", ltv[i]);
	}
}

int main()
{
	AdjGraph *G;
	G = (AdjGraph *)malloc(sizeof(AdjGraph));
	CreateGraph(G);
	system("cls");
	printAdjGraph(G);
	//system("pause");
	//printf("            :
");
	//AdjGraphTraverse(G);
	//printf("
");
	//printf("            :
");
	//BFSTraverse(G);
	//TopologicalSort(G);
	CriticalPath(G);
    return 0;
}