<div id="readability-page-1" class="page"><div><ol>
<li>그래프란 ? 
정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조. 
정점 집합과 간선 집합으로 표현할 수 있다.</li>
</ol>
실무사용 예시 
<ul>
<li>지하철 노선도</li>
<li>페이지랭크 
<a href="https://ko.wikipedia.org/wiki/%ED%8E%98%EC%9D%B4%EC%A7%80%EB%9E%AD%ED%81%AC">https://ko.wikipedia.org/wiki/%ED%8E%98%EC%9D%B4%EC%A7%80%EB%9E%AD%ED%81%AC</a></li>
</ul>
2-1 그래프의 특징
<ul>
<li>정점은 여러개의 간선을 가질 수 있다.</li>
<li>크게 방향 그리프와 무방향 그래프로 나눌 수 있다.</li>
<li>간선은 가중치를 가질 수 있다.</li>
<li>사이클이 발생할 수 있다.</li>
</ul>
2-2 그래프 종류
<h3 id="방향의-유무">방향의 유무</h3>
<ul>
<li>
무방향 그래프 
간선으로 이어진 정점끼리는 양방향으로 이동이 가능 
표현하기에 (A, B)와 (B, A)는 같은 간선으로 취급 
ex) 양방향 통행 도로 
<img src="https://velog.velcdn.com/images/2taesung/post/0984901c-1c1b-4d8e-b6e5-4bed60316c52/image.png">
</li>
<li>
방향 그래프 
간선에 방향성이 존재하는 그래프 
양방향으로 갈 수 있더라도 (A, B)와 (B, A)는 다른 간선으로 취급 
ex) 일방 통행
</li>
</ul>
<img src="https://velog.velcdn.com/images/2taesung/post/63de104f-0704-4d33-8588-4435d867639c/image.png">
<h3 id="연결-상태에따라">연결 상태에따라</h3>
<ul>
<li>연결 그래프 
모든 정점이 서로 이동 가능한 상태인 그래프</li>
</ul>
<img src="https://velog.velcdn.com/images/2taesung/post/e0d7d590-dc16-4004-bd06-d49e780bea1c/image.png">
<ul>
<li>비연결 그래프 
특점 정점쌍 사이에 간선이 존재하지 않는 그래프</li>
</ul>
<img src="https://velog.velcdn.com/images/2taesung/post/3ef84c79-db4e-49a8-845b-82bc74b1c25f/image.png">
<ul>
<li>완전 그래프 
모든 정점끼리 연결된 상태인 그래프</li>
</ul>
<img src="https://velog.velcdn.com/images/2taesung/post/038b55a5-1656-4e06-919c-1475481ce50f/image.png">
한 노드(정점)의 간선 수 = (모든 노드의 수 -1) 
모든 노드의 수 = 한 노드의 간선수 +1
2-3 사이클 
그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분 
<img src="https://velog.velcdn.com/images/2taesung/post/0459cd69-d540-4cae-a1bb-1dd9acb98929/image.png">
<ol start="3">
<li>코테 
핵심 키워드 : 
대표문제</li>
</ol></div></div>

2taesung.log

Taesung Lee

그래프란 ?
정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조. 
정점 집합과 간선 집합으로 표현할 수 있다.
실무사용 예시 
지하철 노선도
페이지랭크
https://ko.wikipedia.org/wiki/%ED%8E%98%EC%9D%B4%EC%A7%80%EB%9E%AD%ED%81%AC
2-1 그래프의 특징
정점은 여러개의 간선을 가질 수 있다.
크게 방향 그리프와 무방향 그래프로 나눌 수 있다.
간선은 가중치를 가질 수 있다.
사이클이 발생할 수 있다.
2-2 그래프 종류
방향의 유무
무방향 그래프
간선으로 이어진 정점끼리는 양방향으로 이동이 가능
표현하기에 (A, B)와 (B, A)는 같은 간선으로 취급
ex) 양방향 통행 도로
방향 그래프
간선에 방향성이 존재하는 그래프
양방향으로 갈 수 있더라도 (A, B)와 (B, A)는 다른 간선으로 취급
ex) 일방 통행
연결 상태에따라
연결 그래프
모든 정점이 서로 이동 가능한 상태인 그래프
비연결 그래프
특점 정점쌍 사이에 간선이 존재하지 않는 그래프
완전 그래프
모든 정점끼리 연결된 상태인 그래프
한 노드(정점)의 간선 수 = (모든 노드의 수 -1)
모든 노드의 수 = 한 노드의 간선수 +1
2-3 사이클
그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분
코테
핵심 키워드 :
대표문제

자료구조 - 그래프

댓글