[Algorithm]그래프 입력받기

많은 알고리즘 문제들은 그래프 기반이다

 

그래프를 입력받는 방법은 크게 두가지가 있는데 

1. 인접행렬을 이용하여 연결관계를 나타내는 방법과

인접 행렬 이용, 출처 : https://sarah950716.tistory.com/12

2. 링크드 리스트를 통해 그래프를 나타내는 것이다.

링크드 리스트 이용, 출처 : https://sarah950716.tistory.com/12

 

 

이 중 두번째 리스트를 이용한 그래프 입력을 구현해 보았다.

문제를 풀기 위해 우선순위 큐 선언이 들어가 있는데 무시해도 좋다.

 

입력은 다음과 같다

노드수, 간선수

시작 노드

출발노드 도착노드 가중치

출발노드 도착노드 가중치

출발노드 도착노드 가중치

...

graph_input.txt

#define VERTEX_MAX 50
#define INF 2123456789
 
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
 
 
struct cmp {
    bool operator()(pair<int, int> a, pair<int, int> b)
    {
        if (a.second <= b.second)
            return 1;
        else
        {
            return 0;
        }
    }
};
 
priority_queue<int,vector<pair<int,int>>,cmp> gMyPriorityQueue;
vector<pair<int, int>> gVertex[VERTEX_MAX];
 
int gDistance[VERTEX_MAX];
int gStartVertex;
int gVertexCount;
int gEdgeCount;
 
void fileInput(void);
void printDistance(int* distnace);
void printGraph(vector<pair<int, int>>* vertex);
 
 
void fileInput(void)
{
    int tempStartVertex = 0;
    int tempEndVertex = 0;
    int tempWeight = 0;
    ifstream inputFile("graph_input.txt");
    
    inputFile >> gVertexCount;
    inputFile >> gEdgeCount;
    inputFile >> gStartVertex;
 
    for (int i = 0; i < gEdgeCount; i++)
    {
        inputFile >> tempStartVertex;
        inputFile >> tempEndVertex;
        inputFile >> tempWeight;
        gVertex[tempStartVertex].push_back(make_pair(tempEndVertex, tempWeight));        
    }
 
}
 
void printDistance(int* distance)
{
    cout << "distance:" << endl;
    for (int i = 1; i < gVertexCount + 1; i++)
    {
        cout << "d[" << i << "] = " << distance[i] << endl;
    }
}
 
void printGraph(vector<pair<int, int>> *vertex)
{
    cout << "vertex:" << endl;
    for (int i = 1; i < gVertexCount+1; i++)
    {
        cout << "[" << i << "]";
        for (vector<pair<int, int>>::iterator iter = vertex[i].begin(); iter != vertex[i].end(); ++iter)
        {
            cout << "->";
            cout << (*iter).first << "|" << (*iter).second;
        }
        cout << endl;
    }
}
 
int main(void)
{
    fileInput();
    printGraph(gVertex);
    printDistance(gDistance);
 
    gMyPriorityQueue.push(make_pair(0, 5));
    gMyPriorityQueue.push(make_pair(0, 1));
    gMyPriorityQueue.push(make_pair(0, 3));
    gMyPriorityQueue.push(make_pair(0, 2));
    cout << gMyPriorityQueue.top().second;
}