algorithm
그래프

소개

비고

위상 학적 정렬

토폴로지 순서 또는 토폴로지 정렬은 지시 된 모든 가장자리가 왼쪽에서 오른쪽으로 향하도록 한 라인, 즉 목록에서 지정된 비순환 그래프의 정점을 정렬합니다. 그래프에서 방향이 지정된 사이클이 포함되어있는 경우 이러한 행렬은 존재할 수 없습니다. 행을 계속 따라 가면서 시작한 위치로 되돌릴 수있는 방법이 없기 때문입니다.

공식적 그래프에서 G = (V, E) 다음의 모든 꼭지점의 선형 순서 경우되도록이고 G 에지를 포함 (u, v) ∈ E 정점에서 u 버텍스 v 다음 u 선행 v 주문한다.

각 DAG에는 적어도 하나의 토폴로지 정렬이 있어야 합니다.

선형 시간에서 모든 DAG의 위상 순서를 구성하는 알려진 알고리즘이 있습니다. 한 가지 예는 다음과 같습니다.

1. depth_first_search(G) 를 호출하여 각 버텍스의 마감 시간 vf 를 계산합니다. v
2. 각 정점이 완성되면 링크 된 목록의 맨 앞에 삽입하십시오
3. 링크 된 정점 목록. 이제 정렬됩니다.

토폴로지 정렬이 수행 될 수 ϴ(V + E) 깊이 우선 탐색 알고리즘이 필요하기 때문에, 시간 ϴ(V + E) 시간과 소요 Ω(1) 의 각각의 삽입 (일정 시간) |V| 링크 된리스트의 정점에 정점.

많은 응용 프로그램은 이벤트 사이의 우선 순위를 나타내는 방향 비순환 그래프를 사용합니다. 토폴로지 정렬을 사용하여 각 후속 작업 전에 각 정점을 처리하라는 명령을받습니다.

그래프의 정점은 수행 될 태스크를 나타낼 수 있고 에지는 하나의 태스크가 다른 태스크보다 먼저 수행되어야한다는 제약 조건을 나타낼 수 있습니다. 토폴로지 순서는 V 설명 된 태스크 세트를 수행하기위한 유효한 순서입니다.

문제 인스턴스와 해결책

Task(hours_to_complete: int) v 가 Task(hours_to_complete: int) 기술하도록합니다. 즉, Task(4) 는 완료하는 데 4 시간이 소요되는 Task 를 기술하고, Edge e 는 Cooldown(hours: int) Cooldown(3) 기술하여 Cooldown(3) 이 완료된 작업 후에 냉각 될 시간.

우리의 그래프를 dag 이라 부르며 (이는 비순환 식 그래프이기 때문에) 5 개의 꼭지점을 포함하게하십시오 :

A <- dag.add_vertex(Task(4)); 
B <- dag.add_vertex(Task(5));
C <- dag.add_vertex(Task(3)); 
D <- dag.add_vertex(Task(2));
E <- dag.add_vertex(Task(7));

여기서 우리는 그래프가 비순환 (acyclic)이되도록 정점을 지향 에지로 연결하고,

// A ---> C ----+
// |      |     |
// v      v     v
// B ---> D --> E
dag.add_edge(A, B, Cooldown(2));
dag.add_edge(A, C, Cooldown(2));
dag.add_edge(B, D, Cooldown(1));
dag.add_edge(C, D, Cooldown(1));
dag.add_edge(C, E, Cooldown(1));
dag.add_edge(D, E, Cooldown(3));

A 와 E 사이에는 세 가지 가능한 토폴로지 순서가 있으며,

1. A -> B -> D -> E
2. A -> C -> D -> E
3. A -> C -> E

Thorup의 알고리즘

무 방향성 그래프에 대한 단일 소스 최단 경로에 대한 Thorup의 알고리즘은 Dijkstra보다 낮은 시간 복잡도 O (m)를가집니다.

기본 아이디어는 다음과 같습니다. (미안하지만, 아직 구현하지 않았기 때문에 사소한 세부 사항을 놓칠 수도 있습니다. 원본 종이는 페이 웰 월이므로 참조하는 다른 소스에서 재구성하려고했습니다. 확인할 수 있으면이 주석을 제거하십시오.)

