/*
간단한 인접리스트 그래프, Simple AdjacencyList Graph
*/
#include <iostream>
using namespace std;
class ChainNode
{
private:
int data;
ChainNode *link;
public:
ChainNode(int element = 0, ChainNode *next = NULL) :data(element), link(next)
{
}
int getData()
{
return data;
}
ChainNode *Link()
{
return link;
}
friend class AdjList;
friend class LinkedGraph;
friend ostream &operator<<(ostream &os, LinkedGraph &lg);
};
class AdjList
{
ChainNode *first;
friend class LinkedGraph;
friend ostream &operator<<(ostream &os, LinkedGraph &lg);
};
class LinkedGraph
{
private:
AdjList *list;
int n;
public:
LinkedGraph(int number) :n(number)
{
list = new AdjList[n];
for (int i = 0; i < n; i++)
list[i].first = NULL; //초기화
}
void linkEdge(int num1, int num2) //꼭지점과 꼭지점을 이어준다
{
ChainNode *newNode = new ChainNode(num2);
newNode->link = list[num1].first; //num2의 다음을 num1로
list[num1].first = newNode;
newNode = new ChainNode(num1);
newNode->link = list[num2].first; //num1의 다음을 num2로
list[num2].first = newNode;
}
friend ostream &operator<<(ostream &os, LinkedGraph &lg);
};
ostream &operator<<(ostream &os, LinkedGraph &lg)
{
os << "각 꼭지점에 연결되어있는 꼭지점을 나열" << endl;
for (int i = 0; i < lg.n; i++)
{
ChainNode *temp = lg.list[i].first;
os << i << ": ";
while (temp)
{
os << temp->data << " ";
temp = temp->link;
}
os << endl;
}
return os;
}
int main(void)
{
LinkedGraph lg(10);
for (int i = 0; i < 10; i++) //랜덤하게 꼭지점을 이어보았다
{
lg.linkEdge(i, i + 1);
if (i < 5)
lg.linkEdge(i, i + 5);
else
lg.linkEdge(i, i - 3);
}
cout << lg;
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.