Possible Route
- Breadth-First Search; BFS
- Depth-First Search; DFS
Minimum Spanning Tree- Kruskal Algorithm
- Prim Algorithm
Single Source Shortest Path
- Bellman-Ford Algorithm
- Dijkstra Algorithm
All Pair Shortest Path
- Floyd-Warshall Algorithm
- Johnson Algorithm
Maximum Flow
- Ford-Fulkerson Method & Edmonds-Karp Algorithm
- Push Relabel Method & Relabel to Front
Graph
G=(V,E)
- 인접 리스트의 집합 ;
|E|<<|V|2 로 낮은 밀도에서 효율적
- 인접 행렬 ;
|E|∼|V|2 로 높은 밀도이거나 빠른 속도로 두 정점을 연결하는 간선을 찾을 때 효율적
Adjacency-list Representation (Undirected)
#include <iostream>
using namespace std;
struct Node{
int value;
Node* next=nullptr;
Node(int _value): value(_value) {}
};
struct adjList{
Node** aL;
int vN, eN;
adjList(int _vN, int E[][2], int _eN): vN(_vN), eN(_eN){
aL=new Node*[this->vN];
for(int i=0; i<this->eN; ++i){
Node* nN1=new Node(E[i][1]);
Node* nN2=new Node(E[i][0]);
if(aL[E[i][0]-1]==nullptr){
aL[E[i][0]-1]=nN1;
} else {
Node* tmp=aL[E[i][0]-1];
aL[E[i][0]-1]=nN1;
nN1->next=tmp;
}
if(aL[E[i][1]-1]==nullptr){
aL[E[i][1]-1]=nN2;
} else {
Node* tmp=aL[E[i][1]-1];
aL[E[i][1]-1]=nN2;
nN2->next=tmp;
}
}
}
};
int main(void){
int E[7][2]={
{1, 2},
{1, 5},
{2, 5},
{2, 4},
{4, 5},
{2, 3},
{3, 4}
};
adjList* list=new adjList(7, E, 7);
return 0;
}
Adjacency-Matrix Representation (Undirected)
struct adjMatrix{
bool* matrix;
int nV, nE;
adjMatrix(int _nV, int E[][2], int _nE): nV(_nV), nE(_nE){
matrix=new bool[this->nV*this->nV];
for(int i=0; i<this->nV*this->nV; ++i) matrix[i]=false;
for(int i=0; i<this->nE; ++i){
matrix[E[i][0]*this->nV+E[i][1]]=true;
matrix[E[i][1]*this->nV+E[i][0]]=true;
}
}
};
int main(void){
int E[7][2]={
{2, 4},
{5, 7},
{1, 3},
{8, 9},
{1, 2},
{5, 6},
{2, 3}
};
adjMatrix* matrix=new adjMatrix(7, E, 7);
return 0;
}