TopoSortGraph.h : 위상 정렬 기능이 추가된 인접 리스트 기반 그래프

#pragma once

#ifndef ___TopoSort

#define ___TopoSort

//TopoSortGraph.h : 위상 정렬 기능이 추가된 인접 리스트 기반 그래프

#include "AdjListGraph.h"

#include "ArrayStack.h"

class TopoSortGraph : public AdjListGraph {

int inDeg[MAX_VTXS]; //정점의 진입차수

public:

void insertDirEdge(int u, int v) { //방향성 간선 삽입 연산

adj[u] = new Node(v, adj[u]);

}

// 위상정렬을 수행한다.

void TopoSort() {

//모든 정점의 진입 차수를 계산 

for (int i = 0; i < size; i++) //초기화

inDeg[i] = 0;

for (int i = 0; i < size; i++) {

Node* node = adj[i]; //정점 i에서 나오는 간선들

while (node != NULL) {

inDeg[node->getId()]++;

node = node->getLink();

}

}

//진입 차수가 0인 정점을 스택에 삽입

ArrayStack s;

for (int i = 0; i < size; i++)

if (inDeg[i] == 0) s.push(i);

// 위상 순서를 생성

while (s.isEmpty() == false) {

int w = s.pop();

printf(" %c", getVertex(w)); //정점 출력

Node* node = adj[w]; //각 정점의 진입 차수를 변경

while (node != NULL) {

int u = node->getId();

inDeg[u]--; //진입 차수를 감수

if (inDeg[u] == 0) //진입 차수가 0인 정점을 push

s.push(u);

node = node->getLink(); //다음 정점

}

}

printf("\n");

}

};

#endif // !___TopoSort