• O (m)에서 스패닝 트리를 찾을 수있는 방법이 있습니다 (여기서는 설명하지 않음). 스패닝 트리를 가장 짧은 가장자리에서 가장 긴 가장자리까지 "성장"시켜야합니다. 완전히 성장하기 전에 여러 연결된 구성 요소가있는 포리스트가됩니다.
• 정수 b (b> = 2)를 선택하고 길이 제한이 b ^ k 인 스패닝 포리스트 만 고려하십시오. 정확히 동일하지만 다른 k를 갖는 구성 요소를 병합하고 최소 k를 구성 요소의 레벨이라고합니다. 그런 다음 구성 요소를 논리적으로 트리로 만듭니다. u는 v의 부모입니다. if u는 v를 완전히 포함하는 v와 구별되는 가장 작은 구성 요소입니다. 루트는 전체 그래프이고 잎은 원본 그래프의 단일 정점입니다 (음수 무한대 수준). 트리는 여전히 O (n) 노드 만 있습니다.
• Dijkstra의 알고리즘과 같이 소스에 대한 각 구성 요소의 거리를 유지합니다. 둘 이상의 꼭지점이있는 구성 요소의 거리는 확장되지 않은 자식의 최소 거리입니다. 소스 정점의 거리를 0으로 설정하고 그에 따라 조상을 업데이트합니다.
• 기초 b의 거리를 고려하십시오. 처음 레벨 k에있는 노드를 방문 할 때 레벨 k의 모든 노드 (버킷 정렬에서와 같이 Dijkstra 알고리즘의 힙을 대체)의 숫자 k와 그 이상의 거리로 공유되는 버킷에 자식을 넣습니다. 노드를 방문 할 때마다 첫 번째 B 버킷 만 고려하고 각 노드를 방문하여 제거하고 현재 노드의 거리를 업데이트 한 다음 새 노드를 사용하여 현재 노드를 자신의 부모 노드에 다시 연결하고 다음 노드를 기다립니다 양동이.
• 잎이 방문하면 현재 거리가 정점의 최종 거리입니다. 원본 그래프에서 모든 가장자리를 확장하고 이에 따라 거리를 업데이트하십시오.
• 대상에 도달 할 때까지 루트 노드 (전체 그래프)를 반복적으로 방문하십시오.

길이 제한이 l 인 스패닝 포리스트의 두 연결된 구성 요소 사이에 l보다 작은 길이의 에지가 없으므로 거리 x에서 시작하여 도달 할 때까지 하나의 연결된 구성 요소에만 집중할 수 있습니다 거리 x + l. 더 짧은 거리의 꼭지점을 모두 방문하기 전에 몇 가지 꼭지점을 방문 할 것입니다. 그러나이 꼭지점에서 더 짧은 경로는 없다는 것이 알려져 있기 때문에 중요하지 않습니다. 다른 부분은 버킷 정렬 / MSD 기수 정렬과 비슷하지만 물론 O (m) 스패닝 트리가 필요합니다.

Depth First Traversal을 사용하여 유향 그래프에서주기 감지

DFS에서 뒤쪽 가장자리가 발견되면 방향 그래프의 한주기가 존재합니다. 뒤쪽 모서리는 노드에서 DFS 트리의 조상 중 하나까지의 가장자리입니다. 연결이 끊어진 그래프의 경우 DFS 포리스트를 얻으므로 그래프의 모든 꼭지점을 반복하여 연결되지 않은 DFS 트리를 찾아야합니다.

