언어 자료구조 알고리즘/디딤돌 알고리즘 (C언어)

[C언어 알고리즘] 5.3 진입 차수, 진출 차수

언제나휴일 2016. 12. 1. 10:40
반응형

[C언어 알고리즘] 5.3 진입 차수, 진출 차수


이번에는 그래프에서 중요하게 생각하는 특징 중에 진입 차수와 진출 차수를 알아보아요.

 

특정 점정으로 있는 간선의 수를 해당 정점의 진입차수(In degree)라고 불러요.

그리고 특정 정점에서 있는 간선의 수를 진출차수(Out degree)라고 부르죠.

 

이번에는 그래프의 이와 같은 정보를 확인하는 기능을 구현해 보아요.

 

그래프 구현은 앞에서 소개한 것을 참고하세요.

이번에 추가할 기능은 진입 차수와 진출 차수를 확인하는 기능이예요.

void ViewIndegree(Graph *g);//진입차수 확인

void ViewOutdegree(Graph *g);//진출차수 확인

 

먼저 진입 차수를 구하는 기능을 작성하기로 해요.

진입 차수는 상대 정점에서 자신의 정점으로 있는 간선이 있는지를 말하죠.

따라서 매트릭스[다른 정점][자신의 정점] 참인 것의 개수를 세면 진입 차수를 있어요.

void ViewIndegree(Graph *g)

{

    int i, j;

    int degree;

    printf("In-degree\n");

    for (i = 0; i < g->vn; i++)

    {

        degree = 0;//0으로 설정

        for (j = 0; j < g->vn; j++)

        {

            if (g->matrix[j][i])//올 수 있는 곳이 있으면

            {

                degree++;//차수 1 증가

            }

        }

        printf("%d ", degree);//차수 출력

    }

    printf("\n");

}

 

먼저 진출 차수를 구하는 기능을 작성하기로 해요.

진출 차수는 상대 정점에서 자신의 정점으로 있는 간선이 있는지를 말하죠.

따라서 매트릭스[다른 정점][자신의 정점] 참인 것의 개수를 세면 진출 차수를 있어요.

void ViewOutdegree(Graph *g)

{

    int i, j;

    int degree;

    printf("Out-degree\n");

    for (i = 0; i < g->vn; i++)

    {

        degree = 0;//0으로 설정

        for (j = 0; j < g->vn; j++)

        {

            if (g->matrix[i][j])//갈 수 있는 곳이 있으면

            {

                degree++;//차수 1 증가

            }

        }

        printf("%d ", degree);//차수 출력

    }

    printf("\n");

}

반응형