9.2   그래프의 기본 연산¶

class GraphAdjMat:
    """인접 행렬로 구현한 무방향 그래프 클래스"""

    def __init__(self, vertices: list[int], edges: list[list[int]]):
        """생성자"""
        # 정점 리스트의 원소는 정점 값을, 인덱스는 정점 인덱스를 나타낸다
        self.vertices: list[int] = []
        # 인접 행렬의 행과 열 인덱스는 정점 인덱스에 해당한다
        self.adj_mat: list[list[int]] = []
        # 정점 추가
        for val in vertices:
            self.add_vertex(val)
        # 간선 추가
        # edges의 원소는 정점 인덱스, 즉 vertices 원소의 인덱스를 나타낸다
        for e in edges:
            self.add_edge(e[0], e[1])

    def size(self) -> int:
        """정점 개수 반환"""
        return len(self.vertices)

    def add_vertex(self, val: int):
        """정점 추가"""
        n = self.size()
        # 정점 리스트에 새 정점의 값을 추가한다
        self.vertices.append(val)
        # 인접 행렬에 행 하나를 추가한다
        new_row = [0] * n
        self.adj_mat.append(new_row)
        # 인접 행렬에 열 하나를 추가한다
        for row in self.adj_mat:
            row.append(0)

    def remove_vertex(self, index: int):
        """정점 삭제"""
        if index >= self.size():
            raise IndexError()
        # 정점 리스트에서 인덱스 index의 정점을 제거한다
        self.vertices.pop(index)
        # 인접 행렬에서 인덱스 index의 행을 삭제한다
        self.adj_mat.pop(index)
        # 인접 행렬에서 인덱스 index의 열을 삭제한다
        for row in self.adj_mat:
            row.pop(index)

    def add_edge(self, i: int, j: int):
        """간선 추가"""
        # 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
        # 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
        if i < 0 or j < 0 or i >= self.size() or j >= self.size() or i == j:
            raise IndexError()
        # 무방향 그래프의 인접 행렬은 주대각선에 대해 대칭이며, (i, j) == (j, i)를 만족한다
        self.adj_mat[i][j] = 1
        self.adj_mat[j][i] = 1

    def remove_edge(self, i: int, j: int):
        """간선 삭제"""
        # 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
        # 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
        if i < 0 or j < 0 or i >= self.size() or j >= self.size() or i == j:
            raise IndexError()
        self.adj_mat[i][j] = 0
        self.adj_mat[j][i] = 0

    def print(self):
        """인접 행렬 출력"""
        print("정점 리스트 =", self.vertices)
        print("인접 행렬 =")
        print_matrix(self.adj_mat)

/* 인접 행렬로 구현한 무방향 그래프 클래스 */
class GraphAdjMat {
    vector<int> vertices;       // 정점 리스트의 원소는 정점 값을, 인덱스는 정점 인덱스를 나타낸다
    vector<vector<int>> adjMat; // 인접 행렬의 행과 열 인덱스는 정점 인덱스에 해당한다

  public:
    /* 생성자 */
    GraphAdjMat(const vector<int> &vertices, const vector<vector<int>> &edges) {
        // 정점 추가
        for (int val : vertices) {
            addVertex(val);
        }
        // 간선 추가
        // edges의 원소는 정점 인덱스, 즉 vertices 원소의 인덱스를 나타낸다
        for (const vector<int> &edge : edges) {
            addEdge(edge[0], edge[1]);
        }
    }

    /* 정점 개수 반환 */
    int size() const {
        return vertices.size();
    }

    /* 정점 추가 */
    void addVertex(int val) {
        int n = size();
        // 정점 리스트에 새 정점의 값을 추가한다
        vertices.push_back(val);
        // 인접 행렬에 행 하나를 추가한다
        adjMat.emplace_back(vector<int>(n, 0));
        // 인접 행렬에 열 하나를 추가한다
        for (vector<int> &row : adjMat) {
            row.push_back(0);
        }
    }

    /* 정점 삭제 */
    void removeVertex(int index) {
        if (index >= size()) {
            throw out_of_range("정점이 존재하지 않는다");
        }
        // 정점 리스트에서 인덱스 index의 정점을 제거한다
        vertices.erase(vertices.begin() + index);
        // 인접 행렬에서 인덱스 index의 행을 삭제한다
        adjMat.erase(adjMat.begin() + index);
        // 인접 행렬에서 인덱스 index의 열을 삭제한다
        for (vector<int> &row : adjMat) {
            row.erase(row.begin() + index);
        }
    }