C ++ 구현 :

    #include <iostream>
     #include <list>
        
    using namespace std; 
    
    #define NUM_V   4

    bool helper(list<int> *graph, int u, bool* visited, bool* recStack)
    {
        visited[u]=true;
        recStack[u]=true;
        list<int>::iterator i;
        for(i = graph[u].begin();i!=graph[u].end();++i)
        {  
            if(recStack[*i]) //if vertice v is found in recursion stack of this DFS traversal
                return true;
            else if(*i==u) //if there's an edge from the vertex to itself
                return true;
            else if(!visited[*i])
            {   if(helper(graph, *i, visited, recStack))
                   return true;
            }
        }
        recStack[u]=false;
        return false;
    }
    /*
    /The wrapper function calls helper function on each vertices which have not been visited. Helper function returns true if it detects a back edge in the subgraph(tree) or false.
*/
    bool isCyclic(list<int> *graph, int V)
    {
      bool visited[V];  //array to track vertices already visited
      bool recStack[V]; //array to track vertices in recursion stack of the traversal.

      for(int i = 0;i<V;i++)
       visited[i]=false, recStack[i]=false;  //initialize all vertices as not visited and not recursed

      for(int u = 0; u < V; u++) //Iteratively checks if every vertices have been visited
      {   if(visited[u]==false)
          {  if(helper(graph, u, visited, recStack)) //checks if the DFS tree from the vertex contains a cycle
               return true;
          }
      }
       return false;
    }
    /*
    Driver function
    */
    int main()
    {
        list<int>* graph = new list<int>[NUM_V];
        graph[0].push_back(1);
        graph[0].push_back(2);
        graph[1].push_back(2);
        graph[2].push_back(0);
        graph[2].push_back(3);
        graph[3].push_back(3);
        bool res = isCyclic(graph, NUM_V);
        cout<<res<<endl;
    }

결과 : 아래 그림과 같이 그래프에는 세 개의 뒤쪽 가장자리가 있습니다. 꼭지점 0과 2 사이에 하나; 버텍스 0, 1, 2 사이; 검색의 시간 복잡도는 O (V + E)이며, 여기서 V는 정점의 수이고 E는 모서리의 수입니다.

그래프 이론 소개

그래프 이론 (Graph Theory) 은 그래프를 연구하는 것으로, 오브젝트 간의 쌍 관계를 모델링하는 데 사용되는 수학적 구조입니다.

여러분은 지구의 거의 모든 문제들이 도로와 도시의 문제로 전환되어 해결 될 수 있다는 것을 알고 계셨습니까? 그래프 이론은 수년 전에 컴퓨터 발명이되기 전에 발명되었습니다. 레온 하드 오일러 (Leonhard Euler) 는 쾨 니히 스 버그 (Königsberg) 의 일곱 다리 에 관한 논문을 썼다.이 이론은 그래프 이론의 첫 번째 논문으로 간주된다. 그 이후로 사람들은 문제를이 도시 도로 문제로 변환 할 수 있다면 그래프 이론을 통해 쉽게 해결할 수 있다는 것을 깨닫게되었습니다.

그래프 이론은 많은 응용 프로그램을 가지고 있습니다. 가장 일반적인 응용 프로그램 중 하나는 한 도시와 다른 도시 간의 최단 거리를 찾는 것입니다. 우리는 귀하의 PC에 도달하기 위해이 웹 페이지가 서버에서 많은 라우터를 여행해야한다는 것을 알고 있습니다. 그래프 이론은 교차해야 할 라우터를 찾는 데 도움이됩니다. 다른 도시들과 자본 도시를 연결 해제하기 위해 폭격을 당해야하는 전쟁 중에는 그래프 이론을 사용하여 수도를 찾아야합니다.

먼저 Graph Theory에 대한 기본 정의를 배웁시다.

그래프:

6 개의 도시가 있다고 가정 해 봅시다. 우리는 그것들을 1, 2, 3, 4, 5, 6으로 표시합니다. 이제 우리는 서로간에 도로가있는 도시들을 연결합니다.

이것은 일부 도시가 연결되어있는 도로가 표시된 간단한 그래프입니다. 그래프 이론에서는 이러한 각 도시 노드 또는 꼭지점 을 호출하고 도로를 에지 라고 부릅니다 . 그래프는 단순히 이러한 노드와 에지를 연결 한 것입니다.

노드 는 많은 것을 나타낼 수 있습니다. 일부 그래프에서 노드는 도시를 나타내며, 일부는 공항을 나타내며 일부는 체스 판의 사각형을 나타냅니다. Edge 는 각 노드 간의 관계를 나타냅니다. 그 관계는 한 공항에서 다른 공항으로 갈 시간, 한 광장에서 다른 모든 광장까지 기사의 움직임 등이 될 수 있습니다.

