하루5분코딩"Graph"
## Graph : 노드 그리고 노드와 노드를 연결하는 edge의 구성
✓tip 그래프는 무방향(undirected)과 방향(directed) 일수있다. "무방향"은 연결된 노드가 대칭, 즉 서로를 가리킨다고 볼수 있고 "방향"은 노드의 비대칭, 즉 한쪽에서만 가리킨다고 볼수있다.
How to search "graph"
- DFS(Depth-First search) 깊이 우선 검색
- BFS(Breadth-First search) 넓이 우선 검색
How to use searching skill
- Stack 이나 Queue 에 들어갔다가 빼주면서 출력 그리고 연결된 노드를 넣어준다
- DFS 는 주로 Stack 으로 사용하고, BFS 는 Queue 에서 사용한다.
✓Reference - https://www.youtube.com/watch?v=_hxFgg7TLZQ
인접 행렬과 인접 리스트
- 인접 리스트: 정점을 노드의 키로 사용하며 해당 노드의 이웃들을 리스트에 저장한다.
- 인접 행렬 : 행렬의 각 항목이 두 정점 간에 연결을 나타내는 V*V 행렬이다.
진입 차수와 진출 차수
-한 정점에 도착하는 edge수
-한 정점에서 출발하는 edge 수
둘을 더하면 차수
가 된다.
✓ Method
- addNode(node) - 그래프에 노드를 추가합니다.
- addEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선을 추가합니다.
- removeNode(node) - 그래프에서 노드를 삭제합니다.
- removeEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선을 삭제합니다.
- hasEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선 존재 여부를 반환합니다.
- contains(node) - 그래프에 해당 노드가 존재하는지 여부를 반환합니다.
✓ 사용
addNode(node) { this.nodes[node] = this.nodes[node] || []; }
contains(node) { return this.nodes.hasOwnProperty(node); }
removeNode(node) { for (let key of this.nodes[node]) { this.removeEdge(node, key) } delete this.nodes[node] }
hasEdge(fromNode, toNode) { for (let key of this.nodes[fromNode]) { if (key === toNode) { return true; } } return false; }
addEdge(fromNode, toNode) { this.nodes[fromNode].push(toNode) this.nodes[toNode].push(fromNode) }
removeEdge(fromNode, toNode) { let from = this.nodes[fromNode] let to = this.nodes[toNode] from.splice(from.indexOf(toNode), 1) to.splice(to.indexOf(fromNode), 1) }
Author And Source
이 문제에 관하여(하루5분코딩"Graph"), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@-hsw9724/하루5분코딩Graph저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)