C++ 위상 정렬 - 연결리스트, 스택

 

 

코드 출처
C++로 쉽게 풀어쓴 자료구조 11장

 

---

 

class Node {
	int id; //정점의 id
	Node* link; //다음 노드의 포인터
public:
	Node(int i, Node* l = NULL): id(i),link(l) {}
	int getId() { return id; }
	Node* getLink() { return link; }
};

int vertices[1000]; //정점 배열
Node* adj[1000]; //각 정점의 인접리스트
int inDeg[1000]; //정점의 진입차수

void insertEdge(int u, int v) {
	adj[u] = new Node(v, adj[u]);
}

void TopoSort() {
	//모든 정점의 진입 차수 계산
	for (int i = 0; i < N; i++) { //초기화
		inDeg[i] = 0; 
	}
	for (int i = 0; i < N; i++) { //정점 i에서 나오는 간선의 수 세기
		Node* node = adj[i];
		while (node != NULL) {
			inDeg[node->getId()]++;
			node = node->getLink();
		}
	}

	//진입차수가 0인 정점 스택에 삽입
	stack<int> stack;
	for (int i = 0; i < N; i++) {
		if (inDeg[i] == 0) {
			stack.push(i);
		}
	}

	//위상정렬 순서 생성
	while (!stack.empty()) {
		int w = stack.top();
		cout << w << " ";           //정점 출력
		stack.pop();

		Node* node = adj[w];
		while (node != NULL) {
			int u = node->getId();
			inDeg[u]--;                 //w와 인접하는 모든 정점의 진입차수 감소
			if (inDeg[u] == 0) {        //진입차수 0인 정점 스택에 push   
				stack.push(u);
			}
			node = node->getLink();
		}
	}

}

 

 

 

참고

벡터, 큐 사용 위상정렬

2021/01/19 - [[백준 알고리즘]] - 2623번 음악프로그램 | Baekjoon BOJ 백준 2623 C++ 코드, 해설, 풀이

2623번 음악프로그램 | Baekjoon BOJ 백준 2623 C++ 코드, 해설, 풀이