그래프

• 정점(Node)와 간선(Edge)로 구성이 되어있다.
• 정점은 점이고 주로 번호가 써있다. 간선은 선이고 정점과의 관계가 표시되어있다(선의 방향)
• G = (V,E)로 나타낸다.

• 사이클은 시작=도착을 사이클이라고 한다.

단순경로와 단순 사이클

• 단순 : 같은 정점을 두번이상 방문하지 않는 경로/사이클
• 특별한 말이 없으면, 경로와 사이클은 단순경로/사이클을 의미한다.

• 방향이 없는 경우, 양방향 모두를 저장을 해서 표현을 한다.

간선 여러개, 루프의 경우도 있다.

가중치

• 가중치가 없는 경우 가중치를 1이라고 계산을 한다.

차수

• 들어가는 간선을 in-degree 나가는 간선을 out-degree라고 한다.

그래프 표현

• 정점은 갯수만 표시를 하면 된다.
• 간선은 방향을 설정을 해야되기때문에, 간선을 저장하는것이 그래프를 저장을 하는 것이다. 간선은 무엇과 무엇이 연결되어 있는지를 표현해야한다.
• 예를들어 정점(2)와 어떤 정점이 연결이 되었는지 표시를 해야한다.

그래프를 저장할때는 인접행렬과 인접리스트 2가지가 있다.

• 정점의 갯수가 V일때 VxV행렬로 표현을 할 수 있다.

• 인접행렬은 없는 간선도 저장을 하기때문에 잘 사용을 안한다.
• 그래프에 존재하지 않는 간선도 저장을 하기때문에 복잡한 그래프에는 잘 사용을 안한다.

int a[10][10];
int main() {
	int n, m;
    scanf("%d %d", &n, &m);
    for (int i=0; i<m; i++) {
    	int u,v;
        scanf("%d %d", &u, &v);
        // 양방향 그래프
        a[u][v] a[v][u] = 1;
    	// 단방향 그래프
        a[u][v]=1;
    }
}

• 위의 그래프는 가중치가 없는(w=1)인 그래프의 표현이다.
• 가중치가 있는 경우는 a[i][j] w(가중치)가 들어간다.
• 만약의 가중치가 음수라면? 이 경우 간선이 없는 경우는 a[i][j]=-1을 저장을 한다.
• 가중치의 범위가 정수라면? 간선이 있으면 1, 없으면 0인 인접행렬을 만들고, 또 다른 인접행렬을 만들어서 간선이 있으면 가중치로 값을 둔다.

int a[10][10];
int main() {
	int n, m;
    scanf("%d %d", &n, &m);
    for (int i=0; i<m; i++) {
    	int u,v, w;
        scanf("%d %d %d", &u, &v, &w);
        // 양방향 그래프
        a[u][v] a[v][u] = w;
    	// 단방향 그래프
        a[u][v]=1;
    }
}