CS/자료구조 & 알고리즘
[자료구조] PHP로 무방향 그래프 구현
초오오이
2025. 6. 6. 20:52
인접 리스트로 무방향 그래프 구현
class Graph {
/**
* @var array 인접 리스트를 저장할 연관 배열
* 예: ['A' => ['B', 'C'], 'B' => ['A']]
*/
private array $adjacencyList = [];
/**
* 그래프에 새로운 정점(Vertex)을 추가
* @param string $vertex
* @return void
*/
public function addVertex(string $vertex): void {
if (!isset($this->adjacencyList[$vertex])) {
$this->adjacencyList[$vertex] = []; // 추후 다른 점들과 연결될 수 있는 공간
}
}
/**
* 두 정점 사이에 무방향 간선(Edge)을 추가
* @param string $vertex1
* @param string $vertex2
* @return void
*/
public function addEdge(string $vertex1, string $vertex2): void {
// 두 정점이 모두 존재하는지 확인
if (isset($this->adjacencyList[$vertex1]) && isset($this->adjacencyList[$vertex2])) {
// vertex1의 인접 리스트에 vertex2 추가
if (!in_array($vertex2, $this->adjacencyList[$vertex1])) {
$this->adjacencyList[$vertex1][] = $vertex2;
}
// vertex2의 인접 리스트에 vertex1 추가
if (!in_array($vertex1, $this->adjacencyList[$vertex2])) {
$this->adjacencyList[$vertex2][] = $vertex1;
}
}
}
/**
* 그래프의 구조(인접 리스트)를 출력
* @return void
*/
public function display(): void {
foreach ($this->adjacencyList as $vertex => $edges) {
echo $vertex . " -> [ " . implode(", ", $edges) . " ]\n";
}
}
}
출력 예시
// 1. 그래프 객체 생성
$graph = new Graph();
// 2. 정점 추가
$vertices = ['A', 'B', 'C', 'D', 'E'];
foreach ($vertices as $vertex) {
$graph->addVertex($vertex);
}
// 3. 간선 추가 (무방향)
$graph->addEdge('A', 'B');
$graph->addEdge('A', 'C');
$graph->addEdge('B', 'D');
$graph->addEdge('C', 'E');
$graph->addEdge('D', 'E');
// 4. 그래프 구조 출력
$graph->display();
// A -> [ B, C ]
// B -> [ A, D ]
// C -> [ A, E ]
// D -> [ B, E ]
// E -> [ C, D ]
깊이 우선 탐색
/**
* 깊이 우선 탐색 (DFS)
* @param string $startVertex 시작 정점
* @return array $result 탐색 순서대로 정점들이 담긴 배열
*/
public function dfs(string $startVertex): array {
$result = [];
$visited = []; // 방문한 노드 기록
$this->_dfsRecursive($startVertex, $visited, $result);
return $result;
}
private function _dfsRecursive(string $vertex, array &$visited, array &$result): void {
// 현재 노드를 방문 처리하고 결과에 추가
$visited[$vertex] = true;
$result[] = $vertex;
// 현재 정점의 모든 인접 정점을 확인
foreach ($this->adjacencyList[$vertex] as $neighbor) {
// 아직 방문하지 않은 인접 정점이라면 재귀 호출
if (!isset($visited[$neighbor])) {
$this->_dfsRecursive($neighbor, $visited, $result);
}
}
}
너비 우선 탐색
/**
* 너비 우선 탐색 (BFS) - 큐 방식
* @param string $startVertex 시작 정점
* @return array $result 탐색 순서대로 정점들이 담긴 배열
*/
public function bfs(string $startVertex): array {
$visited = []; // 방문할 정점 기록
$queue = [$startVertex]; // 배열을 큐처럼 사용
$visited[] = $startVertex; // 시작 정점 방문 처리
$result = [];
while (!empty($queue)) {
// 리스트의 첫 번째 요소를 꺼냄
$currentVertex = array_shift($queue);
$result[] = $currentVertex;
// 인접한 정점들을 큐에 추가
foreach ($this->adjacencyList[$currentVertex] as $neighbor) {
if (!in_array($neighbor, $visited)) {
$visited[] = $neighbor; // 방문 기록
array_push($queue, $neighbor); // 큐의 끝에 추가해 나중에 방문할 수 있도록 함
}
}
}
return $result;
}