C++/Fundamentals of Data Structures in C++(Horowitz)

C++ Fundamentals of Data Structures(C++ 자료구조론) 6.1 AdjacencyList Graph(인접리스트 그래프) 예제

꾸준함. 2017. 9. 11. 20:44

/*

간단한 인접리스트 그래프, 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) 원서


*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.

반응형