    /* 간선 추가 */
    // 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
    void addEdge(int i, int j) {
        // 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
        if (i < 0 || j < 0 || i >= size() || j >= size() || i == j) {
            throw out_of_range("정점이 존재하지 않는다");
        }
        // 무방향 그래프의 인접 행렬은 주대각선에 대해 대칭이며, (i, j) == (j, i)를 만족한다
        adjMat[i][j] = 1;
        adjMat[j][i] = 1;
    }

    /* 간선 삭제 */
    // 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
    void removeEdge(int i, int j) {
        // 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
        if (i < 0 || j < 0 || i >= size() || j >= size() || i == j) {
            throw out_of_range("정점이 존재하지 않는다");
        }
        adjMat[i][j] = 0;
        adjMat[j][i] = 0;
    }

    /* 인접 행렬 출력 */
    void print() {
        cout << "정점 리스트 = ";
        printVector(vertices);
        cout << "인접 행렬 =" << endl;
        printVectorMatrix(adjMat);
    }
};

/* 인접 행렬로 구현한 무방향 그래프 클래스 */
class GraphAdjMat {
    List<Integer> vertices; // 정점 리스트의 원소는 정점 값을, 인덱스는 정점 인덱스를 나타낸다
    List<List<Integer>> adjMat; // 인접 행렬의 행과 열 인덱스는 정점 인덱스에 해당한다

    /* 생성자 */
    public GraphAdjMat(int[] vertices, int[][] edges) {
        this.vertices = new ArrayList<>();
        this.adjMat = new ArrayList<>();
        // 정점 추가
        for (int val : vertices) {
            addVertex(val);
        }
        // 간선 추가
        // edges의 원소는 정점 인덱스, 즉 vertices 원소의 인덱스를 나타낸다
        for (int[] e : edges) {
            addEdge(e[0], e[1]);
        }
    }

    /* 정점 개수 반환 */
    public int size() {
        return vertices.size();
    }

    /* 정점 추가 */
    public void addVertex(int val) {
        int n = size();
        // 정점 리스트에 새 정점의 값을 추가한다
        vertices.add(val);
        // 인접 행렬에 행 하나를 추가한다
        List<Integer> newRow = new ArrayList<>(n);
        for (int j = 0; j < n; j++) {
            newRow.add(0);
        }
        adjMat.add(newRow);
        // 인접 행렬에 열 하나를 추가한다
        for (List<Integer> row : adjMat) {
            row.add(0);
        }
    }

    /* 정점 삭제 */
    public void removeVertex(int index) {
        if (index >= size())
            throw new IndexOutOfBoundsException();
        // 정점 리스트에서 인덱스 index의 정점을 제거한다
        vertices.remove(index);
        // 인접 행렬에서 인덱스 index의 행을 삭제한다
        adjMat.remove(index);
        // 인접 행렬에서 인덱스 index의 열을 삭제한다
        for (List<Integer> row : adjMat) {
            row.remove(index);
        }
    }

    /* 간선 추가 */
    // 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
    public void addEdge(int i, int j) {
        // 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
        if (i < 0 || j < 0 || i >= size() || j >= size() || i == j)
            throw new IndexOutOfBoundsException();
        // 무방향 그래프의 인접 행렬은 주대각선에 대해 대칭이며, (i, j) == (j, i)를 만족한다
        adjMat.get(i).set(j, 1);
        adjMat.get(j).set(i, 1);
    }

    /* 간선 삭제 */
    // 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
    public void removeEdge(int i, int j) {
        // 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
        if (i < 0 || j < 0 || i >= size() || j >= size() || i == j)
            throw new IndexOutOfBoundsException();
        adjMat.get(i).set(j, 0);
        adjMat.get(j).set(i, 0);
    }

    /* 인접 행렬 출력 */
    public void print() {
        System.out.print("정점 리스트 = ");
        System.out.println(vertices);
        System.out.println("인접 행렬 =");
        PrintUtil.printMatrix(adjMat);
    }
}

/* 인접 행렬로 구현한 무방향 그래프 클래스 */
class GraphAdjMat {
    List<int> vertices;     // 정점 리스트의 원소는 정점 값을, 인덱스는 정점 인덱스를 나타낸다
    List<List<int>> adjMat; // 인접 행렬의 행과 열 인덱스는 정점 인덱스에 해당한다

