1. 그래프의 역사와 이야깃거리
-> 직관적으로는 모든 정점에 입구와 출구가 있어야 하기 때문
그래프는 정점(노드)과 간선을 하나로 모아 놓은 자료구조인데
그래프는 하나의 표현 방법이고 그와 관련된 알고리즘이 매우 많다.
그래프는 저장보다 표현의 특색이 훨씬 짙다.
2. 그래프의 이해와 종류
방향 그래프의 예에서 민석이 연락을 전달했을 때, 지율,수정으로부터 연락을 받으면 연락이 모두 전달됐음을 알 수 있다.
위 방향 그래프의 단점 - 동수가 연락을 못하면 지율에게 연락이 끊겨 민석에게 지율로부터 연락이 오지 않는데, 연락이 어디서 끊겼는지 민석은 알 수가 없음
용어 설명 -
무방향 완전 그래프 : 각 정점들이 자기 자신을 제외한 모든 정점과 연결되어 있는 무방향 그래프를 무방향 완전 그래프라 한다.
방향 완전 그래프 : 각 정점들이 자기 자신으로부터 자기 자신을 제외한 모든 정점에 연결되어 있는 방향 그래프를 방향 완전 그래프라 한다.
3. 가중치 그래프와 부분 그래프
각 간선에 가중치를 부여할 수 있고, 이는 무방향, 방향 모두에 부여할 수 있다.
정점과 간선은 집합으로 나타낼 수 있는데, 어떤 그래프의 정점의 집합과 간선의 집합의 부분집합으로 이루어진 그래프를 부분 그래프라 한다.
4. 그래프의 집합 표현
무방향 그래프의 간선은 ()로 표기, 방향 그래프의 간선은 <>로 표기한다.
그리고 방향 그래프에서 간선의 방향성은 <출발점, 도착점> 으로 표현한다.
5. 그래프의 ADT
Tip. enumeration 선언을 하면 해당 단어들은 상수값으로 선언이 된다.
ex. enum character {
A = 0, B, C, D, E
};
열거형의 값은 처음에만 할당해주면 그 아래에 오는 값들은 1씩 증가하면서 자동으로 할당되고 아무 값도 할당하지 않으면 0부터 시작한다.
사용범 :
enum character Ch; //열거형 변수 선언
Ch = D;
printf("%d", Ch);//3춣력
이 때 enum안에 선언한 단어들은 모두 상수이다!!!!!
즉, E = 6; 등으로 값의 변경이 불가능하다.
(1) 인접 행렬 기반
A에서 B가 연결되면 무방향 그래프는 A행 B열 즉, 0행 1열과 B행 A열 1행 0열 모두 1로 바꿔주고
방향 그래프는 A형 B열만 1로 바꿔준다.
(2) 인접 리스트 기반
궁금한 점 : 저렇게 인접 리스트 기반으로 그래프를 구현하면
A -> B -> C -> D를 구현한거지 A에서 B,C,D를 연결한걸 구현한 건 아니지 않나?
X
각 연결리스트는 정점이 가진 간선의 갯수만큼의 길이를 가지게 된다고 생각하면 이해가 갈 것이다.
6. 구현
N과 M이 주어지는데 N은 정점의 개수, M은 간선의 개수이다.
출력은 1부터 N까지의 정점에서부터의 간선을 순서대로 출력
(1) 인접 리스트 기반
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node* next;
}Node;
int main()
{
int i, N, M;
int x;
Node* cur;
scanf("%d %d", &N, &M);//정점의 개수 N개, 간선의 개수 M개
Node** array = (Node**)malloc(sizeof(Node*) * (N + 1));
for (i = 1; i <= N; i++)
{
array[i] = (Node*)malloc(sizeof(Node));
array[i]->next = NULL;
}
for (i = 0; i < M; i++)
{
scanf("%d", &x);
cur = array[x];
while (cur->next != NULL)
{
cur = cur->next;
}
cur->next = malloc(sizeof(Node));
cur->next->next = NULL;
scanf("%d", &(cur->next->data));
}
for (i = 1; i <= N; i++)
{
cur = array[i];
while (cur->next != NULL)
{
printf("%d %d\n", i, cur->next->data);
cur = cur->next;
}
}
return 0;
}(2) 인접 행렬 기반
#include <stdio.h>
#include <stdlib.h>
int main()
{
int i, j;
int N, M;
int x, y;
scanf("%d %d", &N, &M);
char** array = calloc(N + 1, sizeof(char*));
for (i = 0; i <= N; i++)
{
array[i] = calloc(N + 1, sizeof(char));
}
for (i = 0; i < M; i++)
{
scanf("%d %d", &x, &y);
array[x][y] = 1;
}
for (i = 1; i <= N; i++)
{
for (j = 1; j <= N; j++)
{
if (array[i][j]) printf("%d %d\n", i, j);
}
}
return 0;
}
