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

``````#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;
}
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
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。