    /* 생성자 */
    public GraphAdjMat(int[] vertices, int[][] edges) {
        this.vertices = [];
        this.adjMat = [];
        // 정점 추가
        foreach (int val in vertices) {
            AddVertex(val);
        }
        // 간선 추가
        // edges의 원소는 정점 인덱스, 즉 vertices 원소의 인덱스를 나타낸다
        foreach (int[] e in edges) {
            AddEdge(e[0], e[1]);
        }
    }

    /* 정점 개수 반환 */
    int Size() {
        return vertices.Count;
    }

    /* 정점 추가 */
    public void AddVertex(int val) {
        int n = Size();
        // 정점 리스트에 새 정점의 값을 추가한다
        vertices.Add(val);
        // 인접 행렬에 행 하나를 추가한다
        List<int> newRow = new(n);
        for (int j = 0; j < n; j++) {
            newRow.Add(0);
        }
        adjMat.Add(newRow);
        // 인접 행렬에 열 하나를 추가한다
        foreach (List<int> row in adjMat) {
            row.Add(0);
        }
    }

    /* 정점 삭제 */
    public void RemoveVertex(int index) {
        if (index >= Size())
            throw new IndexOutOfRangeException();
        // 정점 리스트에서 인덱스 index의 정점을 제거한다
        vertices.RemoveAt(index);
        // 인접 행렬에서 인덱스 index의 행을 삭제한다
        adjMat.RemoveAt(index);
        // 인접 행렬에서 인덱스 index의 열을 삭제한다
        foreach (List<int> row in adjMat) {
            row.RemoveAt(index);
        }
    }

    /* 간선 추가 */
    // 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
    public void AddEdge(int i, int j) {
        // 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
        if (i < 0 || j < 0 || i >= Size() || j >= Size() || i == j)
            throw new IndexOutOfRangeException();
        // 무방향 그래프의 인접 행렬은 주대각선에 대해 대칭이며, (i, j) == (j, i)를 만족한다
        adjMat[i][j] = 1;
        adjMat[j][i] = 1;
    }

    /* 간선 삭제 */
    // 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
    public void RemoveEdge(int i, int j) {
        // 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
        if (i < 0 || j < 0 || i >= Size() || j >= Size() || i == j)
            throw new IndexOutOfRangeException();
        adjMat[i][j] = 0;
        adjMat[j][i] = 0;
    }

    /* 인접 행렬 출력 */
    public void Print() {
        Console.Write("정점 리스트 = ");
        PrintUtil.PrintList(vertices);
        Console.WriteLine("인접 행렬 =");
        PrintUtil.PrintMatrix(adjMat);
    }
}

/* 인접 행렬로 구현한 무방향 그래프 클래스 */
type graphAdjMat struct {
    // 정점 리스트의 원소는 정점 값을, 인덱스는 정점 인덱스를 나타낸다
    vertices []int
    // 인접 행렬의 행과 열 인덱스는 정점 인덱스에 해당한다
    adjMat [][]int
}

/* 생성자 */
func newGraphAdjMat(vertices []int, edges [][]int) *graphAdjMat {
    // 정점 추가
    n := len(vertices)
    adjMat := make([][]int, n)
    for i := range adjMat {
        adjMat[i] = make([]int, n)
    }
    // 그래프 초기화
    g := &graphAdjMat{
        vertices: vertices,
        adjMat:   adjMat,
    }
    // 간선 추가
    // edges의 원소는 정점 인덱스, 즉 vertices 원소의 인덱스를 나타낸다
    for i := range edges {
        g.addEdge(edges[i][0], edges[i][1])
    }
    return g
}

/* 정점 개수 반환 */
func (g *graphAdjMat) size() int {
    return len(g.vertices)
}

/* 정점 추가 */
func (g *graphAdjMat) addVertex(val int) {
    n := g.size()
    // 정점 리스트에 새 정점의 값을 추가한다
    g.vertices = append(g.vertices, val)
    // 인접 행렬에 행 하나를 추가한다
    newRow := make([]int, n)
    g.adjMat = append(g.adjMat, newRow)
    // 인접 행렬에 열 하나를 추가한다
    for i := range g.adjMat {
        g.adjMat[i] = append(g.adjMat[i], 0)
    }
}

/* 정점 삭제 */
func (g *graphAdjMat) removeVertex(index int) {
    if index >= g.size() {
        return
    }
    // 정점 리스트에서 인덱스 index의 정점을 제거한다
    g.vertices = append(g.vertices[:index], g.vertices[index+1:]...)
    // 인접 행렬에서 인덱스 index의 행을 삭제한다
    g.adjMat = append(g.adjMat[:index], g.adjMat[index+1:]...)
    // 인접 행렬에서 인덱스 index의 열을 삭제한다
    for i := range g.adjMat {
        g.adjMat[i] = append(g.adjMat[i][:index], g.adjMat[i][index+1:]...)
    }
}

