자료구조-인접리스트 그래프

목차

1. 문제정의
2. 추가 구현 사항
3. 알고리즘
4. 소스
5. 결과화면
6. 느낀점

본문내용

◆ 문제정의:
다음 요구 사항을 만족하는 무방향 가중치 그래프 관리 프로그램을 만들어라.
- 입력으로 인접 행렬을 받는다.
- 인접 리스트를 사용하여 그래프를 저장한다.
- DFS와 BFS를 지원해야한다.
- 최소 비용 신장트리를 구할 수 있어야 한다.(3가지 알고리즘 중 택1)

◆ 추가 구현 사항:
- 삼각행렬로 입력을 받아 그래프에서 방향성이 생길 상황을 미연에 방지함
- 큐와 링크드 리스트를 템플릿을 구현하여 활용
- 여러 가지 입력오류 감지

◆ 알고리즘:
우선 입력에 대해서 생각해 보았다. 입력을 인접 행렬로 받아야 한다. 0을 간선이 없는 것으로 인식하도록 한 후 0이 아닌 값을 그 간선의 가중치로 볼 것이다. 여기서 가중치를 자연수로만 하려고 했다가 음수도 가능하게 해 보았다. 나중에 최소 비용 신장 트리를 형성할 때 어떤 이유 때문에 가중치를 무시하고 반드시 지나야 하는 경우를 고려하기 위해서 이다. 또한 무방향 그래프이므로 인접 행렬은 반드시 대각 대칭이어야 하며 자기 자신으로 가는 간선이 없다. 따라서 입력 시 대각선을 제외한 삼각 행렬을 입력하게 하는 것이 입력 시간을 줄이는데도 좋고 방향성이 생기는 오류를 막을 수 있다. 이제 삼각행렬중 상삼각을 사용할 것인가 하삼각을 사용할 것인지가 문제인데 나는 상삼각을 사용하였다. 유저 입장에선 아무래도 앞의 노드의 간선을 완성해 나가는 것이 사용할 때 안정감을 줄 수 있다고 생각 했기 때문이다.

<중 략>

public:
listWGraph (int size);//size 만큼의 노드를 가진 그래프를 생성합니다.
~listWGraph();

friend istream& operator>> (istream& is, listWGraph& graph);
/***************************************************
입력방법:
- 인접 행렬을 입력하세요.
- 행렬 형식은 상삼각 행렬입니다.
- n번 노드는 n+1노드부터 엣지를 입력할 수 있습니다.
- 0은 엣지가 없는 것으로 간주합니다.
- 가중치로 음수도 사용할 수 있습니다.

참고 자료

없음