그래프(Graph)의 종류, 용어, 구현

그래프란?

• 연결된 원소간의 관계를 표현하는 자료구조
• SNS 친구관계, 수도 배수 시스템, 물질의 분자구조 등에 적합한 자료구조  

 

그래프의 종류

• 무방향 그래프(Undirected Graph)
  • 두 정점을 연결하는 간선에 방향이 없는 그래프
• 방향 그래프(Directed Graph)
  • 간선에 방향이 있는 그래프

출처: algorithmsinsight

 

• 완전 그래프(Complete Graph)
  • 한 정점에서 다른 모든 정점과 연결 된 그래프
  • 최대의 간선 수를 가진 그래프

출처: wikipedia

 

• 부분 그래프
  • 원래의 그래프에서 일부의 정점이나 간선을 제외한 그래프

출처: wikipedia

 

• 가중 그래프(Weight Graph)
  • 간선에 가중치를 할당한 그래프

출처: wikipedia

 

 

그래프 관련 용어

• 인접(adjacent): 그래프의 두 정점이 연결되어 간선이 있을 때, 두 정점을 인접되어 있다고 함.
• 부속(incident): 두 정점이 인접되어 있을 때, 간선은 두 정점에 부속되어 있다고 함.
• 차수(degree): 정점에 부속되어 있는 간선의 수
• 경로(path): 간선을 따라갈 수 있는 길
• 경로 길이(path length): 경로를 구성하는 간선의 수
• 단순 경로(simple path): 모두 다른 정점으로 구성된 경로
• 사이클(cycle): 단순 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로
• DAG(Directed Acyclic Graph): 방향 그래프이면서 사이클이 없는 그래프

 

 

순차 자료구조 방식으로 그래프 구현: 인접 행렬

public class AdjacentMatrix {
    public static void main(String[] args) {
        AdjMatrix am = new AdjMatrix();
        for (int i = 0; i < 5; i++) {
            am.insertVertex(i);
        }
        am.insertEdge(0,2);
        am.insertEdge(0,4);
        am.insertEdge(0,1);
        am.insertEdge(1,2);
        am.insertEdge(1,4);
        am.insertEdge(2,4);
        am.insertEdge(3,2);
        am.insertEdge(3,1);
        am.insertEdge(4,0);
        am.insertEdge(4,1);
        am.printAdjMatrix();
    }
}

class AdjMatrix {
    int matrix[][] = new int[10][10];
    int totalVertex = 0;

    public void insertVertex(int vertex) {
        totalVertex++;
    }

    public void insertEdge(int vertex1, int vertex2) {
        if (vertex1 >= totalVertex || vertex2 >= totalVertex) {
            System.out.println("There is no vertex");
        } else {
            matrix[vertex1][vertex2] = 1;
        }
    }

    public void printAdjMatrix() {
        for (int i = 0; i < totalVertex; i++) {
            System.out.printf("\n\t\t");
            for (int j = 0; j < totalVertex; j++) {
                System.out.printf("%2d", matrix[i][j]);
            }
        }
    }
}

 

연결 자료구조 방식으로 그래프 구현: 인접 리스트

public class AdjacentList {
    public static void main(String[] args) {
        AdjList al = new AdjList();
        for (int i = 0; i < 4; i++) {
            al.insertVertex(i);
        }

        al.insertEdge(0, 3);
        al.insertEdge(0, 2);
        al.insertEdge(0, 1);
        al.insertEdge(1, 3);
        al.insertEdge(1, 0);
        al.insertEdge(2, 1);
        al.insertEdge(2, 0);
        al.insertEdge(3, 1);
        al.insertEdge(3, 1);
        al.insertEdge(4, 3);

        al.printAdjList();
    }
}

class GraphNode {
    int vertex;
    GraphNode link;
}

class AdjList {
    private GraphNode head[] = new GraphNode[10];
    private int totalVertex = 0;

    // vertex 값을 입력하지 않는다.
    // vertex 갯수 카운트용 메소드
    public void insertVertex(int vertex) {
        totalVertex++;
    }

    // vertex2 값을 내림차순으로 입력해야 함.
    public void insertEdge(int vertex1, int vertex2) {
        if (vertex1 >= totalVertex || vertex2 >= totalVertex) {
            System.out.println("Vertex is out of range");
        } else {
            GraphNode gNode = new GraphNode();
            gNode.vertex = vertex2;
            gNode.link = head[vertex1];
            head[vertex1] = gNode;
        }
    }

    public void printAdjList() {
        for (int i = 0; i <= totalVertex; i++) {
            System.out.printf("\n정점 "+ i +"의 인접리스트 ");
            GraphNode gNode = head[i];

            while (gNode != null) {
                System.out.printf("-> " + gNode.vertex);
                gNode = gNode.link;
            }
        }
    }
}

 

 

 

학습 교재

자바로 배우는 쉬운 자료구조 - 이지영 지음

누구나 자료구조와 알고리즘 - 제이 웬그로우 지음