최소비용신장트리 (Spanning Tree)에 대해서 질문드립니다.
들햇님
2023.04.01
질문 제목 :최소비용신장트리 (Spanning Tree)에 대해서 질문드립니다. 질문 요약 :최소비용신장트리는 무방향 그래프에서만 정의 가능한 것인지 알고 싶습니다.질문 내용 : 안녕하세요 이번에 학교 컴퓨터네트워크 수업중에 프로젝트가 하나 나왔는데, 스패닝 트리를 응용하는 과제입니다. (브릿지와 랜 연결 구현하는 과제입니다.)
근데 이번 과제에서는 무방향 그래프가 아닌 출발점과 도착점에 따라서 가중치가 달라집니다;(이미지 참조! 이미지는 저가 그린것인데, 모든 연결은 귀찮아서 하지 않았습니다만, 인접한 요소들 끼리는 모두 연결된 상태입니다.) (브릿지 edge(사각형)에서 랜 edge로 이동시 가중치는 1, 랜 edge(동그라미)에서 브릿지 edge에서 이동 가중치는 0) (edge의 종류는 브릿지와 랜이 있습니다. 그리고 랜과 브릿지는 상호 연결되어있습니다.)저가 알기로는 Spanning tree 의 정의가 무방향 그래프에서만 성립하는걸로 아는데, 방향그래프에서도 충분히 구현가능할까요???일단 인접배열로는 구현이 불가능할 것 같고.. 인접리스트로 해야할 것 같은데.. 지금 이 과제 때문에 1주일 째 헤매고 있습니다 ㅜㅜ 도와주세요 ㅜㅜ
| 번호 | 제 목 | 글쓴이 | 날짜 |
|---|---|---|---|
| 2694854 | 절대값을 구할때 (2) | 그녀는귀여웠다 | 2025-05-15 |
| 2694827 | 이제 어떻게 공부해야할지 모르겠네요 | 새얀 | 2025-05-14 |
| 2694778 | 순열 계산요. | 맛조이 | 2025-05-14 |
| 2694754 | ShowWindow 함수를 이용하려 하는데 질문있습니다. (2) | 파도 | 2025-05-14 |
| 2694731 | 리눅스 커널의 시작점 질문 | 미르 | 2025-05-13 |
| 2694702 | 이거 뭐가문제인가요 코드수정좀 (3) | 맑은 | 2025-05-13 |
| 2694675 | C언어 후위표기를 중위표기로 | 앨런 | 2025-05-13 |
| 2694646 | 안녕하세요 파일 합치기 함수! (1) | 연블루 | 2025-05-13 |
| 2694618 | 잘몰라서 설명부탁드립니다. scanf 관련 (3) | 파라 | 2025-05-12 |
| 2694590 | 이 코드가 뭐하는 코드일까요? #2 | 빵순 | 2025-05-12 |
| 2694559 | 동적할당으로 배열(2차원열)을 만드는데 있어 그걸 함수화시키는데... (1) | 늘솔길 | 2025-05-12 |
| 2694532 | 네트워크에 관하여... (4) | 황소자리 | 2025-05-12 |
| 2694503 | 프로그램 연산 후 바로 종료되는 현상 (6) | Judicious | 2025-05-11 |
| 2694450 | while문질문입니다. (1) | 허리품 | 2025-05-11 |
| 2694420 | C언어 질문할게요(유니코드,자료형,버퍼,캐스트연산자) | 은새 | 2025-05-11 |
| 2694370 | 내일까진데 함수호출 제발 도와주세요!!!!!!!!!11 | 들찬 | 2025-05-10 |
| 2694339 | putchar()의 괄호 안에 int c=10;로 전에 선언된 c를 넣으면 안되는 이유에서 제가 생각한 것이 그 이유가 되는지 확인하고 싶습니다. (3) | 미르 | 2025-05-10 |
| 2694316 | 이 코드 어디가 잘못되었는지 고수분들 ㅠㅠ (2) | 나빛 | 2025-05-10 |
| 2694285 | 언어 공부하는 과정 좀 추천해주세요! (1) | 아빠몬 | 2025-05-09 |
| 2694258 | 카운터.. 질문입니다. (4) | 하늘빛눈망울 | 2025-05-09 |