C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 12

[1번 문제]

[WGraph.h]

/*

인접 행렬로 구현된 가중치 그래프 클래스

*/

#include "AdjMatGraph.h"

#define INF 9999 //값이 INF 이상이면 간선이 없음

 

class WGraph :public AdjMatGraph //AdjMatGraph 상속

{

public:

        void insertEdge(int u, int v, int weight)

        {

               if (weight > INF)

                       weight = INF;

               setEdge(u, v, weight);

        }

        void insertBothEdge(int u, int v, int weight)

        {

               if (weight > INF)

                       weight = INF;

               setEdge(u, v, weight);

               setEdge(v, u, weight);

        }

        bool hasEdge(int i, int j)

        {

               return (getEdge(i, j) < INF);

        }

        void randomWeightedGraph(int numVtx, int maxWeight=1000)

        {

               int i = 0;

               int random = (numVtx*numVtx - 1) / 2; //모든 정점이 연결되어있는 경우 n(n-1)/2

               int numEdge = rand() % (random-1) + 1;

               for (int j = 0; j < numVtx; j++)

                       insertVertex('A' + j);

               while (i < numEdge)

               {

                       int count = 0;

                       do

                       {

                              int first = rand() % numVtx;

                              int second;

                              do

                              {

                                      second = rand() % numVtx;

                              } while (first == second);

                              if (!adj[first][second])

                              {

                                      int w = rand() % maxWeight + 1;

                                      insertBothEdge(first, second, w);

                                      count++;

                              }

                       } while (!count);

                       i++;

               }

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

                       for (int j = 0; j < numVtx; j++)

                              if (i != j && !adj[i][j])

                                      adj[i][j] = INF;

        }

        void load(char *filename)

        {

               FILE *fp = fopen(filename, "r");

               if (fp != NULL)

               {

                       int n;

                       fscanf(fp, "%d", &n);

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

                       {

                              char str[80];

                              int val;

                              fscanf(fp, "%s", str);

                              insertVertex(str[0]); //정점 삽입

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

                              {

                                      fscanf(fp, "%d", &val); //간선 정보

                                      insertEdge(i, j, val); //간선 삽입

                              }

                       }

                       fclose(fp);

               }

        }

};

 

[2번 문제]

/*

무작위로 가중치 그래프를 발생시키는 함수를 구현한다.

가중치 그래프의 결과를 이용하여 무작위로 발생시키고 Kruskal과 Prim의 최소 신장 트리

알고리즘을 실행하여 결과를 비교하라

*/

#include "WGraphMST.h"

 

int main(void)

{

        WGraphMST g;

        g.randomWeightedGraph(6, 10);

        g.display();

        cout << endl << endl;

        cout << "Kruskal 알고리즘 적용" << endl;

        g.Kruskal();

        cout << endl << endl;

        cout << "Prim 알고리즘 적용" << endl;

        g.Prim(0);

        return 0;

} 

다른 함수들은 http://jaimemin.tistory.com/252?category=970810를 참고하여주시기 바랍니다.

[3번]

[Dijkstra Main]

/*

가중치 그래프를 무작위로 발생시키고, Dijkstra와 Floyd 알고리즘을 실행하여 결과를 비교한다

*/

#include "WGraphDijkstra.h"

 

int main(void)

{

        WGraphDijkstra g1;

        g1.randomWeightedGraph(6, 100);

        g1.display();

        cout << endl << endl;

        cout << "Dijkstra 알고리즘" << endl;

        g1.ShortestPath(0);

        return 0;

}

[Floyd Main]

/*

가중치 그래프를 무작위로 발생시키고, Dijkstra와 Floyd 알고리즘을 실행하여 결과를 비교한다

*/

#include "WGraphFloyd.h"

 

int main(void)

{

        WGraphFloyd g1;

        g1.randomWeightedGraph(6, 100);

        g1.display();

        cout << endl << endl;

        cout << "Floyd 알고리즘" << endl;

        g1.ShortestPathFloyd();

        return 0;

}

다른 함수들은 http://jaimemin.tistory.com/254?category=970810를 참고하여주시기 바랍니다.

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] C++로 쉽게 풀어쓴 자료구조