-
Notifications
You must be signed in to change notification settings - Fork 0
/
Graph.h
64 lines (46 loc) · 1.69 KB
/
Graph.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#ifndef GRAPH_H
#define GRAPH_H
#include "Vertex.h"
#include "Edge.h"
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;
#define IN_FINITY 999999
#define visited true
#define unvisited false
class Graph
{
private:
// the head pointer for the linked list of the vertics
Vertex* m_pVHead;
// the number of the vertics
int m_vSize;
public:
/// constructor
Graph();
/// destructor
~Graph();
/// add vertex with vertexNum at the end of the linked list for the vertics
void AddVertex(int vertexKey);
/// add edge from the vertex which the number is startVertexKey to the vertex which the number is endVertexKey
void AddEdge(int startVertexKey, int endVertexKey, int weight);
/// get the vertex which the key is vertexNum
Vertex* FindVertex(int key);
/// get the number of the vertics
int Size() const;
/// memory free for the vertics
void Clear();
/// print out the graph as matrix form
void Print(std::ofstream& fout);
/// check whether the graph has negative edge or not.
bool IsNegativeEdge();
/// find the shortest path from startVertexKey to endVertexKey with Dijkstra using std::set
std::vector<int> FindShortestPathDijkstraUsingSet(int startVertexKey, int endVertexKey);
/// find the shortest path from startVertexKey to endVertexKey with Dijkstra using MinHeap
std::vector<int> FindShortestPathDijkstraUsingMinHeap(int startVertexKey, int endVertexKey);
/// find the shortest path from startVertexKey to endVertexKey with Bellman-Ford
std::vector<int> FindShortestPathBellmanFord(int startVertexKey, int endVertexKey);
std::vector<vector<int> > FindShortestPathFloyd();
};
#endif