위상 정렬 문제 C

조건

• 인접리스트 배열 사용
• 진입차수를 이용하여 위상정렬
• 새로 입력되는 간선에 대한 노드를 리스트의 맨 앞에 삽입해야
• 진입간선, 진출간선을 별도의 인접리스트로 보관한다.(처음에 이거 몰라서 헤맸음;;)
• 위상순서를 구하는 과정에서 동시에 방향사이클의 존재 여부를 확인할 수 있도록 코드 짜야 함

형태

<struct>

• Edge
  • int origin
  • int destination
• Vertex
  • struct incList* inEdge
  • struct incList* outEdge
  • char name
  • int inDegree
• IncList
  • int e
  • struct incList* next

<main>

1. buildGraph
   1. 정점의 개수
   2. 정점의 이름
   3. 간선의 개수
   4. 간선 정보
   를 입력 받고 방향 그래프 생성
   • 새로 입력되는 간선(inEdge 혹은 outEdge)에 대한 노드를 리스트의 맨 앞에 삽입해야!!
   • 방향 간선 초기화 할 때 outEdges는 시작 정점에, inEdges는 도착정점에서만 갱신해야 한다.
   • Alg insertDirectedEdge(uName, wName, i) u<-index(uName) w<-index(wName) G.edges[i].origin<-u G.edges[i].destination<-w **addFirst(G.vertex[u].outEdges,i) addFirst(G.vertex[w].inEdges,i)** G.vertex[w].inDegree++;
2. topologicalSort(그래프를 위상 정렬)
   1. vertex의 inDegree에 저장했던 정점 별 진입차수를 in 배열에 할당해준다.
   주의
   • 위상순서를 구하는 과정에서 동시에 방향사이클의 존재 여부를 확인할 수 있도록 코드 짜야 함

   while(!Q.isEmpty())
   	u <-Q.dequeue()
   	topOrder[t]<-u
   	t ++;
   	for each e in G.vertex[u].outEdges
   		w<-G.edges[e].destination
   		**in[w] --;
   		if (in[w]=0)
   			Q.enqueue(w)**