체스 판에 나이트의 길

간단히 말해 Node 는 모든 객체를 나타내고 Edge 는 두 객체 간의 관계를 나타냅니다.

인접 노드 :

노드 A 가 노드 B 와 모서리를 공유하면 B 는 A에 인접한 것으로 간주됩니다. 즉, 2 개의 노드가 직접 연결되어있는 경우이를 인접 노드라고합니다. 하나의 노드는 여러 인접 노드를 가질 수 있습니다.

지향 및 방향 지정되지 않은 그래프 :

유향 그래프에서 가장자리는 한쪽 방향 기호를 가지므로 가장자리가 단방향 입니다. 한편, 방향이 지정되지 않은 그래프의 가장자리에는 양쪽에 방향 표시가 있습니다. 즉, 양방향 입니다. 일반적으로 방향이 지정되지 않은 그래프는 모서리의 양쪽에 부호가없는 것으로 나타납니다.

파티가 진행 중이라고 가정 해 봅시다. 파티에 참여한 사람들은 노드로 대표되며 악수를하면 두 사람 사이에 우위가 있습니다. 어떤 사람 A가 사람 B와 악수를하기 때문에 그리고이 그래프는 무향 경우에만 B도 악수를합니다. B가 A '의 감탄 B에 대응하는 다른 사용자에 사용자 A로부터 모서리,이 그래프에 관한 경우 대조적으로, 감탄 반드시 왕복 운동하지 않기 때문에. 전자의 유형은 무향 그래프 (undirected graph)라고하며 에지는 무향 에지 ( undirected edge) 라고 불리는 반면 후자의 그래프는 유향 그래프 (directed graph )라고하며 에지는 지향 에지 ( directed edge) 라고 부릅니다 .

가중치 및 비가 중 그래프 :

가중 그래프는 각 에지에 숫자 (가중치)가 할당 된 그래프입니다. 이러한 가중치는 현재의 문제에 따라 비용, 길이 또는 용량을 나타낼 수 있습니다.

가중치가 적용되지 않은 그래프는 그 반대입니다. 우리는 모든 모서리의 무게가 같다고 가정합니다 (아마 1).

통로:

경로는 한 노드에서 다른 노드로 이동하는 방법을 나타냅니다. 그것은 일련의 모서리로 이루어져 있습니다. 두 노드 사이에 여러 경로가있을 수 있습니다.

위의 예에서 A 부터 D 까지 의 두 경로가 있습니다. A → B, B → C, C → D 는 하나의 경로입니다. 이 경로의 비용은 3 + 4 + 2 = 9 입니다. 또 다른 경로 A-> D가 있습니다. 이 경로의 비용은 10 입니다. 비용이 가장 낮은 경로를 최단 경로 라고 합니다 .

정도:

정점의 정도는 그것에 연결된 모서리의 수입니다. 양쪽 끝의 정점에 연결되는 모서리 (루프)가 두 번 계산됩니다.

유향 그래프에서 노드는 두 가지 유형의 학위가 있습니다.

• In-degree : 노드를 가리키는 가장자리의 수.
• Out-degree : 노드에서 다른 노드를 가리키는 엣지의 수.

방향이 지정되지 않은 그래프의 경우 간단히 학위라고합니다.

그래프 이론과 관련된 몇 가지 알고리즘

• 벨만 포드 (Bellman-Ford) 알고리즘
• 다이크 스트라의 알고리즘
• Ford-Fulkerson 알고리즘
• Kruskal의 알고리즘
• 가장 가까운 이웃 알고리즘
• 프림의 알고리즘
• 깊이 우선 검색
• 너비 우선 검색

그래프 저장 (인접 행렬)

그래프를 저장하려면 두 가지 방법이 일반적입니다.

• 인접 행렬
• 인접 목록

인접 행렬 은 유한 그래프를 나타내는 데 사용되는 정사각형 행렬입니다. 행렬의 요소는 그래프에서 인접한 정점 쌍인지 여부를 나타냅니다.

