#008 DS&A- 그림

그림

도론은 일반적으로 사물 간의 관계를 연구하는 대수 과목으로 컴퓨터 과학에서 가장 자주 사용하는 것은 인터넷이다.

그림의 표시

첫 번째 표현은 adjacency matrix입니다. 어떤 경우에도 점과 다른 점 사이의 링크를 나타냅니다. 예를 들어 a 은 점 자체와 관계가 없고, a 은 b 과 관계가 있으며, a 은 c 과 직접적인 관계가 없습니다.
하나
b
c
d
하나
0
일.
0
일.
b
일.
0
일.
0
c
0
일.
0
일.
d
일.
0
일.
0
또 다른 유행 표현법은 linked list
각 노드에는 연결된 노드를 가리키는 바늘이 있습니다.
조밀도는 그것의 노드 사이에 많은 연결이 있는 그림이다.
만약에 조밀함E=O(v^2)이면 그 중E은 변의 수량이고 v은 정점의 수량이다. 이것은 그림 자체가 그들 사이에 많은 관계를 가진다는 것을 의미한다. 다시 말하면 행렬은 거의 1이다.
만약에 우리가 비슷한 소셜네트워크서비스를 필요로 한다면 체인 시계는 더욱 의미가 있다. 왜냐하면 우리는 단지 몇 명의 친구를 통해 인터넷 속의 모든 사람들과 연락하지 않기 때문이다.
체인 테이블의 순서는 O(V+2E), 즉 <O(v^2)

BFS 및 DFS

방문은 내가 그것을 방문하거나 인쇄하는 것을 의미한다.
탐색은 내가 그녀(이웃) 사이의 모든 관계를 탐색하는 것을 의미한다.
액세스됨
탐색
뜻
0
0
액세스하지 않음 및 탐색하지 않음
일.
0
참관했지만 탐색하지 않았다
일.
일.
참관과 탐색
그룹 검사를 통해 접근할 수 있는 노드를 사용할 수 있습니다. Queue 또는 Stack explorer there 알고리즘을 사용하려면 Queue 을 사용하십시오. BFS (Breadth First Search) 을 사용하려면 stack 을 사용하십시오.DFS (Depth First Search) 이렇게 나무를 통과합니다.
BFS 이렇게 나무를 통과합니다.

BFS 알고리즘

// the graph G and array visited[] are global
// visited[] is initialized to 0
BFS(v)
{
    u = v;
    visited[u] = 1;
    repeat
    {
        for all vertices w adj to u do
        {
            if(visited == 0)
            {
                add w to q;
                visited[w] = 1;
            }
        }

        if q is empty then return;
        delete the next element u from q;
    }
}

차트 DFS G 수조를 visited로 초기화
일.
이.
삼.
사.
오.
육.
칠.
팔.
0
0
0
0
0
0
0
0
대기열0첫 번째 교체q와 정점u=1이 w 예u로 조정되기 때문에 방문과 대기열은
일.
이.
삼.
사.
오.
육.
칠.
팔.
일.
0
0
0
0
0
0
0
이.
대기열w={2,3}에 추가한 후 액세스됨으로 표시2 수조를 visited로 초기화
일.
이.
삼.
사.
오.
육.
칠.
팔.
일.
일.
0
0
0
0
0
0
지금 우리는 0에서 끝난다. 우리는 2로 가야 한다. 왜냐하면 여기는 3 순환이 있기 때문이다. for의 모든 인접 부분으로 돌아갈 수 있다. 그것들은 1일.
이.
삼.
사.
오.
육.
칠.
팔.
일.
일.
일.
0
0
0
0
0
이.
삼.
현재 우리는 {2,3} 순환for이 비어 있지 않기 때문에 q에서 다음 요소, 즉 q을 삭제해야 한다. 현재 우리의 2은 u, 이웃의 2은 2이 방문되었기 때문에 우리는 다시는 그것을 방문하지 않을 것이다. 우리는 이전과 같은 논리를 집행하고 우리가 비어 있을 때까지w={1,4,5}, 이것은 모든 것이 방문하고 탐색된다는 것을 의미한다.

linkedlist의 BFS 분석

대기열 구현의 공간 복잡도1linkedlist 필요q

인접 행렬로 이루어진 BFS 분석

만약 우리가 O(v)의 정점이 있다면, 이것은 우리가 O(v+E) 크기의 행렬이 필요하다는 것을 의미한다. 그 수조와 대기열 실현은 모두 8의 공간 복잡도를 가지게 될 것이다. 그 중에서 v는 정점수이고 시간 복잡도는 8x8

BFS 너비 우선 적용

그림이 연결되었는지 알기 위해서, 이것은 모든 노드가 같은 그림에 있다는 것을 의미한다

이것들은 두 개의 그림O(v)과 T(v^2)으로 나눌 수 있는데, 그 중에서 적어도 한 개의 노드가 U와 G의 교차점이 없다
이 두 개의 하위 그림을 두루 훑어보다

BFT(G,n)
{
    // this loop to fill the array with not visited yet
    for i=1 to n do
        visited[i] = 0
    // this will visit every node that is not visited yet
    for i=1 to n do
        if(visited[i]==0) then BFS(i) //BFS not BFT !!!!!
}

각 사례가 하나의 노드를 대표하도록 하다

첫 번째 U 상자는 V 노드가 있는 4 그림입니다. 그는 1부터 시작하여 U 에서 방문한 것으로 표시하고 중단합니다.
그런 다음 4 부터 시작하여 동일한 작업을 수행합니다.
시간 복잡도1->4, 공간 복잡도V

DFS 알고리즘

DFS(v)
{
    visited[v] = 1;
    for each vertex w adj to v do
    {
        if(visited[w] == 0) then
            DFS(w);
    }
}

O(E+V)에서 우리는 한 점에서 그것을 탐색하기 시작한다. 만약에 그 중의 다음 노드가 탐색되지 않으면 이전 노드를 떠나 새로운 노드를 탐색한다.
액세스를 초기화하는 수조는 이 함수를 호출하는 프로그램에서 이루어집니다. 시간 복잡도를 계산할 때 고려합니다.

V=1
V=2
V=4
V=8
V=5
V=6
V=3
V=7
w={2,3}
w={1,4,5}
w={2,8}
w={4,5,6,7}
w={2,8}
w={3,8}
w={1,7}
w={3,8}
2 미방문
4 미방문
8 미방문
5 액세스하지 않음
모든 w 방문은 v=8, 6로 돌아갑니다.
8 액세스하지 않음
v=8, 7로 돌아갔습니다. 액세스하지 않았습니다.
모든 w 액세스, 모든 V 액세스
우리가 본 바와 같이, 매번 우리가 방문하지 않은 노드가 있을 때마다, 우리는 그것의 이웃을 충분히 탐색할 것이다.만약 모든 이웃이 방문된다면, 우리는 옛 이웃에게 돌아갈 것이다.

DFS 및 DFT 분석

O(V)의 공간 복잡도DFS는 그림이 체인식이라면 최악의 상황이다. 모든 노드가 창고에 동시에 위치하기 때문이다.따라서 DFS과O(V)의 공간 복잡도DFS, 체인표가 표시하는 시간 복잡도BFS, 그 중에서 O(v)는 액세스 그룹을 초기화하는 시간, O(E)+O(V)는 행렬이 표시하는 시간으로 O(V)과 같다.O(V^2)호출BFS이 아니라 DFT호출BFT과 같습니다.