Hi, I'm new to graphs, and I need to build one. The graph is a weighted graph that holds some number of city names with edges linking them together. Each edge will have a weight (hopefully) equivalent to the driving distance between the two places.
As for functionality, the user should be able to set a starting point and a destination, and then the function should send back the shortest route between the two.
I understand a little bit about pointers (although I'm not great with them), and I know how to set up a node (for example, like the nodes one would find in a binary search tree). In fact... I probably already know everything I need to know to actually do this, but I'm having trouble putting it all together.
You start by creating a graph class.
The graph can be represented using either adjacency list representation or matrix representation. The later uses more memory but allows for looking up edges connected to each vertex in O(1) time.
a vertex is dependent on the representation of the graph.
for adjancecy list, the vertex will hold:
- list of all vertices it is pointing to
- shortest distance from itself to source
for matrix representation:
- shortest distance from itself to source
finally to implement shortest distance algorithm you have some options:
- breadth first search (BFS)
- Dijkstra's shortest path algorithm
- Bellman Ford algorithm
To really understand graph theory, you have to learn some of the terms usually associated with graphs, especially these:
Alright... I think I understand all the graph terms reasonably well, I just don't really know how to apply any of that information. Am I right in assuming that the vertex and edges need to be classes/structs within the graph class?
If so, I'm thinking the vertex and edge should look something like this:
1 2 3 4 5 6 7 8 9
struct vertex{
string city; //holds the city name
vector<edge> edgeName[arrSize];
};
struct edge{
string city; //This one holds the name of the city at the other end of the edge
int distance; //weight of the edge
};
class graph{
public:
graph();
~graph();
vertex *point = new vertex[MAX];
bool searchGraph(string); //searches the vertex array for a match.
//If no match, returns false.
void setPointA(string);
void setPointB(string;
string findRoute(string pointA, string pointB);
//This should implement the shortest path algorithm at some point
struct vertex{
string city;
vector<edge> road[MAX];
};
struct edge{
string city;
int distance;
};
private:
string pointA; //Starting point
string pointB; //Target city
};
I'm not really sure where to go from here. I feel like I'm missing something obvious, but I can't figure out what that might be. Any tips?
#include <list> //std::list
#include <utility> //std::pair
typedefstruct vert {
//List of edges connected to current vertex
std::list<std::pair<double, vert&> > edges;
//Smallest distance from source to this node
double distance;
//unique id to use for indexing this vertex
int ID;
} Vertex;