인접행렬2 [알고리즘] ep5-1+) 인접리스트, 인접행렬 구현 다음의 문제 1과 문제 2는 주어진 그래프를 인접리스트 및 인접행렬로 각각 표현하여 해결해야 한다. 다음은 두 문제 모두에 공통된 사항이다. 1) 그림 1의 그래프에 관해 해결해야 한다. 2) 가중치의 값은 양수와 음수 모두 가능하나, 0은 허용하지 않는다. 3) 그림 1 그래프의 정점 개수는 변경되지 않는다. 단, 간선 개수는 변화할 수 있다. 참고로 정점 6개인 그래프에서 가능한 간선 개수는, 자기 자신으로 가는 간선(즉, 루프)을 포함하여 최대 21(= 6 + 5 + 4 + 3 + 2 + 1)개다. 4) 간선의 이름을 생략하기로 한다. 따라서 간선 구조체의 이름 필드는 정의하지 않아도 된다. 5) 그래프를 배열 또는 연결리스트 가운데 어느 것을 이용하여 구현할지는 각자의 판단에 맡긴다. 문.. 2024. 7. 21. [알고리즘] ep5-1) 그래프(graph) ㅁ그래프(graph) ADT: (vertex, edge)의 쌍v: 정점 노드들의 집합e: 간선 노드들의 집합 정점: 공항을 표현하며 공항도시 이름을 저장간선: 두 공항 사이의 항로를 표현하며 항로의 거리(mile)를 저장 [그래프 응용]- 전자회로: 인쇄회로기판(PCB), 집적회로(IC)- 교통망: 고속도로망, 항공노선망- 컴퓨터 네트워크: LAN, 인터넷, 웹- 데이터베이스: 개체-관계 다이어그램(entity-relationship diagram) ㅇ무방향그래프(undirected graph): 모든 간선이 무방향간선인 그래프 ㅇ방향그래프(directed graph): 모든 간선이 방향간선인 그래프 [그래프 기본 용어]간선의 끝점(end vertex or endpoint): 점점 U와 V는 a.. 2024. 7. 21. 이전 1 다음