[자료구조] 무방향 그래프 알고리즘

* A와 B로 연결이 한번만 되는 것은 방향 그래프이다.

A->B

* A와 B로 연결이 두번 되는 것이 무방향 그래프이다. 방향이 없다.

A - B

이진탐색트리보단 쉽지만 결코 이해하고 코딩하는 것은 쉽지않다..!

A와 B가 연결되었고 A와 C가 연결되었다면 무방향 그래프로 나타낼 수 있다.

A - C, B  // a와 c, b는 연결되었다.

B - A  // b는 a와 연결되었다.

C - A  // c는 a와 연결되었다.

main.cpp

#include <stdio.h>

#include "graph.h"

int main(){

struct data graph;

init(&graph, 3);  // 그래프와 정점 숫자를 넘겨준다. 정점은 a,b,c 3개이다.

add(&graph, A, B);   // a와 b를 연결한다.

add(&graph, A, C);  // a와 c를 연결한다.

show(&graph);  // 연결된 그래프를 보여준다.

destroy(&graph);  // 그래프를 파괴한다.

return 0;

}

graph.cpp

#include <stdio.h>

#include <stdlib.h>

#include "graph.h"

void init(struct data *a, int num){

int i;

a->ad = (struct link*)malloc(sizeof(struct link)*num);

a->v = num;   // v는 전체 정점이다.

a->e = 0;  // e는 전체 간선이다.

for (i = 0; i < num; i++){

listinit(&(a->ad[i]));  // 초기화 해준다.

}

}

void listinit(struct link *a){

a->head = (struct node*)malloc(sizeof(struct node));  // 정점 수만큼 동적할당한다.

a->num = 0;  // 정점이 몇 개의 정점과 연결 되었는지 나타낸다.

a->head->next = NULL;  // 현재 정점이 가리키는 다른 정점의 위치를 초기화함

}

void add(struct data *a, int b, int c){

insert(&(a->ad[b]), c);  // 무방향이기 때문에 2번을 써줬다. 서로 가리키게하기 위해서

insert(&(a->ad[c]), b);

a->e += 1;  // a와 b가 연결된다면 간선이 1개 증가하므로 1을 더해준다.

}

void insert(struct link *a, int num){

struct node *newnode = (struct node*)malloc(sizeof(struct node));  // 연결될 노드를 만든다.

newnode->num = num;  // 연결될 노드의 정점을 담는다. 0이면 a 1이면 b

newnode->next = a->head->next; 

a->head->next = newnode;

// 노드끼리 서로의 주소를 바꿔주는 듯한 모양새이다.

// 서로 바꿔주는 이유는 두개의 노드가 연결된 곳에 다른 노드가 다시 연결될때 주소를 바꿔주기 위해서이다.

(a->num)++;  // 현재 정점에 연결된 정점이 몇 개인지 증가한다.

}

void show(struct data *a){

int i;

int x;  // 숫자를 문자로 변환한다. (0->a 1->b)

for (i = 0; i < a->v; i++){

printf("%c와 연결: ", i + 65);

if (first(&(a->ad[i]), &x)){

printf("%c ", x + 65);

while (next(&(a->ad[i]), &x)){

printf("%c ", x + 65);

}

}

printf("\n");

}

}

int first(struct link *a, int *b){

if (a->head->next == NULL){  // 연결할 노드에 연결된 노드가 없다면 반환

return 0;

}

a->before = a->head;

a->cur = a->head->next;  // 커서에 연결된 노드의 주소를 넣는다.

*b = a->cur->num;  // 연결된 노드의 값 출력 (a와 연결된 c의 값 2 출력)

return 1;

}

int next(struct link *a, int *b){

if (a->cur->next == NULL){  // 연결된 노드의 또 연결된 노드가 없다면 반환

return 0;

}

a->before = a->cur;

a->cur = a->cur->next;  // 연결된 노드의 연결된 노드의 주소를 넣음. 즉 a와 연결된 c와 연결된 b의 주소.

*b = a->cur->num; // 연결된 노드의 값 출력

return 1;

}

void destroy(struct data *a){

if (a->ad != NULL){  // malloc 배열을 해제한다.

free(a->ad);

}

}

graph.h

enum{

A, B, C, D

};

struct data{

int v;

int e;

struct link *ad;

};

struct link{

struct node *head;

struct node *before;

struct node *cur;

int num;

};

struct node{

int num;

struct node *next;

};

void init(struct data *a, int num);

void add(struct data *a, int b, int c);

void listinit(struct link *a);

void insert(struct link *a, int num);

void destroy(struct data *a);

void show(struct data *a);

int first(struct link *a, int *b);

int next(struct link *a, int *b);

