Graph

그래프에서
한 노드를 vertex라고 부름
연결을 connection 또는 edge라고 부름
하나의 vertex는 여러 vertex와 연결될 수 있다.
양방향 연결되어 있다.

 
adjacency Matrix
양방향으로 연결되어 있는 경우에만 대조되는 모습을 보인다.
 

 
adjacency List
리스트로 표현하면

{
"A"= ["B","E"],
"B"= ["A","C"],
"C"= ["B","D"],
"D"= ["C","E"],
"E"= ["A","D"]
}

 

Big O

add vertex

• adjacency Matrix방법으로 표기할 경우

하나의 vertex를 추가하려면 원래 있는 vertex의 수 + 1의 제곱만큼의 칸을 만들어야 한다.
⇒ 0(n^2)

• 반면 adjacency list

의 방법의 경우 빈 리스트를 추가하면 되기 때문에 더 효율적이다.
⇒ 0(1)

add edge

값만 바꿔주면 되므로 둘 다 0(1)

remove edge

• adjacency Matrix

값만 바꾸면 되므로
⇒ 0(1)

• 반면 adjacency list

B와 F vertex사이의 edge를 없애려면 서로의 리스트값에서 서로를 빼면 되는데
먼저 B리스트에서 F를 뺀다. 그러기 위해 B를 찾는 과정에서 반복문을 돌며 찾아야 하기 때문에
⇒ 0(n)

remove vertext

remove f

• adjacency list

F를 제거하고, 다른 리스트를 반복문을 돌면서 F가 있는지 확인해야 한다.
⇒ 0(n)

• adjacency matrix

F에 해당하는 행렬을 지우고 행렬을 다시 쓴다
⇒ 0(n^2)
행렬보다 리스트가 보통 더 효율적인 이유는 리스트는 연결되는 vertex만 각 vertex의 리스트에 저장하지만 행렬은 연결되지 않는 vertex를 의미하는 0의 값도 저장해야 하기 때문.
 
 
 

사진참고

code

add vertex

private HashMap<String, ArrayList<String>> adjList = new HashMap<>();

graph adjacency list방식은 는 해시맵으로 구현한다.
키 = vertex 값
value = edge값

public boolean addVertex(String vertex) {
        if (adjList.get(vertex) == null) {
            adjList.put(vertex, new ArrayList<String>());
            return true;
        }
        return false;
    }

그래프에서는 중복을 허용하지 않는다.
기존의 그래프에서 추가하려는 값의 키를 가진 hash map 요소(?)가 없다면 추가한다.
 
 
 

add edge

public boolean addEdge(String vertex1, String vertex2) {
        if (adjList.get(vertex1) != null && adjList.get(vertex2) != null) {
            adjList.get(vertex1).add(vertex2);
            adjList.get(vertex2).add(vertex1);
            return true;
        }
        return false;
    }

연결할 vertex 2개를 파라미터값으로 받는다.
파라미터로 받은 값의 vertex가 존재할 경우에 로직을 실행한다.
각 vertex에 해당하는 값인 리스트를 받아 그 리스트에 서로를 추가한다.
 
 
 
 

remove edge

public boolean removeEdge(String vertex1, String vertex2) {
        if (adjList.get(vertex1) != null && adjList.get(vertex2) != null) {
            adjList.get(vertex1).remove(vertex2);
            adjList.get(vertex2).remove(vertex1);
            return true;
        }
        return false;
    }

없앨 edge의 양 끝 vertex 2개를 파라미터로 받는다.
파라미터로 받은 값의 vertex가 존재할 경우에 로직을 실행한다.
각 vertex의 리스트를 받아서 그 리스트에서 서로를 없앤다.
 
 
 
 

remove vertex

public boolean removeVertex(String vertex) {
        if (adjList.get(vertex) == null) return false;
        for (String otherVertex : adjList.get(vertex)) {
            adjList.get(otherVertex).remove(vertex);
        }
        adjList.remove(vertex);
        return true;
    }

edge를 먼저 없애고 vertex를 없애야 한다.
그러기 위해 먼저 삭제할 vertex의 리스트를 찾는다. 왜냐하면 삭제할 vertex의 리스트 안에 이 vertex와 연결된 vertex들이 들어있기 때문.
삭제할 vertex의 리스트를 반복문을 돌면서 연결된 vertex의 리스트 안에 있는 삭제할 vertex의 값을 없앤다.
마지막으로 삭제할 vertex를 그래프 리스트에 서 삭제해 준다.