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;
}