[Data Structure] 그래프(Graph) - 자료 구조

그래프(Graph)

개념: 연결되어 있는 원소 간의 관계를 표현하는 자료구조

버스 노선도나 전철 노선도, 인간 관계 인맥 로드맵, 수도 배수 시스템 등 폭 넓게 쓰임.

그래프는 연결할 객체를 나타내는 정점(Vertex)과 

객체를 연결하는 간선(Edge)의 집합으로 구성

'G = (V,E)' 

V 는 그래프에 있는 정점들의 집합

E 는 정점을 연결하는 간선들의 집합

1. 그래프의 종류

무방향 그래프

무방향 그래프(Undirected Graph)는 두 정점을 연결하는 간선의 방향이 없는 그래프입니다. 

무방향 그래프에서 정점 Vi와 정점 Vj을 연결하는 간선을 (Vi, Vj)로 표현하고

(Vi, Vj)와 (Vj, Vi)는 같은 간선을 나타냅니다.

위 그림에서의 그래프는 무방향 그래프입니다. 

왼쪽 그래프를 G1, 오른쪽 그래프를 G2라 했을 때, 아래와 같이 표현 가능합니다.

V(G1) = {A, B, C}     E(G1) = {(A,B), (A,C), (B,C)}

V(G2) = {A, B, C, D}     E(G2) = {(A,B), (B,C), (B,D), (A,C), (C,D)}

방향 그래프

방향 그래프(Directed Graph)는 간선에 방향이 있는 그래프입니다.

방향 그래프에서 정점 Vi와 정점 Vj를 연결하는 간선 Vi -> Vj를 <Vi, Vj>로 표현하고 화살표로 나타냅니다.

Vi를 Tail, Vj를 Head라고 합니다.

<Vi, Vj> 와 <Vj, Vi>는 다른 간선입니다.

완전 그래프

완전 그래프(Complete Graph) 는 각 정점에서 다른 모든 정점을 연결하여 가능한 최대의 간선 수를 가진 그래프입니다. 

부분 그래프

원래의 그래프에서 일부의 정점이나 간선을 제외하여 만든 그래프를 부분 그래프(Sub Graph)라고 합니다.

가중 그래프

정점을 연결하는 간선에 가중치(Weight)를 할당한 그래프를 가중 그래프(Weight Graph)라고 합니다.

간단하게 구현된 그래프 예제입니다.

인접 행렬로 G1과 G2를 나타냅니다.

 * Graph.java

package ssww;
 
public class Graph {
    public final int MAX_VERTEX = 30;
    
    int n;
    int [][] adjMatrix;
    
    public Graph() {
        n = 0;
        adjMatrix = new int [MAX_VERTEX][MAX_VERTEX];
        
        for (int i = 0; i < MAX_VERTEX; i++) {
            for (int j = 0; j < MAX_VERTEX; j++) {
                adjMatrix[i][j] = 0;
            }
        }
    }
    
    /*
     * 그래프에 정점을 삽입하는 연산
     */
    public void insertVertex(int v) {
        if ((n + 1) > MAX_VERTEX) {
            System.out.println("정점의 갯수 초과!");
            return;
        }
        
        n++;
    }
    
    /*
     * 그래프에 간선 (u, v)를 삽입하는 연
     */
    public void insertEdge(int u, int v) {
        if (u >= n || v >= n) {
            System.out.println("그래프에 없는 정점!");
            return;
        }
        
        adjMatrix[u][v] = 1;
    }
    
    public void printMatrix() {
        for (int i = 0; i < n; i++) {
            System.out.print("\n\t");
            for (int j = 0; j < n; j++) {
                System.out.print(adjMatrix[i][j] + " ");
            }
        }
    }
}
 
 
 

 * GraphMain.java

 
 
 
 
 
 
 
 
 
 
 
 
package ssww;
 
public class GraphMain {
    public static void main(String[] args) {
        Graph g1, g2;
        
        g1 = new Graph();
        g2 = new Graph();
        
        for (int i = 0; i < 4; i++) {
            g1.insertVertex(i);
        }
        
        g1.insertEdge(0, 1);
        g1.insertEdge(0, 3);
        g1.insertEdge(1, 0);
        g1.insertEdge(1, 2);
        g1.insertEdge(1, 3);
        g1.insertEdge(2, 1);
        g1.insertEdge(2, 3);
        g1.insertEdge(3, 0);
        g1.insertEdge(3, 1);
        g1.insertEdge(3, 2);
        
        System.out.println("G1의 인접 행렬");
        g1.printMatrix();
        
        System.out.println("\n");
        for (int i = 0; i < 3; i++) {
            g2.insertVertex(i);
        }
        
        g2.insertEdge(0, 1);
        g2.insertEdge(0, 2);
        g2.insertEdge(1, 0);
        g2.insertEdge(1, 2);
        g2.insertEdge(2, 0);
        g2.insertEdge(2, 1);
 
        System.out.println("G2의 인접 행렬");
        g2.printMatrix();
    }
}
 
 
 

end

tags: Data Structure, 그래프, Graph, 자료 구조, 간선, 정점, Vertex, Edge