[Algorithm] Graph

Graph

그래프의 개념을 알아 보고 구현을 해본다.

 

 

 

Graph 의 구조

• Graph 는 Vertex(Node) 와 Edge 를 가지는 자료 구조이다.
• Vertex: 정점
• Edge: 간선
• G(V,E) : 그래프는 정점과 간선으로 이루어져 있다.
• Adjacent Vertex: 인접정점 으로 하나의 정점과 연결되어 있는 정점을 말한다.
• 정점 v1 과 V2 가 Edge 로 연결 되어 있다고 하면 다음과 같다. 

 

 

 

 

Graph 의 종류

• 무방향 그래프
• 방향 그래프
• 가중치 그래프

 

 

무방향 그래프

무방향은 말 그대로 방향이 없는 그래프이다.

 

위 그래프를 정점과 노드로 표현 하면 다음과 같다.

• V = {V1, V2, V3, V4, V5}
• E = {(V1, V2), (V1,V3), (V2,V4), (V2,V5), (V3,V4), (V4,V5)}
• 특징
  - (V1, V2) == (V2,V1) 은 같다 방향이 없기 때문이다.

 

 

 

방향 그래프

방향을 가지는 그래프이다.

• 특징
  - (V1, V2) != (V2, V1) 은 다르다 방향을 가지기 때문에 동일 할 수 없다.

 

 

가중치 그래프

Edge 에 가중치가 있는 그래프이이다.

• 특징
  - 지나가는 경로시 최단거리등을 가중치로 구할수 있다.

 

 

 

무방향 그래프의 표현

그래프의 표현은 인접행렬과 인접리스트로 구현 할 수 있다.

• 인접행렬 (adjacency matrix) 
• 인접리스트(adjacency list)

 

인접행렬

• 행렬로 그래프를 표현한다. 
• 저장공간: n x n
• 인접한 모든 노드 찾기: O(n) 시간
• 엣지 존재 여부: O(1)

 

 

 

인접리스트

• 리스트로 그래프를 표현한다.
• 저장공간: n+m
• 인접한 모든 노드 찾기: O(degree(v)) 시간
• 엣지 존재 여부: O(degree(u))

 

 

 

방향 그래프의 표현

• 인접행렬은 비대칭을 가진다.
• 인접리스트는 M 개의 노드를 가진다.

 

 

 

 

무방향, 방향 그래프 구현

그래프의 자료구조는 인접리스트를 택했다.

인접행렬 은 예제가 많고 구현하기 쉽기 때문이다.

package com.company;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class GraphListExample {
    private ArrayList<ArrayList<Integer>> mListGraph;

    public GraphListExample(int graphSize)
    {
        mListGraph= new ArrayList<ArrayList<Integer>>();
        for(int i = 0; i < graphSize+1; i++) {
            mListGraph.add(new ArrayList<Integer>());
        }
    }

    public void addVertex(int v1, int v2)
    {
        mListGraph.get(v1).add(v2);
        mListGraph.get(v2).add(v1);
    }

    public void addDirectVertex(int v1, int v2)
    {
        mListGraph.get(v1).add(v2);
    }

    public ArrayList<Integer> getVertex(int v1) {
        return mListGraph.get(v1);
    }

    public  ArrayList<ArrayList<Integer>> getGraph() {
        return mListGraph;
    }

    public void printGraph() {
        for (int i = 1; i < mListGraph.size(); i++) {
            System.out.print(i);
            for (int j = 0; j <mListGraph.get(i).size(); j++) {
                System.out.print(" -> " + mListGraph.get(i).get(j));
            }
            System.out.println("");

        }
    }

    public static void main(String[] args) {
	// write your code here
        int graphSize = 5;
        GraphListExample listGraph = new GraphListExample(graphSize);
        listGraph.addVertex(1,2);
        listGraph.addVertex(1,3);
        listGraph.addVertex(2,5);
        listGraph.addVertex(2,4);
        listGraph.addVertex(3,4);
        listGraph.addVertex(4,5);
        listGraph.printGraph();
    }
}

 

 

결과

 

 

 

전체코드

 

구현코드:

https://github.com/rnrl1215/algorithm-base/blob/master/src/main/java/algorithm/graph/ListGraphExample.java

 

테스트 코드:

https://github.com/rnrl1215/algorithm-base/blob/master/src/test/java/GraphTest.java