/* 간선 추가 */
// 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
func (g *graphAdjMat) addEdge(i, j int) {
    // 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
    if i < 0 || j < 0 || i >= g.size() || j >= g.size() || i == j {
        fmt.Errorf("%s", "인덱스가 범위를 벗어났다")
    }
    // 무방향 그래프의 인접 행렬은 주대각선에 대해 대칭이며, (i, j) == (j, i)를 만족한다
    g.adjMat[i][j] = 1
    g.adjMat[j][i] = 1
}

/* 간선 삭제 */
// 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
func (g *graphAdjMat) removeEdge(i, j int) {
    // 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
    if i < 0 || j < 0 || i >= g.size() || j >= g.size() || i == j {
        fmt.Errorf("%s", "인덱스가 범위를 벗어났다")
    }
    g.adjMat[i][j] = 0
    g.adjMat[j][i] = 0
}

/* 인접 행렬 출력 */
func (g *graphAdjMat) print() {
    fmt.Printf("\t정점 리스트 = %v\n", g.vertices)
    fmt.Printf("\t인접 행렬 = \n")
    for i := range g.adjMat {
        fmt.Printf("\t\t\t%v\n", g.adjMat[i])
    }
}

/* 인접 행렬로 구현한 무방향 그래프 클래스 */
class GraphAdjMat {
    private var vertices: [Int] // 정점 리스트의 원소는 정점 값을, 인덱스는 정점 인덱스를 나타낸다
    private var adjMat: [[Int]] // 인접 행렬의 행과 열 인덱스는 정점 인덱스에 해당한다

    /* 생성자 */
    init(vertices: [Int], edges: [[Int]]) {
        self.vertices = []
        adjMat = []
        // 정점 추가
        for val in vertices {
            addVertex(val: val)
        }
        // 간선 추가
        // edges의 원소는 정점 인덱스, 즉 vertices 원소의 인덱스를 나타낸다
        for e in edges {
            addEdge(i: e[0], j: e[1])
        }
    }

    /* 정점 개수 반환 */
    func size() -> Int {
        vertices.count
    }

    /* 정점 추가 */
    func addVertex(val: Int) {
        let n = size()
        // 정점 리스트에 새 정점의 값을 추가한다
        vertices.append(val)
        // 인접 행렬에 행 하나를 추가한다
        let newRow = Array(repeating: 0, count: n)
        adjMat.append(newRow)
        // 인접 행렬에 열 하나를 추가한다
        for i in adjMat.indices {
            adjMat[i].append(0)
        }
    }

    /* 정점 삭제 */
    func removeVertex(index: Int) {
        if index >= size() {
            fatalError("범위를 벗어남")
        }
        // 정점 리스트에서 인덱스 index의 정점을 제거한다
        vertices.remove(at: index)
        // 인접 행렬에서 인덱스 index의 행을 삭제한다
        adjMat.remove(at: index)
        // 인접 행렬에서 인덱스 index의 열을 삭제한다
        for i in adjMat.indices {
            adjMat[i].remove(at: index)
        }
    }

    /* 간선 추가 */
    // 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
    func addEdge(i: Int, j: Int) {
        // 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
        if i < 0 || j < 0 || i >= size() || j >= size() || i == j {
            fatalError("범위를 벗어남")
        }
        // 무방향 그래프의 인접 행렬은 주대각선에 대해 대칭이며, (i, j) == (j, i)를 만족한다
        adjMat[i][j] = 1
        adjMat[j][i] = 1
    }

    /* 간선 삭제 */
    // 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
    func removeEdge(i: Int, j: Int) {
        // 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
        if i < 0 || j < 0 || i >= size() || j >= size() || i == j {
            fatalError("범위를 벗어남")
        }
        adjMat[i][j] = 0
        adjMat[j][i] = 0
    }

    /* 인접 행렬 출력 */
    func print() {
        Swift.print("정점 리스트 = ", terminator: "")
        Swift.print(vertices)
        Swift.print("인접 행렬 =")
        PrintUtil.printMatrix(matrix: adjMat)
    }
}

/* 인접 행렬로 구현한 무방향 그래프 클래스 */
class GraphAdjMat {
    vertices; // 정점 리스트의 원소는 정점 값을, 인덱스는 정점 인덱스를 나타낸다
    adjMat; // 인접 행렬의 행과 열 인덱스는 정점 인덱스에 해당한다

