[C언어] 자료구조 - 그래프 기본연산 배열 -2

그래프 용어랑 종류랑 저번에 익혔으니까 이제 그래프를 만들 기초는 다져놨네? 

그럼 그래프를 만들어봐야겠지?? 

 

그래프는 노드간의 연결관계를 나타내야하는데

저번에도 매트릭스로 나타내면 좋을 것 같다고 했잖아.

 

정말 행렬로 만드는게 효율적이라서 2차원 매트릭스로 구성해야겠는데

n개와 연결관계를 나타낼거니까

n*n행렬로 만들면 될것같음. 그런 생각을 하면 굿굿

 

근데 연결리스트로도 만들 수 있다?  그건 나중에보고

 

아무튼 제일먼저 생각난 것이 배열이니까 행렬로 만들어보자

배열은 G[i][j]이런식으로 만드는 거 알지?

연결되었으면 1, 아니면 0으로 표시하자 그렇게해도 충분히 연결관계를 파악할 수 있으니까 

우선 무방향그래프로 구현한다면 i행 j열의 관계와 j행 i열의 값이 똑같겠지? 

대각선을 기준으로 대칭이 되겠다. 그렇지?

 

그리고 배열로 접근하면 i와 j가 연결되어있는지 알려면

G[i][j]로 접근해서 0인지 1인지 알아보면되겠지?

 

인덱스만 알면 되니까 바로 접근 가능하고

차수를 알고싶으면 예를 들어 i 노드의 차수는 i행 전체를 조사하면 나오겠지?

그런식으로 배열은 직접 접근이 가능해서 좋아

 

 

 

그래프를 말로 구현했으면 이제 코드로도 구현해봐야겠지?

 

그래프 노드, 정점에 데이터도 저장할 수 있어 그래서 vdata[]이렇게 선언하지

여기서 adj는 adjacent 인접한이란 뜻을 가져서 인접행렬을 가리켜

 

for문을 2번써서 첫번째 행의 max크기의 열을 만들고 그다음 두번째 행의 max... 

 이런식으로 반복해서 행렬을 만드는거다. 알겠지? 

 

기본적으로 삽입연산은 어떻게 할까? 배열이니까 배열의 정보를 수정하는 거겠지? 그렇게 생각하고 코드를 보자.

 

밑에랑 위에 차이를 알겠어?

위에는 교환법칙이 성립안하는 방향그래프일때!!

밑에는 교환법칙 성립하는 무방향그래프 일때 !! ㅋㅋㅋ

 

 

삭제는 왜 없냐고?? ㅋㅋ1대신 0삽입하면 연결이 끊어지는 거잖아ㅋㅋㅋ 그치?

 

 

근데 그래프는 시각적이라는 그런느낌이 있지?? 그러면 출력을 해야할거아냐 한 번 출력해보자

 

 

이러면 잘 나오긴 할거야.

 

 

간선 삭제는 쉽잖아 그렇잖아? 연결을 끊기는 쉽다.. 그치?

헤어지는건 쉬운데.. 내 인생에서 그 사람을 지운다는 건 참 어렵지..ㅠㅠ

그래서 여기서도 노드를 지우긴 정말 어렵더라 

그렇다고 내 경험담은 딱히 아냐 

 

그건 그렇고 이젠 그럼 연결리스트로 구현해볼까??

다음 글에서 해보자 ㅋㅋ