[C언어 자료구조] 7.3 인접 행렬로 방향성 있는그래프

7.3 인접 행렬로 방향성 있는그래프

---

방향성 있는 그래프는 간선의 출발지와 목적지가 정해져 있는 그래프를 말해요.

 

방향성 있는 그래프를 표현하는 방법 중에 간단한 그래프에는 인접 행렬을 많이 사용해요.

 

먼저 그래프 형식을 정의하기로 해요.

그래프 형식은 방향성 없는 그래프와 차이가 없어요.

정점의 개수와 인접 행렬을 멤버를 추가하세요.

typedef struct{//그래프 형식 정의

    int vn; //정점 개수

    int **matrix;//그래프 인접 행렬

} Graph;

 

그래프를 생성하고 소멸, 추가, 정보 출력하는 기능을 제공하기로 해요.

Graph *NewGraph(int max_vertex);//그래프 동적 생성

void DeleteGraph(Graph *graph);//그래프 소멸

void AddEdge(Graph *graph, int start, int goal);//간선 추가

 void ViewGraph(Graph *graph);//그래프 정보 출력

 

그래프를 생성하는 함수를 작성하기로 해요.

먼저 그래프를 동적 메모리 할당하고 최대 정점 개수를 설정하세요.

그래프의 매트릭스 메모리를 할당하세요.

그래프의 정점 개수만큼 매트릭스의 행을 메모리를 할당하고 할당한 메모리의 내용을 0으로 초기화하세요.

Graph *NewGraph(int max_vertex)

{

    int i = 0;

    Graph *graph = (Graph *)malloc(sizeof(Graph));//그래프 메모리 동적 할당

    graph->vn = max_vertex;//최대 정점 개수 설정

    graph->matrix = (int **)malloc(sizeof(int *)*max_vertex);//매트릭스 메모리 할당

    for (i = 0; i < max_vertex; i++)

    {

        graph->matrix[i] = (int *)malloc(sizeof(int)*max_vertex);//매트릭스 [i-row] 메모리 할당

        memset(graph->matrix[i], 0, sizeof(int)*max_vertex);//메모리 0으로 초기화

    }

    return graph;

}

 

 

메모리를 소멸하는 함수를 작성하세요.

최대 정점 개수만큼 매트릭스의 행을 소멸한 후에 매트릭스를 소멸하세요.

그리고 그래프를 소멸하세요.

void DeleteGraph(Graph *graph)

{

    int i = 0;

   

    for (i = 0; i < graph->vn; i++)//최대 정점 개수만큼

    {

        free(graph->matrix[i]);//매트릭스 [i-row]  메모리 소멸

    }

    free(graph->matrix);//매트릭스 메모리 해제

    free(graph);//그래프 메모리 해제

}

 

간선을 추가하는 함수를 작성하세요.

방향성 있는 그래프이므로 매트릭스의 [start][goal] 요소를 1로 설정하세요.

void AddEdge(Graph *graph, int start, int goal)

{

    graph->matrix[start][goal] = 1;//간선설정

}

 

그래프 정보를 출력하는 함수를 작성하세요.

모든 정점에서 다른 모든 정점으로 갈 수 있는지 확인하여 출력하세요.

void ViewGraph(Graph *graph)

{

    int i =0;

    int j =0;

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

    {

        printf("%d 에서 갈 수 있는 정점:",i);

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

        {

            if(graph->matrix[i][j])

            {

                printf("%d ",j);

            }

        }

        printf("\n");

    }

}