带权有向图的邻接表表示、拓扑排序

#pragma once
#include <iostream>
#include "SqStack.h"
using namespace std;
#define MaxVertexNum 100
typedef char VertexType;
typedef struct ArcNode{ 
	int vertex;
	struct ArcNode* next;
	int info;
}ArcNode;
typedef struct VNode { 
	VertexType data;
	ArcNode* first;

}VNode,ArcList[MaxVertexNum];
typedef struct { 
	ArcList vertexes;
	int vertexNum, arcNum;
}ALGraph;
bool InitGraph(ALGraph* g) { 
	cout << "vertexNum、arcNum" << endl;
	cin >> g->vertexNum >> g->arcNum;
	for (int j = 0; j < g->vertexNum; j++) { 
		g->vertexes[j].data = '`';
		g->vertexes[j].first = NULL;
	}
	return true;
}
int GetVertexIndex(ALGraph* g, VertexType x) { 
	for (int i = 0; i < g->vertexNum; i++) { 
		if (g->vertexes[i].data == x) { 
			return i;
		}
	}
	return -1;
}
bool AddArc(ALGraph* g, VertexType x, VertexType y, int n) { 
	int xi = GetVertexIndex(g, x);
	int yi = GetVertexIndex(g, y);
	if (xi >= 0 && yi >= 0) { 
		ArcNode* p = new ArcNode;
		p->vertex = yi;
		p->info = n;
		p->next = g->vertexes[xi].first;
		g->vertexes[xi].first = p;
		return true;
	}
	return false;
}
bool CreateGraph(ALGraph* g) { 
	cout << "顶点" << endl;
	for (int i = 0; i < g->vertexNum; i++) { 
		cin >> g->vertexes[i].data;
	}
	VertexType a, b;
	int n;
	cout << "添加的边" << endl;
	for (int i = 0; i < g->arcNum; i++) { 
		cin >> a >> b >> n;
		AddArc(g, a, b, n);
	}
	return true;
}
bool TopologicalSort(ALGraph *g) { 
	int* indegree = new int[g->vertexNum];
	int* print = new int[g->vertexNum];
	for (int i = 0; i < g->vertexNum; i++) { 
		indegree[i] = 0;
	}
	for (int i = 0; i < g->vertexNum; i++) { 
		ArcNode* p = g->vertexes[i].first;
		while (p) { 
			indegree[p->vertex]++;
			p = p->next;
		}
	}
	SqStack s;
	InitStack(s);
	int count = 0;
	for (int i = 0; i < g->vertexNum; i++) { 
		if (indegree[i] == 0) { 
			Push(s,i);
		}
	}
	while (!StackEmpty(s)) { 
		int temp;
		Pop(s,temp);
		print[count] = temp;
		count++;
		for (ArcNode* p = g->vertexes[temp].first; p;p=p->next) { 
			indegree[p->vertex]--;
			if (!indegree[p->vertex]) { 
				Push(s,p->vertex);
			}
		}
	}
	for (int i = 0; i < count; i++) { 
		cout << print[i] << " ";
	}
	if (count < g->vertexNum) { 
		return false;				//排序失败,有向图中有回路
	}
	else { 
		return true;				//拓扑排序成功
	}
}
#include "ALGraph.h"
#include <iostream>
int main() { 
	ALGraph* g=new ALGraph;
	InitGraph(g);
	CreateGraph(g);
	TopologicalSort(g);
	return 0;
}

《带权有向图的邻接表表示、拓扑排序》

    原文作者:要当太空人
    原文地址: https://blog.csdn.net/Warmmm/article/details/113762803
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