그래프 표현: 인접 목록 대 인접 매트릭스

그래프는 정점과 가장자리로 구성된 비선형 데이터 구조입니다. 소셜 네트워크, 라우팅, 전화 네트워크 및 회선 네트워크와 같은 많은 실제 응용 프로그램에서 가장 중요한 데이터 구조 중 하나입니다.

두 가지 구성 요소로 구성됩니다.

정점 또는 노드의 유한 세트.

( u , v ) 형식의 유한 순서 쌍 집합을 가장자리라고 합니다.

그래프 표현

G = (V, E) 여기서 V는 정점 집합이고 E는 가장자리 집합이며 각 가장자리는 정점의 튜플로 표현됩니다.

가장 일반적으로 사용되는 두 가지 그래프 표현이 있습니다.

인접 매트릭스

인접 목록

그래프는 발생률 매트릭스 및 발생률 목록을 사용하여 표현할 수도 있습니다. 그래프 표현의 선택은 수행되는 작업 유형과 사용할 알고리즘에 따라 다릅니다.

인접 행렬

인접 행렬은 |V| |브이| V가 그래프의 정점인 2차원 배열입니다. 행렬의 요소(i, j)는 에지 E(vi,vj)가 있는 경우에만 1입니다. 따라서 인접 행렬은 (|V|2) 저장 공간을 차지합니다. 무방향 그래프의 인접 행렬은 항상 대칭입니다. 가중 그래프의 경우 adj[i][j]는 w와 같을 것입니다. 이는 가중치가 w인 정점 i에서 정점 j까지의 간선이 있음을 의미합니다.

인접 행렬 알고리즘

Create a matrix A of size NxN Initialise it with zero Now, Iterate over each edge given in form (u,v)

Assign 1 to A[u][v] : If graph is undirected then assign 1 to A[v][u].

인접 행렬의 구현

class Graph:
    """
    Adjacency Matrix Representation in Python
    """

    # Initialize the matrix
    def __init__ (self, size):
        self.adjMatrix = [[0 for _ in range(size)] for _ in range(size)]
        self.size = size

    # adding edge from vertex v1 to v2
    def addEdge(self, v1, v2):
        self.adjMatrix[v1][v2] = 1
        self.adjMatrix[v2][v1] = 1

    # deleting edge
    def delEdge(self, v1, v2):
        self.adjMatrix[v1][v2] = 0
        self.adjMatrix[v2][v1] = 0

    # length of graph
    def __len__ (self):
        return self.size

    # printing matrix
    def printMatrix(self):
        for row in self.adjMatrix:
            print(*row)
            print

def main():
    graph = Graph(5) # init graph of size 5
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 2)
    graph.addEdge(2, 0)
    graph.addEdge(2, 3)

    graph.printMatrix()

if __name__ == " __main__":
    main()

출력 : 0 1 1 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0

장점:

구현하고 이해하기 쉽습니다.

모서리 제거에는 O(1) 시간이 걸립니다.

정점 u에서 정점 v까지의 에지를 찾는 것과 같은 쿼리는 효율적이며 O(1)로 수행할 수 있습니다.

단점:

더 많은 공간 O(V2)를 소비합니다.

희소 그래프의 경우에도 동일한 공간을 차지하고 정점을 추가하는 데 O(V2) 시간이 걸립니다.

인접 목록

인접 목록은 목록의 목록이며 각 목록은 정점 u에 연결되며 여기에는 u에서 시작되는 가장자리 목록이 포함됩니다. 따라서 인접 목록은 최악의 경우 (V + E) 공간을 차지합니다.

인접 목록 구현

class Node:
    """
    creating a node to connect
    to our main adjacency list
    """

    def __init__ (self, data):
        self.vertex = data
        self.next = None

class Graph:
    """
    this class represents a graph as an adjacency list. The size of the array will be the no.
    of the vertices "V"
    """

    def __init__ (self, vertices):
        self.V = vertices
        self.graph = [None] * self.V

    def addEdge(self, src, dest):
        # Adding the node to the source node
        node = Node(dest)
        node.next = self.graph[src]
        self.graph[src] = node

        # Adding the source node to the destination
        # as a undirected graph
        node = Node(src)
        node.next = self.graph[dest]
        self.graph[dest] = node

    # printing the graph
    def printGraph(self):
        for i in range(self.V):
            print("Adjacency list of vertex {}\n head".format(i), end="")
            temp = self.graph[i]
            while temp:
                print(" -> {}".format(temp.vertex), end="")
                temp = temp.next
            print

def main():
    graph = Graph(5) # graph of 5 vertices
    graph.addEdge(0, 1)
    graph.addEdge(0, 4)
    graph.addEdge(1, 2)
    graph.addEdge(1, 3)
    graph.addEdge(1, 4)
    graph.addEdge(2, 3)
    graph.addEdge(3, 4)

    graph.printGraph()

if __name__ == " __main__":
    main()

출력 : 정점 0 헤드의 인접 리스트 -> 4 -> 1 정점 1 헤드의 인접 리스트 -> 4 -> 3 -> 2 -> 0 정점 2 헤드의 인접 리스트 -> 3 -> 1 정점 3 헤드의 인접 리스트 -> 4 -> 2 -> 1 정점 4 헤드의 인접 리스트 -> 3 -> 1 -> 0

장점:

공간 O(|V|+|E|)를 절약합니다. 최악의 경우 그래프의 가장자리 수는 C(V, 2)개이며 이는 최대 O(V2) 공간을 차지함을 의미합니다.

정점을 추가하는 것은 더 간단합니다.

단점:

정점 u에서 정점 v까지의 에지를 찾는 것과 같은 쿼리는 효율적이지 않으며 O(V)로 수행할 수 있습니다.