인접한 의미는 '다른 옆이나 옆에있는 것'또는 옆에있는 것을 의미합니다. 예를 들어 이웃 사람들이 당신 옆에 있습니다. 우리는 노드 A에서 B 노드로 이동 할 수있는 경우 그래프 이론에서, 우리는 노드 B가 노드에 인접 말할 수있다. 이제 Adjacency Matrix를 통해 어떤 노드가 어느 노드에 인접 해 있는지를 저장하는 방법에 대해 배웁니다. 이것은 우리가 어떤 노드가 그들 사이의 가장자리를 공유하는지 나타낼 것임을 의미합니다. 여기서 행렬은 2D 배열을 의미합니다.

여기서 그래프 옆의 테이블을 볼 수 있습니다. 이것이 우리의 인접 매트릭스입니다. 여기서 Matrix [i] [j] = 1 은 i 와 j 사이에 모서리가 있음을 나타냅니다. 모서리가 없다면 Matrix [i] [j] = 0을 넣으면됩니다.

이 가장자리는 두 도시 간의 거리를 나타낼 수있는 것처럼 가중치를 적용 할 수 있습니다. 그런 다음 1을 쓰는 대신 Matrix [i] [j]에 값을 넣을 것입니다.

우리는 노드 2로부터 노드 1로 갈 수 있으면 상술 한 그래프, 즉, 양방향 또는 무향, 우리는 또한 노드 1에서 노드 2까지 갈 수있다. 그래프가 Directed 이면 그래프의 한쪽에 화살표 기호가 표시됩니다. 그렇다하더라도 인접 행렬을 사용하여 표현할 수 있습니다.

무한대로 가장자리를 공유하지 않는 노드를 나타냅니다. 한 가지 주목할 점은 그래프가 방향이 지정되어 있지 않으면 행렬이 대칭 이된다는 것입니다.

행렬을 생성하는 의사 코드 :

Procedure AdjacencyMatrix(N):    //N represents the number of nodes
Matrix[N][N]
for i from 1 to N
    for j from 1 to N
        Take input -> Matrix[i][j]
    endfor
endfor

다음과 같은 일반적인 방법으로 매트릭스를 채울 수도 있습니다.

Procedure AdjacencyMatrix(N, E):    // N -> number of nodes
Matrix[N][E]                        // E -> number of edges
for i from 1 to E
    input -> n1, n2, cost
    Matrix[n1][n2] = cost
    Matrix[n2][n1] = cost
endfor

유향 그래프의 경우 Matrix [n2] [n1] = cost line을 제거 할 수 있습니다.

인접성 매트릭스 사용의 단점 :

기억은 큰 문제입니다. 얼마나 많은 모서리가 있더라도 항상 N * N 크기의 행렬이 필요합니다. 여기서 N은 노드의 수입니다. 10000 개의 노드가있는 경우, 매트릭스 크기는 381 메가 바이트를 기준으로 4 * 10000 * 10000이됩니다. 에지가 몇 개인 그래프를 생각하면 엄청난 낭비입니다.

노드 u 에서 어떤 노드로 갈 수 있는지 알고 싶다고합시다. 우리는 많은 시간을 소모하는 u 의 전체 행을 확인할 필요가 있습니다.

유일한 이점은 Adjacency Matrix를 사용하여 uv 노드와 비용 사이의 연결을 쉽게 찾을 수 있다는 것입니다.

위의 의사 코드를 사용하여 구현 된 Java 코드 :

import java.util.Scanner;
 
public class Represent_Graph_Adjacency_Matrix 
{
    private final int vertices;
    private int[][] adjacency_matrix;
 
    public Represent_Graph_Adjacency_Matrix(int v) 
    {
        vertices = v;
        adjacency_matrix = new int[vertices + 1][vertices + 1];
    }
 
    public void makeEdge(int to, int from, int edge) 
    {
        try 
        {
            adjacency_matrix[to][from] = edge;
        }
        catch (ArrayIndexOutOfBoundsException index) 
        {
            System.out.println("The vertices does not exists");
        }
    }
 
    public int getEdge(int to, int from) 
    {
        try 
        {
            return adjacency_matrix[to][from];
        }
        catch (ArrayIndexOutOfBoundsException index) 
        {
            System.out.println("The vertices does not exists");
        }
        return -1;
    }
 
