Directed graph with distances
Hi everyone) How can I implement a graph oriented with vertex distances. I.e ., the input is vertex A, vertex B, and the distance between them is 6. And B C is the distance between them is 3. And A C the distance between them is 1.
4 answers
Please specify what it means to implement? Imagine in memory? Then in the simplest case (if not a very large graph - and most likely in the training task so), it is enough to have an adjacency matrix with weights, in which at the intersection of row I and column J will be located the weight-cost of the transition from I to J. Weight can mean anything, including distance (the semantics are determined by the task).
The matrix for your example might look like this if, as you wrote, the graph oriented, i.e. since it is not explicitly written that from B you can get to A, we believe that you can not:
0 6 1
0 0 3
0 0 0
Or so, if you still assume the existence of inverse arcs of the graph:
0 6 1
6 0 3
3 1 0
In this case, zero denotes the absence of an arc. If the task implies the possibility of an "instantaneous transition" or the presence of a zero-cost path, then the absence should be denoted differently to avoid collisions. For example, if negative weight arcs are not possible within the meaning of the problem (when you pay for travel on this arc), you can take -1. In short, everything depends very much on the specifics of the task.
Larger graphs that have a special structure may require more interesting data structures. Here it remains to advise you to arm yourself with a good book on algorithms - Sedgwick, Corman, etc.
Adjacency list
That is, for example, you have 3 vertices A, B, C
And on each vertex is hung a list of adjacent vertices with the weight of the edge
For vertex A: (B, 6), (C, 1)
For vertex B: (C,3)
For vertex C:-
The vertexes themselves can also be represented as a list (that is, you will get a list of lists)
It is impossible in any way, since 3+1
I would implement it like this:
There is a Vertex class, which contains the name, and an ID; there is an Edge class, which contains 2 ID numbers of vertices, start and end, this is important, because the graph must be inverted, and the length between them.
And there is a Graph class that contains 2 lists:
- list of vertices
- list of edges
Draw as follows: go through the list of edges and draw them, drawing the corresponding vertices according to the start and end ids.