    /* 생성자 */
    constructor(vertices, edges) {
        this.vertices = [];
        this.adjMat = [];
        // 정점 추가
        for (const val of vertices) {
            this.addVertex(val);
        }
        // 간선 추가
        // edges의 원소는 정점 인덱스, 즉 vertices 원소의 인덱스를 나타낸다
        for (const e of edges) {
            this.addEdge(e[0], e[1]);
        }
    }

    /* 정점 개수 반환 */
    size() {
        return this.vertices.length;
    }

    /* 정점 추가 */
    addVertex(val) {
        const n = this.size();
        // 정점 리스트에 새 정점의 값을 추가한다
        this.vertices.push(val);
        // 인접 행렬에 행 하나를 추가한다
        const newRow = [];
        for (let j = 0; j < n; j++) {
            newRow.push(0);
        }
        this.adjMat.push(newRow);
        // 인접 행렬에 열 하나를 추가한다
        for (const row of this.adjMat) {
            row.push(0);
        }
    }

    /* 정점 삭제 */
    removeVertex(index) {
        if (index >= this.size()) {
            throw new RangeError('인덱스가 범위를 벗어났다');
        }
        // 정점 리스트에서 인덱스 index의 정점을 제거한다
        this.vertices.splice(index, 1);

        // 인접 행렬에서 인덱스 index의 행을 삭제한다
        this.adjMat.splice(index, 1);
        // 인접 행렬에서 인덱스 index의 열을 삭제한다
        for (const row of this.adjMat) {
            row.splice(index, 1);
        }
    }

    /* 간선 추가 */
    // 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
    addEdge(i, j) {
        // 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
        if (i < 0 || j < 0 || i >= this.size() || j >= this.size() || i === j) {
            throw new RangeError('인덱스가 범위를 벗어났다');
        }
        // 무방향 그래프의 인접 행렬은 주대각선을 기준으로 대칭이므로 (i, j) === (j, i)를 만족한다
        this.adjMat[i][j] = 1;
        this.adjMat[j][i] = 1;
    }

    /* 간선 삭제 */
    // 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
    removeEdge(i, j) {
        // 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
        if (i < 0 || j < 0 || i >= this.size() || j >= this.size() || i === j) {
            throw new RangeError('인덱스가 범위를 벗어났다');
        }
        this.adjMat[i][j] = 0;
        this.adjMat[j][i] = 0;
    }

    /* 인접 행렬 출력 */
    print() {
        console.log('정점 리스트 = ', this.vertices);
        console.log('인접 행렬 =', this.adjMat);
    }
}

/* 인접 행렬로 구현한 무방향 그래프 클래스 */
class GraphAdjMat {
    vertices: number[]; // 정점 리스트의 원소는 정점 값을, 인덱스는 정점 인덱스를 나타낸다
    adjMat: number[][]; // 인접 행렬의 행과 열 인덱스는 정점 인덱스에 해당한다

    /* 생성자 */
    constructor(vertices: number[], edges: number[][]) {
        this.vertices = [];
        this.adjMat = [];
        // 정점 추가
        for (const val of vertices) {
            this.addVertex(val);
        }
        // 간선 추가
        // edges의 원소는 정점 인덱스, 즉 vertices 원소의 인덱스를 나타낸다
        for (const e of edges) {
            this.addEdge(e[0], e[1]);
        }
    }

    /* 정점 개수 반환 */
    size(): number {
        return this.vertices.length;
    }

    /* 정점 추가 */
    addVertex(val: number): void {
        const n: number = this.size();
        // 정점 리스트에 새 정점의 값을 추가한다
        this.vertices.push(val);
        // 인접 행렬에 행 하나를 추가한다
        const newRow: number[] = [];
        for (let j: number = 0; j < n; j++) {
            newRow.push(0);
        }
        this.adjMat.push(newRow);
        // 인접 행렬에 열 하나를 추가한다
        for (const row of this.adjMat) {
            row.push(0);
        }
    }

    /* 정점 삭제 */
    removeVertex(index: number): void {
        if (index >= this.size()) {
            throw new RangeError('인덱스가 범위를 벗어났다');
        }
        // 정점 리스트에서 인덱스 index의 정점을 제거한다
        this.vertices.splice(index, 1);

        // 인접 행렬에서 인덱스 index의 행을 삭제한다
        this.adjMat.splice(index, 1);
        // 인접 행렬에서 인덱스 index의 열을 삭제한다
        for (const row of this.adjMat) {
            row.splice(index, 1);
        }
    }

