위상정렬

출처:https://www.youtube.com/watch?v=qzfeVeajuyc

//위상정렬-순서가 정해져있는 작업, 차례로 수행해야하는 작업을 수행해야할떼 그 순서를 결정해주기위해 사용하는 알고리즘
//사이클이 발생하지 않는 방향그래프에서 작업
//사이클이 발생하면 위상정렬을 수행하지 못한다.

//위상정렬이 가능한지
//위상정렬이 가능하다면 그 결과는 무엇인지

//수행방식->스택 및 큐가 있는데 큐를 더 선호
//진입차수- 현재 노드에 들어오는 간선 개수
//1.진입차수가 0인 정점을 큐에 삽입
//2.큐에서 원소를 꺼내 연결된 모든 간선을 제거
//3.간선 제거 이후에 진입차수가 0이 된 정점을 큐에 다시 삽입
//4.큐가빌때까지 2번~3번과정을 반복
//단, 모든 원소를 방문하기전에 큐가 빈다면 사이클 존재
//모든 원소를 방문했다면 큐가 꺼낸 순서가 위상정렬의 결과

#include
#include
#include
#define Max 10
using namespace std;

int n, inDegree[Max]; //진입차수
vectora[Max];//연결된간선정보
void topologySort()
{
int result[Max]; //결과 담을꺼임
queueq;
//진입차수가 0인 노드를 큐에 삽입합니다.
for (int i = 1; i <= n; i++)
{
if (inDegree[i] == 0)q.push(i);
}
//위상정렬이 완전히 수행되려면 정확히 N개의 노드를 방문
for (int i = 1; i <= n; i++)
{
//n개를 방문하기전에 큐가빈다면 사이클 발생
if (q.empty())
{
return;
}
int x = q.front();
q.pop();
result[i] = x;//꺼낸순서 집어넣기
for (int i = 0; i < a[x].size(); i++)
{
int y = a[x][i];//간선정보 삭제
if (--inDegree[y] == 0) //진입차수 1 감소
{
q.push(y); //새롭게 진입차수가0이라면 큐에 다시 넣으면됨
}
}
}
//성공 결과
for (int i = 1; i <= n; i++)
{
printf("%d ", result[i]);
}
}
int main()
{
n = 7;//전체노드개수
a[1].push_back(2);//1번노드로부터 2번 노드로 오는것
inDegree[2]++;//그렇기때문에 진입차수증가

//...마찬가지
}