인접 목록 그래프 표현의 구현

Question

방금 ​​그래프 이론으로 시작했습니다. 연결된 목록을 사용하여 인접 목록을 코딩하는 방법을 이해할 수 없습니다. 예를 들어이 그래프가있는 경우 (무향) :

A--------B 
|  /|\ 
| /| \ 
| /| \ 
| / | \ 
| / | \ 
|/ |  \ 
|/ |  \ 
C  E-------D 

어떻게 코딩합니까? 인접 행렬을 사용하는 방법을 알고 있지만 인접 목록과 연결된 목록 (C++)을 사용하여 코드를 작성하는 방법은 무엇입니까?

Answer 1

인접 목록은 목록의 벡터/배열 일뿐입니다. 그래프의 각 요소는 배열의 요소이며 모든 인접 요소는 인접 목록에 추가됩니다. 따라서이 같은 같습니다

A -> {B, C}를

B -> {A, C, D, E}

C -> {A, B}

D -> {B, E}

E -> {B, D}는

그래서 우리는 std::vector<std::list<vertex>>과 같이 시작합니다. 그러나 vertifications는 고유하므로 더 잘 수행 할 수 있으므로 map을 사용할 수 있습니다. 또한 정점은 한 번만 가장자리 목록에 나타날 수 있으므로 std::map<vertex, std::set<vertex>>으로 수정합니다.

그래서 같은과 함께 시작합니다 :

struct vertex 
{ 
    // 
}; 

class undirected_graph 
{ 
private: 
    std::map<vertex, std::set<vertex>> graph_container; 
public: 
    void add_vertex(const vertex& v) { //add a vertex to the map } 
    void add_edge(const vertex& v, const vertex& u) { //look up vertex in map and add to the vertex adjacency list } 
    //Other methods 
    //... 
}; 

Answer 2

인접 목록은 그래프 가장자리를 나타내는 개체 집합입니다.

struct edge { 
    node *nodes[2]; 

    edge(node *a, node *b) { 
     if (a < b) { // define canonical order of edges for undirected graph 
      nodes[0] = a; 
      nodes[1] = b; 
     } else { 
      nodes[0] = b; 
      nodes[1] = a; 
     } 
    } 
}; 

연결된 목록은 특히 실용적이지 않습니다. 일반적으로 가장자리의 순서를 정의하고 std::set 또는 std::map에 넣습니다.

bool operator< (edge const &lhs, edge const &rhs) { 
    if (lhs.nodes[0] < rhs.nodes[0]) return true; 
    if (rhs.nodes[0] < lhs.nodes[0]) return false; 
    return lhs.nodes[1] < rhs.nodes[1]; 
} 

typedef std::set<edge> graph; 

이렇게하는 방법은 많이 있지만, 그래프로하려는 의도를 알지 못해서 더 이상 제안하기가 어렵습니다.