    /* 간선 추가 */
    // 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
    addEdge(i: number, j: number): void {
        // 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
        if (i < 0 || j < 0 || i >= this.size() || j >= this.size() || i === j) {
            throw new RangeError('인덱스가 범위를 벗어났다');
        }
        // 무방향 그래프의 인접 행렬은 주대각선을 기준으로 대칭이므로 (i, j) === (j, i)를 만족한다
        this.adjMat[i][j] = 1;
        this.adjMat[j][i] = 1;
    }

    /* 간선 삭제 */
    // 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
    removeEdge(i: number, j: number): void {
        // 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
        if (i < 0 || j < 0 || i >= this.size() || j >= this.size() || i === j) {
            throw new RangeError('인덱스가 범위를 벗어났다');
        }
        this.adjMat[i][j] = 0;
        this.adjMat[j][i] = 0;
    }

    /* 인접 행렬 출력 */
    print(): void {
        console.log('정점 리스트 = ', this.vertices);
        console.log('인접 행렬 =', this.adjMat);
    }
}

/* 인접 행렬로 구현한 무방향 그래프 클래스 */
class GraphAdjMat {
  List<int> vertices = []; // 정점 원소는 정점 값을, 인덱스는 정점 인덱스를 나타낸다
  List<List<int>> adjMat = []; //인접 행렬의 행과 열 인덱스는 정점 인덱스에 해당한다

  /* 생성자 */
  GraphAdjMat(List<int> vertices, List<List<int>> edges) {
    this.vertices = [];
    this.adjMat = [];
    // 정점 추가
    for (int val in vertices) {
      addVertex(val);
    }
    // 간선 추가
    // edges의 원소는 정점 인덱스, 즉 vertices 원소의 인덱스를 나타낸다
    for (List<int> e in edges) {
      addEdge(e[0], e[1]);
    }
  }

  /* 정점 개수 반환 */
  int size() {
    return vertices.length;
  }

  /* 정점 추가 */
  void addVertex(int val) {
    int n = size();
    // 정점 리스트에 새 정점의 값을 추가한다
    vertices.add(val);
    // 인접 행렬에 행 하나를 추가한다
    List<int> newRow = List.filled(n, 0, growable: true);
    adjMat.add(newRow);
    // 인접 행렬에 열 하나를 추가한다
    for (List<int> row in adjMat) {
      row.add(0);
    }
  }

  /* 정점 삭제 */
  void removeVertex(int index) {
    if (index >= size()) {
      throw IndexError;
    }
    // 정점 리스트에서 인덱스 index의 정점을 제거한다
    vertices.removeAt(index);
    // 인접 행렬에서 인덱스 index의 행을 삭제한다
    adjMat.removeAt(index);
    // 인접 행렬에서 인덱스 index의 열을 삭제한다
    for (List<int> row in adjMat) {
      row.removeAt(index);
    }
  }

  /* 간선 추가 */
  // 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
  void addEdge(int i, int j) {
    // 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
    if (i < 0 || j < 0 || i >= size() || j >= size() || i == j) {
      throw IndexError;
    }
    // 무방향 그래프의 인접 행렬은 주대각선에 대해 대칭이며, (i, j) == (j, i)를 만족한다
    adjMat[i][j] = 1;
    adjMat[j][i] = 1;
  }

  /* 간선 삭제 */
  // 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
  void removeEdge(int i, int j) {
    // 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
    if (i < 0 || j < 0 || i >= size() || j >= size() || i == j) {
      throw IndexError;
    }
    adjMat[i][j] = 0;
    adjMat[j][i] = 0;
  }

  /* 인접 행렬 출력 */
  void printAdjMat() {
    print("정점 리스트 = $vertices");
    print("인접 행렬 = ");
    printMatrix(adjMat);
  }
}

/* 인접 행렬로 구현한 무방향 그래프 자료형 */
pub struct GraphAdjMat {
    // 정점 리스트의 원소는 정점 값을, 인덱스는 정점 인덱스를 나타낸다
    pub vertices: Vec<i32>,
    // 인접 행렬의 행과 열 인덱스는 정점 인덱스에 해당한다
    pub adj_mat: Vec<Vec<i32>>,
}

