그래프는 Node(혹은 Vertex)와 Edge로 이루어져 있다.(An undirected graph is a tuple (V,E) where V is a set of nodes and E is a set of edges, each of which being a collection of exactly two elements in V.)

그래프의 Node(Vertex, 혹은 Cell)와 Edge를 컴퓨터 상의 Data Structure로 표현하기 위해 Adjacency Matrix와 Adjacency List를 사용한다.

Adjacency Matrix는 노드의 ID를 Array의 인덱스로 사용하는 2중배열(Matrix)을 만들고 그 배열의 값을 노드간의 연결 - Edge - 로 나타내는 표현방법이다. 예를들면, 노드 아이디 3번과 7번이 연결이 되어있다면 adj_mat[3][7] = 1, 연결되어 있지 않다면 adj_mat[3][7] = 0 식으로 나타낸다.

Adjacency List는 노드가 연결된 노드를 가짐으로써 Edge를 나타내는 표현 방식이다. 대표적인 구현이 List를 Linked-List 방식으로 구현하는 것이지만, map< vertex_id, weight > 방식으로 표현될 수도 있다. - 앞에서도 말했듯이, 이 표현의 핵심은 노드의 연결(edge)을 ‘노드들간의 가짐(linked-list든 pair-map이든)’으로 표현한다는데 있다.

탐색에 있어서 Adjacency Matrix는 기본적으로 O(n^2) 인 반면에 Adjacency List는 (Undirected graph라고 가정하고) O(2e)(e는 edge의 갯수) 만큼의 시간복잡도를 가진다. 뿐만 아니라 Adjacency Matrix는 표현하기 위해 Node의 갯수^2 만큼의 메모리 영역을 차지한다. 그래서 보통 표현에 있어서 Adjacency List를 통해 그래프라는 자료구조를 나타낸다.

아래의 코드는 루비와 Adjacency List 표현을 통해 만든 그래프
(Cell이 node를 의미한다. 전체 Graph Code는 여기서 볼 수 있다.)

class Cell
    attr_accessor :cell_id, :edge_container
    def initialize
        @edge_container = Hash.new
    end
    def addEdge( _rConnectedCell, nWeight )
        if @edge_container[_rConnectedCell.cell_id] != nil && @edge_container[_rConnectedCell.cell_id] != nWeight
            puts "Hei, this graph is not directional graph. weight between vertexes must be same!\n"
        end
        @edge_container[_rConnectedCell.cell_id] = nWeight  
    end
end

class Graph
    def initialize( _nCellidStartNum )
        @nNextCellid = _nCellidStartNum
        @aCellContainer = Hash.new
    end
    def makeCell
        aCell = Cell.new
        aCell.cell_id = @nNextCellid
        @aCellContainer[ aCell.cell_id ] = aCell
        @nNextCellid += 1
        return aCell
    end
    def connectCells( _rCell1, _rCell2 , nWeight)
        _rCell1.addEdge( _rCell2, nWeight )
        _rCell2.addEdge( _rCell1, nWeight )
    end
end