4.2.4.1 - Graphs and adjacency representations (VB.NET)
Model relationships as graphs, store their edges in matrices and lists, and choose a representation for a VB.NET solution. This route uses written code with no Run: incomplete: runnable support pending.
Nodes, edges and weighted directed graphs
A graph represents objects and the relationships between them, even when the relationships do not form a simple sequence or hierarchy.
Graph
A collection of vertices (nodes) and edges (arcs) joining pairs of vertices.
In a road model, nodes might be junctions and edges direct road connections. A social network can use people as nodes and friendships as undirected edges. A dependency graph can use tasks as nodes and a directed edge to mean one task depends on another. A graph is this relationship structure, not necessarily a statistical line chart.
An undirected edge joins two nodes in both directions. A directed edge has an indicated source and destination, so A→B does not imply B→A. A weighted graph assigns a value to each edge, such as distance, travel time or cost; the task defines its units and meaning. Node labels identify objects and are not automatically edge weights.
Use this directed weighted example throughout the lesson: A→B has weight 4, A→C has weight 2, B→C has weight 1 and C→A has weight 3. These are four edges, not eight. A and C have edges in both directions with different weights.
[DIAGRAM: asset_slug: graph_routes; description: Directed edges A to B with weight 4, A to C with weight 2, B to C with weight 1 and C to A with weight 3]
Adjacency matrices
An adjacency matrix stores one entry for every possible ordered pair of nodes.
Rows are sources and columns are destinations in the convention below. Use -1 for no edge because all example weights are non-negative. Zero is a possible weight and therefore cannot also mean no edge. No self-edges are supplied, so the diagonal is -1.
| From / to | A | B | C |
|---|---|---|---|
| A | -1 | 4 | 2 |
| B | -1 | -1 | 1 |
| C | 3 | -1 | -1 |
The equivalent VB.NET array is:
Dim weights(,) As Integer = {{-1, 4, 2}, {-1, -1, 1}, {3, -1, -1}}
Map A, B, C to indices 0, 1, 2. weights(0, 1) finds A→B directly. An unweighted matrix can instead use Boolean entries for edge existence. For an undirected graph with one weight per connection, the matrix is symmetric across its diagonal: the two matching entries record the same edge. The directed example is not symmetric.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account