그래프 표현 방식과 탐색 방법

 

그래프(Graph)의 종류

• 무방향 그래프
• 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다.정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다. (A, B)는 (B, A) 동일
• 방향 그래프<A, B>는 <B, A>는 다름
• 간선에 방향성이 존재하는 그래프, A -> B로만 갈 수 있는 간선은 <A, B>로 표시한다.
• 가중치 그래프
• 간선에 비용이나 가중치가 할당된 그래프로 ‘네트워크(Network)’ 라고도 한다.

그래프 표현 방법

• 인접 행렬먼저, 인접행렬(adjacency matrix) 방법이 있다. 인접 행렬은 그래프를 nxn의 행렬로 표현하는 방법이다. 인접 행렬 방법에서, i 번째행 j 번째 열을 Aij 라고 할 때 정점 i와 j 사이에 엣지가 있으면 1, 없으면 0으로 표시한다.

• 인접 리스트 인접 리스트에서는 배열 하나가 각각의 노드를 표시한다.그리고 나서 해당 노드에 인접한 노드들을 리스트로써 표현한다.

 

• 인접 배열 다른 곳에서는 언급이 없지만 쉽게 배우는 알고리즘 책에 있던 방식.N 개의 연결 배열로 표현한다. i 번째 배열은 정점 i 에 인접한 정점들의 집합으로 표현한다. 아마도 정점 수를 담은 배열과 연결된 정점들을 담은 배열을 연결해서 구현 가능하다.

그래프 탐색 방법

1. 깊이 우선 탐색(DFS, Depth-First Search)
 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법. 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.

사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단하다.

2. 너비 우선 탐색(BFS, Breadth-First Search)
 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법.즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

인접 행렬로 BFS와 DFS 구현

 

import java.util.HashMap;
import java.util.Arrays;
import java.util.LinkedList;

public class GraphByMatrix {
    private HashMap<String,Integer> vertex = new HashMap<>();
    private int[][] edges;
    String[] names = {"철수","영희","동건","준호","재상","승우"};
    public GraphByMatrix(){

        for(int i=0; i<names.length;i++){
            vertex.put(names[i],i);
        }
        edges = new int[][]{{0,1,1,1,0,1},{1,0,1,0,0,0},{1,1,0,0,1,0},{1,0,0,0,0,1},{0,0,1,0,0,1},{1,0,0,1,1,0}};
    }
    public void showVertex(){
        for(String key : vertex.keySet()){
            System.out.printf("%s %d\n",key,vertex.get(key));
        }
    }
    public void showEdges(){
        System.out.printf("\t");
        for(int i = 0; i<edges.length; i++){
            System.out.printf("%s\t",names[i]);
        }
        System.out.println();
        for(int i = 0; i<edges.length;i++){
            System.out.printf("%s",names[i]);
            for(int j = 0; j<edges.length;j++){
                System.out.printf("%2d\t",edges[i][j]);
            }
            System.out.println();
        }
    }
    public void BFS(String v){
        boolean[] isVisited = new boolean[names.length];
        Arrays.fill(isVisited,false);

        LinkedList<String> queue = new LinkedList();
        queue.add(v);
        while(!queue.isEmpty()){
            String x = queue.pop();
            int index = 0;
            for(int i =0; i<names.length;i++){
                if(x.equals(names[i])) index = i;
            }
            isVisited[index] = true;
            System.out.printf("%s ",x);

            int[] edge = edges[index];
            for(int i = 0; i<edge.length;i++){
                if(edge[i] != 0 && !isVisited[i]){
                    isVisited[i] = true;
                    //       System.out.printf("%s ",x);
                    queue.add(names[i]);
                }
            }
        }
    }
    public void DFS(String v){
        boolean[] isVisited = new boolean[names.length];
        Arrays.fill(isVisited,false);

        int index = 0;
        for(int i =0; i<names.length;i++){
            if(names[i].equals(v)) index = i;
        }
        isVisited[index] = true;
        System.out.printf("%s ",v);

        int[] edge = edges[index];
        for(int i = 0; i<edge.length;i++){
            if(edge[i] != 0 && !isVisited[i]){
                aDFS(i,isVisited);
            }
        }
        System.out.println();
    }
    public void aDFS(int index,boolean[] isVisited){
        isVisited[index] = true;
        System.out.printf("%s ",names[index]);
        int[] edge = edges[index];
        for(int i = 0; i<edge.length;i++){
            if(edge[i] != 0 && !isVisited[i]){
                aDFS(i,isVisited);
            }
        }
    }


}

 

인접리스트 구현

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;

public class GraphByList {
    private final String[] names = {"철수","영희","동건","준호","재상","승우"};
    private ArrayList<LinkedList<Vertex>> edges = new ArrayList<>();
    private Vertex[] entry = new Vertex[names.length];
    class Vertex{
        private String key;
        private int values;

        private Vertex(String key,int values){
            this.key = key;
            this.values = values;
        }
    }

    public GraphByList(){
        for(int i = 0;i<names.length;i++){
            entry[i] = new Vertex(names[i],i);
        }
        LinkedList<Vertex> a = new LinkedList<>();
        a.add((entry[1])); a.add((entry[2])); a.add((entry[3])); a.add((entry[5]));
        edges.add(a);

        LinkedList<Vertex> b = new LinkedList<>();
        b.add((entry[0])); b.add((entry[2]));
        edges.add(b);

        LinkedList<Vertex> c = new LinkedList<>();
        c.add((entry[0]));c.add((entry[1])); c.add((entry[4]));
        edges.add(c);

        LinkedList<Vertex> d = new LinkedList<>();
        d.add((entry[0])); d.add((entry[5]));
        edges.add(d);

        LinkedList<Vertex> e = new LinkedList<>();
        e.add((entry[2])); e.add((entry[5]));
        edges.add(e);

        LinkedList<Vertex> f = new LinkedList<>();
        f.add((entry[0])); f.add((entry[3])); f.add((entry[4]));
        edges.add(f);

    }

    public void showVertex(){
        for(Vertex v : entry){
            System.out.printf("%s, %d\n",v.key,v.values);
        }
    }
    public void showEdges(){
        for(int i = 0; i<edges.size();i++){
            LinkedList<Vertex> list = edges.get(i);
            for(Vertex v : list){
                System.out.printf("%s[%d] ",v.key,v.values);
            }
            System.out.println();
        }
    }
    void BFS(int s){
        boolean[] isVisited = new boolean[names.length];
        LinkedList<Integer> queue = new LinkedList();
        isVisited[s] = true;
        queue.add(s);

        while(queue.size()!=0){
            s = queue.poll();
            System.out.printf("%s ",names[s]);

            Iterator<Vertex> i = edges.get(s).listIterator();
            while(i.hasNext()){
                int n = i.next().values;
                if(!isVisited[n]){
                    isVisited[n] = true;
                    queue.add(n);
                }
            }
        }
        System.out.println();
    }

    public void DFS(int v){
        boolean isVisited[] = new boolean[names.length];
        aDFS(v,isVisited);
        System.out.println();
    }
    public void aDFS(int index,boolean[] isVisited){
        isVisited[index] = true;
        System.out.printf("%s ",names[index]);
        Iterator<Vertex> i = edges.get(index).listIterator();
        while(i.hasNext()){
            int n = i.next().values;
            if(!isVisited[n]){
                aDFS(n,isVisited);
            }
        }

    }

}​