------------------------------------------------------------------------------------------------

2017.01.06

#include <stdio.h>

#include <stdlib.h>

struct data{

 int v;  // 점 개수

 int e;  // 선 개수

 struct link *ad;  // 점 개수만큼 3개 생성

};

struct link{

 struct node *head;  

 struct node *before;

 struct node *cur;

 int num; // 점과 점 연결된 숫자

};

struct node{

int num; 

struct node *next;

};

void listinit(struct link *a){

a->head = (struct node*)malloc(sizeof(struct node));  // 정점 수만큼 동적할당한다.

a->num = 0;  // 정점이 몇 개의 정점과 연결 되었는지 나타낸다.

a->head->next = NULL;  // 현재 정점이 가리키는 다른 정점의 위치를 초기화함

}

void init(struct data *a, int num){   // list , 3

int i;

a->ad = (struct link*)malloc(sizeof(struct link)*num);

a->v = num;   // v는 전체 정점이다.

a->e = 0;  // e는 전체 간선이다.

for (i = 0; i < num; i++){

listinit(&(a->ad[i]));  // 초기화 해준다.

}

}

void insert(struct link *a, int num){

struct node *newnode = (struct node*)malloc(sizeof(struct node));  // 연결될 노드를 만든다.

newnode->num = num;  // 연결될 노드의 정점을 담는다. 0이면 a 1이면 b

newnode->next = a->head->next; 

a->head->next = newnode;

// 노드끼리 서로의 주소를 바꿔주는 듯한 모양새이다.

// 서로 바꿔주는 이유는 두개의 노드가 연결된 곳에 다른 노드가 다시 연결될때 주소를 바꿔주기 위해서이다.

(a->num)++;  // 현재 정점에 연결된 정점이 몇 개인지 증가한다.

}

void add(struct data *a, int b, int c){  // 그래프, 0, 1 넘김

insert(&(a->ad[b]), c);  // 무방향이기 때문에 2번을 써줬다. 서로 가리키게하기 위해서

insert(&(a->ad[c]), b);

a->e += 1;  // a와 b가 연결된다면 간선이 1개 증가하므로 1을 더해준다.

}

int first(struct link *a, int *b){

if (a->head->next == NULL){  // 연결할 노드에 연결된 노드가 없다면 반환

return 0;

}

a->before = a->head;

a->cur = a->head->next;  // 커서에 연결된 노드의 주소를 넣는다.

*b = a->cur->num;  // 연결된 노드의 값 출력 (a와 연결된 c의 값 2 출력)

return 1;

}

int next(struct link *a, int *b){

if (a->cur->next == NULL){  // 연결된 노드의 또 연결된 노드가 없다면 반환

return 0;

}

a->before = a->cur;

a->cur = a->cur->next;  // 연결된 노드의 연결된 노드의 주소를 넣음. 즉 a와 연결된 c와 연결된 b의 주소.

*b = a->cur->num; // 연결된 노드의 값 출력

return 1;

}

void show(struct data *a){

int i;

int x;  // 숫자를 문자로 변환한다. (0->a 1->b)

for (i = 0; i < a->v; i++){

printf("%c와 연결: ", i + 65);

if (first(&(a->ad[i]), &x)){

printf("%c ", x + 65);

while (next(&(a->ad[i]), &x)){

printf("%c ", x + 65);

}

}

printf("\n");

}

}

void destroy(struct data *a){

if (a->ad != NULL){  // malloc 배열을 해제한다.

free(a->ad);

}

}

int main(){

struct data graph;

enum{ A, B, C, D };

init(&graph, 3);  // 그래프와 정점 숫자를 넘겨준다. 정점은 a,b,c 3개이다.

add(&graph, A, B);   // a와 b를 연결한다.

add(&graph, A, C);  // a와 c를 연결한다.

show(&graph);  // 연결된 그래프를 보여준다.

destroy(&graph);  // 그래프를 파괴한다.

return 0;

}

입력할땐 ad의 head->next와 newnode의 next를 사용한다.

첫번째는 newnode(1)의 next에 ad의 head의 next값인 null을 넣는다.

그 후 ad의 head의 next에 newnode(1)을 넣는다.

두번째는 newnode(2)의 next에 ad의 head의 next값인 newnode(1)을 넣는다.

그 후 ad의 head의 next에 newnode(2)을 넣는다.

출력할땐 ad의 before와 cur를 사용한다.

before의 경우는 처음엔 ad의 head를 저장했다가 계속 cur에 있는 newnode의 위치를 저장한다.

cur의 경우는 처음엔 ad의 head의 next를 저장했다가 계속 cur의 next에 있는 newnode 위치를 저장한다.