도 론 기초 편

그림 소개
그림 이라는 단 어 를 말하자면 많은 사람들 이 먼저 생각 하 는 것 이 바로 그림, 지도... 등 이지 만 여기 서 말 하 는 그림 은 추상 적 인 개념 이다.
정의: 그림 은 한 그룹의 정점 과 한 그룹 이 두 개의 정점 을 연결 할 수 있 는 변 으로 구성 되 어 있다.
도 론 은 수학 분야 의 중요 한 부분 이 었 으 나 컴퓨터 과학 분야 의 응용 에서 도 론 을 바탕 으로 일련의 결점 과 변 의 모델 에서 매우 중요 한 역할 을 했다. 그림 의 알고리즘 은 실제 생활 에서 비교적 복잡 한 문 제 를 해결 할 수 있다. 예 를 들 어 우리 의 지도, 회로,사회 에서 사람과 사람 간 의 관계 망 은 이미 급 컴퓨터 네트워크 등 일반적인 데이터 구 조 를 통 해 묘사 할 수 없다.그래서 이것 도 많은 고급 알고리즘 의 초석 이다. 지금까지 도 론 알고리즘 에 대한 연 구 는 계속 진행 되 고 있다. 왜냐하면 아직도 많은 분야 에서 해결 할 수 없 는 문제 가 있 기 때문이다.여기 서 그림 의 기초 산법 을 총 결 하 다.
그림 의 표시
그림 의 분 류 는 매우 많은 데 방향 에 따라 유방 향도 와 무방 향도 로 나 눌 수 있 고 밀도 에 따라 희소 도와 조밀도 로 나 눌 수 있다.희소 도 에 대한 일반적인 표현 방법 은 인접 표 이 고 조밀도 에 대한 일반적인 표현 은 인접 행렬 이다.여기 서 방향 성 이 있 는 것 에 대해 우 리 는 간단 한 불 유형의 변 수 를 사용 하여 표시 한 다음 에 int 형의 변수 v, e 로 각각 정점 과 변 을 표시 할 수 있다.우선 희소 도 표시 입 니 다. 다음 코드 를 보 세 요.

//     -    
public class SparseGraph {

    private int v;  //    
    private int e;  //   
    private boolean directed;    //       
    private Vector[] g; //       

    //     
    public SparseGraph( int n , boolean directed ){
        assert n >= 0;
        this.v = v;
        this.e = e;    //         
        this.directed = directed;
        // g    n   vector,      g[i]   ,       
        g = (Vector[])new Vector[n];
        for(int i = 0 ; i < n ; i ++)
            g[i] = new Vector();
    }

    public int V(){ return v;} //       
    public int E(){ return e;} //       

    //         
    public void addEdge( int v, int w ){

        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;

        g[v].add(w);
        if( v != w && !directed )
            g[w].add(v);

        e ++;
    }

    //         v w  
    boolean hasEdge( int v , int w ){

        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;

        for( int i = 0 ; i < g[v].size() ; i ++ )
            if( g[v].elementAt(i) == w )
                return true;
        return false;
    }
}

여기 서 hasEdge () 를 사용 하여 변 의 검증 을 진행 하 였 으 며, addEdge () 방법 으로 변 을 추가 하 였 으 며, 주의 방법 중의 판단 에 주의 하 였 습 니 다. 만약 정점 에서 자 환 이 생기 지 않 았 다 면 (자 환 은 하나의 정점 에서 출발 하여 마지막 으로 이 정점 으로 돌아 가 는 것 입 니 다), 그림 이 방향 이 없 는 그림 이 라면 v 도 w 의 링크 에 추가 한 다음 에 조밀도 의 표 시 를 보 았 습 니 다.

//     -     
public class DenseGraph {

    private int v;  //    
    private int e;  //   
    private boolean directed;   //       
    private boolean[][] g;      //       

    //     
    public DenseGraph( int n , boolean directed ){
        assert n >= 0;
        this.n = n;
        this.e = 0;    //         
        this.directed = directed;
        // g    n*n     ,    g[i][j]  false,        
        // false boolean       
        g = new boolean[n][n];
    }

    public int V(){ return n;} //       
    public int E(){ return m;} //       

    //         
    public void addEdge( int v , int w ){

        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;

        if( hasEdge( v , w ) )
            return;

        g[v][w] = true;
        if( !directed )
            g[w][v] = true;

        e ++;
    }

    //         v w  
    boolean hasEdge( int v , int w ){
        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;
        return g[v][w];
    }
}

같은 이치 이지 만 인접 행렬 은 인접 링크 보다 더 높 은 공간 복잡 도 를 가진다.
3. 흔히 볼 수 있 는 그림 처리 방식
먼저 adj () 방법 을 정의 합 니 다.

//      v       
public Iterable adj(int v) {
    return adj[v];
}

1. 정점 의 도 수 를 계산한다
여기 서 가리 키 는 어떤 정점 에 붙 어 있 는 변 의 수량

public static int degree(Graph G,int v) {
    int degree = 0;
    for (int w : G.adj(v))
        degree++;
    return degree;
}

2. 모든 정점 의 최대 도 수 를 계산한다.

public static int maxDegree(Graph G) {
        int max = 0;
        for (int v = 0;vif (degree(G,v) > max) {
                max = degree(G,v);
            }
        }
        return max;
    }

3. 자체 고리 의 개 수 를 계산한다.

public static int numberOfSelfLoops(Graph G) {
        int count = 0;
        for (int v=0;vfor (int w : G.adj(v))
                if (v == w)
                    count++;
        }
        return count/2;  //           
    }

이 편 은 여기까지 하 겠 습 니 다.