impl GraphAdjMat {
    /* 생성자 */
    pub fn new(vertices: Vec<i32>, edges: Vec<[usize; 2]>) -> Self {
        let mut graph = GraphAdjMat {
            vertices: vec![],
            adj_mat: vec![],
        };
        // 정점 추가
        for val in vertices {
            graph.add_vertex(val);
        }
        // 간선 추가
        // edges의 원소는 정점 인덱스, 즉 vertices 원소의 인덱스를 나타낸다
        for edge in edges {
            graph.add_edge(edge[0], edge[1])
        }

        graph
    }

    /* 정점 개수 반환 */
    pub fn size(&self) -> usize {
        self.vertices.len()
    }

    /* 정점 추가 */
    pub fn add_vertex(&mut self, val: i32) {
        let n = self.size();
        // 정점 리스트에 새 정점의 값을 추가한다
        self.vertices.push(val);
        // 인접 행렬에 행 하나를 추가한다
        self.adj_mat.push(vec![0; n]);
        // 인접 행렬에 열 하나를 추가한다
        for row in self.adj_mat.iter_mut() {
            row.push(0);
        }
    }

    /* 정점 삭제 */
    pub fn remove_vertex(&mut self, index: usize) {
        if index >= self.size() {
            panic!("인덱스 오류")
        }
        // 정점 리스트에서 인덱스 index의 정점을 제거한다
        self.vertices.remove(index);
        // 인접 행렬에서 인덱스 index의 행을 삭제한다
        self.adj_mat.remove(index);
        // 인접 행렬에서 인덱스 index의 열을 삭제한다
        for row in self.adj_mat.iter_mut() {
            row.remove(index);
        }
    }

    /* 간선 추가 */
    pub fn add_edge(&mut self, i: usize, j: usize) {
        // 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
        // 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
        if i >= self.size() || j >= self.size() || i == j {
            panic!("인덱스 오류")
        }
        // 무방향 그래프의 인접 행렬은 주대각선에 대해 대칭이며, (i, j) == (j, i)를 만족한다
        self.adj_mat[i][j] = 1;
        self.adj_mat[j][i] = 1;
    }

    /* 간선 삭제 */
    // 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
    pub fn remove_edge(&mut self, i: usize, j: usize) {
        // 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
        // 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
        if i >= self.size() || j >= self.size() || i == j {
            panic!("인덱스 오류")
        }
        self.adj_mat[i][j] = 0;
        self.adj_mat[j][i] = 0;
    }

    /* 인접 행렬 출력 */
    pub fn print(&self) {
        println!("정점 리스트 = {:?}", self.vertices);
        println!("인접 행렬 =");
        println!("[");
        for row in &self.adj_mat {
            println!("  {:?},", row);
        }
        println!("]")
    }
}

/* 인접 행렬로 구현한 무방향 그래프 구조체 */
typedef struct {
    int vertices[MAX_SIZE];
    int adjMat[MAX_SIZE][MAX_SIZE];
    int size;
} GraphAdjMat;

/* 생성자 */
GraphAdjMat *newGraphAdjMat() {
    GraphAdjMat *graph = (GraphAdjMat *)malloc(sizeof(GraphAdjMat));
    graph->size = 0;
    for (int i = 0; i < MAX_SIZE; i++) {
        for (int j = 0; j < MAX_SIZE; j++) {
            graph->adjMat[i][j] = 0;
        }
    }
    return graph;
}

/* 소멸자 */
void delGraphAdjMat(GraphAdjMat *graph) {
    free(graph);
}

/* 정점 추가 */
void addVertex(GraphAdjMat *graph, int val) {
    if (graph->size == MAX_SIZE) {
        fprintf(stderr, "그래프의 정점 개수가 최댓값에 도달했다\n");
        return;
    }
    // n번째 정점을 추가하고 n번째 행과 열을 0으로 설정한다
    int n = graph->size;
    graph->vertices[n] = val;
    for (int i = 0; i <= n; i++) {
        graph->adjMat[n][i] = graph->adjMat[i][n] = 0;
    }
    graph->size++;
}

/* 정점 삭제 */
void removeVertex(GraphAdjMat *graph, int index) {
    if (index < 0 || index >= graph->size) {
        fprintf(stderr, "정점 인덱스가 범위를 벗어났다\n");
        return;
    }
    // 정점 리스트에서 인덱스 index의 정점을 제거한다
    for (int i = index; i < graph->size - 1; i++) {
        graph->vertices[i] = graph->vertices[i + 1];
    }
    // 인접 행렬에서 인덱스 index의 행을 삭제한다
    for (int i = index; i < graph->size - 1; i++) {
        for (int j = 0; j < graph->size; j++) {
            graph->adjMat[i][j] = graph->adjMat[i + 1][j];
        }
    }
    // 인접 행렬에서 인덱스 index의 열을 삭제한다
    for (int i = 0; i < graph->size; i++) {
        for (int j = index; j < graph->size - 1; j++) {
            graph->adjMat[i][j] = graph->adjMat[i][j + 1];
        }
    }
    graph->size--;
}

