인접 리스트(Adjacency List)

인접 리스트(Adjacency List)

정의

 각각의 정점에 인접한 정점들을 연결 리스트로 표시한 것

특징

1) 각 연결 리스트의 노드들은 인접 정점을 저장

2) 연결 리스트들은 헤더 노드를 가지고 있고 헤더 노드들은 하나의 배열로 구성되어 있다.

3) 정점의 번호를 이용하여 배열의 인덱스에 접근할 수 있으므로 정점 리스트에 쉽게 접근할 수 있다.

4) 정점의 개수에 비해 연결된 선분이 적을 때 사용하면 좋다

#include <iostream>

using namespace std;

// enum으로 정점을 숫자로 치환, 배열을 이용하여 다시 되돌림

enum vertices { a, b, c, d, e, f };

char vertices[] = { 'a', 'b', 'c', 'd', 'e', 'f' };    

typedef int LData;

typedef struct _node

{

_node() : data(0), next(NULL) {}

LData data;

struct _node * next;

} Node;

typedef struct _list

{

Node * head;

} List;

class adjacency_graph

{

private:

List * plist;

int n;

public:

adjacency_graph() {}

adjacency_graph(int n);

~adjacency_graph() {}

Node * create_vertex(int vertex);

void connect(int start_vtx, int dest_vtx);

void print();

};

adjacency_graph::adjacency_graph(int n)

{

this->n = n + 1;

plist = new List[n+1]; // 점의 개수만큼 리스트 생성

for (int i = 0; i < this->n; i++)

{

plist[i].head = NULL;

}

}

// 정점 생성

Node * adjacency_graph::create_vertex(int vertex)

{

Node * newnode = new Node;

newnode->data = vertex;

return newnode;

}

// 정점 연결

void adjacency_graph::connect(int start_vtx, int near_vtx)

{

Node * newnode = create_vertex(start_vtx);

newnode->next = plist[near_vtx].head;

plist[near_vtx].head = newnode;

}

void adjacency_graph::print()

{

for (int i = 0; i < n; i++)

{

Node * p = plist[i].head;

cout << "점 " << vertices[i] << "의 인접리스트";

while (p)

{

cout << "->" << vertices[p->data];

p = p->next;

}

cout << endl;

}

}

int main()

{

adjacency_graph adj_list(f);

adj_list.connect(a, b);

adj_list.connect(a, d);

adj_list.connect(a, e);

adj_list.connect(b, a);

adj_list.connect(b, d);

adj_list.connect(b, c);

adj_list.connect(b, f);

adj_list.connect(c, b);

adj_list.connect(c, f);

adj_list.connect(d, a);

adj_list.connect(d, b);

adj_list.connect(d, e);

adj_list.connect(d, f);

adj_list.connect(e, a);

adj_list.connect(e, d);

adj_list.connect(e, f);

adj_list.connect(f, b);

adj_list.connect(f, c);

adj_list.connect(f, d);

adj_list.connect(f, e);

adj_list.print();

return 0;

}