자료구조 14강 그래프 정리

그래프 수학자 오일러(Euler)에 의해 1736년 고안됨. 버스와 지하철의 노선도, 출발지와 목적지에 맞는 최적의 경로 등에 사용.

정점(vertex)과 정점 사이를 연결하는 간선(edge)으로 구성. 그래프를 구현하는 두 가지 방법 인접 행렬(adjacent matrix) 기반 그래프 - 정방 행렬을 활용 인접 리스트(adjacent list) 기반 그래프 - 연결 리스트를 활용 인접리스트 기반의 그래프 소스 코드 // ALGraph.h #ifndef ALGraph_h #define ALGraph_h #include "DLinkedList.h" // 정점의 이름을 상수화 enum {A,B,C,D,E,F,G,H,I,J}; typedef struct _ual { int numV; // 정점의 수 int numE; // 간선의 수 List * adjList; //간선의 정보 }ALGraph; // init graph void GraphInit(ALGraph * pg, int nv); ...