/* 간선 추가 */
// 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
void addEdge(GraphAdjMat *graph, int i, int j) {
    if (i < 0 || j < 0 || i >= graph->size || j >= graph->size || i == j) {
        fprintf(stderr, "간선 인덱스가 범위를 벗어나거나 서로 같다\n");
        return;
    }
    graph->adjMat[i][j] = 1;
    graph->adjMat[j][i] = 1;
}

/* 간선 삭제 */
// 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
void removeEdge(GraphAdjMat *graph, int i, int j) {
    if (i < 0 || j < 0 || i >= graph->size || j >= graph->size || i == j) {
        fprintf(stderr, "간선 인덱스가 범위를 벗어나거나 서로 같다\n");
        return;
    }
    graph->adjMat[i][j] = 0;
    graph->adjMat[j][i] = 0;
}

/* 인접 행렬 출력 */
void printGraphAdjMat(GraphAdjMat *graph) {
    printf("정점 리스트 = ");
    printArray(graph->vertices, graph->size);
    printf("인접 행렬 =\n");
    for (int i = 0; i < graph->size; i++) {
        printArray(graph->adjMat[i], graph->size);
    }
}

/* 인접 행렬로 구현한 무방향 그래프 클래스 */
class GraphAdjMat(vertices: IntArray, edges: Array<IntArray>) {
    val vertices = mutableListOf<Int>() // 정점 리스트의 원소는 정점 값을, 인덱스는 정점 인덱스를 나타낸다
    val adjMat = mutableListOf<MutableList<Int>>() // 인접 행렬의 행과 열 인덱스는 정점 인덱스에 해당한다

    /* 생성자 */
    init {
        // 정점 추가
        for (vertex in vertices) {
            addVertex(vertex)
        }
        // 간선 추가
        // edges의 원소는 정점 인덱스, 즉 vertices 원소의 인덱스를 나타낸다
        for (edge in edges) {
            addEdge(edge[0], edge[1])
        }
    }

    /* 정점 개수 반환 */
    fun size(): Int {
        return vertices.size
    }

    /* 정점 추가 */
    fun addVertex(_val: Int) {
        val n = size()
        // 정점 리스트에 새 정점의 값을 추가한다
        vertices.add(_val)
        // 인접 행렬에 행 하나를 추가한다
        val newRow = mutableListOf<Int>()
        for (j in 0..<n) {
            newRow.add(0)
        }
        adjMat.add(newRow)
        // 인접 행렬에 열 하나를 추가한다
        for (row in adjMat) {
            row.add(0)
        }
    }

    /* 정점 삭제 */
    fun removeVertex(index: Int) {
        if (index >= size())
            throw IndexOutOfBoundsException()
        // 정점 리스트에서 인덱스 index의 정점을 제거한다
        vertices.removeAt(index)
        // 인접 행렬에서 인덱스 index의 행을 삭제한다
        adjMat.removeAt(index)
        // 인접 행렬에서 인덱스 index의 열을 삭제한다
        for (row in adjMat) {
            row.removeAt(index)
        }
    }

    /* 간선 추가 */
    // 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
    fun addEdge(i: Int, j: Int) {
        // 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
        if (i < 0 || j < 0 || i >= size() || j >= size() || i == j)
            throw IndexOutOfBoundsException()
        // 무방향 그래프의 인접 행렬은 주대각선에 대해 대칭이며, (i, j) == (j, i)를 만족한다
        adjMat[i][j] = 1
        adjMat[j][i] = 1
    }

    /* 간선 삭제 */
    // 매개변수 i, j는 vertices 원소의 인덱스에 해당한다
    fun removeEdge(i: Int, j: Int) {
        // 인덱스가 범위를 벗어나거나 서로 같은 경우를 처리한다
        if (i < 0 || j < 0 || i >= size() || j >= size() || i == j)
            throw IndexOutOfBoundsException()
        adjMat[i][j] = 0
        adjMat[j][i] = 0
    }

    /* 인접 행렬 출력 */
    fun print() {
        print("정점 리스트 = ")
        println(vertices)
        println("인접 행렬 =")
        printMatrix(adjMat)
    }
}