    public static void main(String args[]) 
    {
        int v, e, count = 1, to = 0, from = 0;
        Scanner sc = new Scanner(System.in);
        Represent_Graph_Adjacency_Matrix graph;
        try 
        {
            System.out.println("Enter the number of vertices: ");
            v = sc.nextInt();
            System.out.println("Enter the number of edges: ");
            e = sc.nextInt();
 
            graph = new Represent_Graph_Adjacency_Matrix(v);
 
            System.out.println("Enter the edges: <to> <from>");
            while (count <= e) 
            {
                to = sc.nextInt();
                from = sc.nextInt();
 
                graph.makeEdge(to, from, 1);
                count++;
            }
 
            System.out.println("The adjacency matrix for the given graph is: ");
            System.out.print("  ");
            for (int i = 1; i <= v; i++)
                System.out.print(i + " ");
            System.out.println();
 
            for (int i = 1; i <= v; i++) 
            {
                System.out.print(i + " ");
                for (int j = 1; j <= v; j++) 
                    System.out.print(graph.getEdge(i, j) + " ");
                System.out.println();
            }
 
        }
        catch (Exception E) 
        {
            System.out.println("Somthing went wrong");
        }
 
        sc.close();
    }
}

코드 실행 : 파일을 저장하고 javac Represent_Graph_Adjacency_Matrix.java 사용하여 javac Represent_Graph_Adjacency_Matrix.java

예:

$ java Represent_Graph_Adjacency_Matrix
Enter the number of vertices:
4
Enter the number of edges:
6
Enter the edges: <to> <from>
1 1
3 4
2 3
1 4
2 4
1 2
The adjacency matrix for the given graph is:
  1 2 3 4
1 1 1 0 1
2 0 0 1 1
3 0 0 0 1
4 0 0 0 0

그래프 저장 (인접 목록)

인접 목록 은 유한 그래프를 나타내는 데 사용되는 정렬되지 않은 목록의 모음입니다. 각 목록은 그래프에서 정점의 이웃 집합을 설명합니다. 그래프를 저장하는 데 필요한 메모리가 적습니다.

그래프와 그 인접 행렬을 봅시다.

이제 우리는 이러한 값을 사용하여 목록을 만듭니다.

이를 인접 목록이라고합니다. 어떤 노드가 어떤 노드에 연결되어 있는지를 보여줍니다. 2D 배열을 사용하여이 정보를 저장할 수 있습니다. 그러나 Adjacency Matrix와 같은 메모리가 필요합니다. 대신 동적으로 할당 된 메모리를 사용하여이 메모리를 저장하려고합니다.

많은 언어가 벡터 또는 목록 을 지원하여 인접 목록을 저장할 수 있습니다. 이를 위해 목록 의 크기를 지정할 필요가 없습니다. 최대 노드 수만 지정하면됩니다.

의사 코드는 다음과 같습니다.

Procedure Adjacency-List(maxN, E):       // maxN denotes the maximum number of nodes
edge[maxN] = Vector()                    // E denotes the number of edges
for i from 1 to E
    input -> x, y                        // Here x, y denotes there is an edge between x, y
    edge[x].push(y)
    edge[y].push(x)
end for
Return edge

이 하나 무향 그래프이기 때문에,이 X와 Y의 에지가, X와 Y에서 에지도있다. 만약 그것이 유향 그래프라면, 우리는 두 번째 그래프를 생략 할 것입니다. 가중 그래프의 경우 비용도 저장해야합니다. 우리는 이것을 저장하기 위해 cost [] 라는 다른 벡터 나 리스트를 생성 할 것입니다. 의사 코드 :

Procedure Adjacency-List(maxN, E):
edge[maxN] = Vector()
cost[maxN] = Vector()
for i from 1 to E
    input -> x, y, w
    edge[x].push(y)
    cost[x].push(w)
end for
Return edge, cost

여기에서 우리는 어떤 노드에 연결되어있는 노드의 총 수와이 노드가 무엇인지 쉽게 알 수 있습니다. Adjacency Matrix보다 시간이 적습니다. 그러나 u 와 v 사이에 가장자리가 있는지 알아야 할 필요가 있다면 인접 매트릭스를 유지하면 더 쉬울 것입니다.