4.2.4.1 - Graphs and adjacency representations (C#)
Represent relationships as graphs, convert between adjacency matrices and lists, and choose a representation for a C# solution. This route is incomplete: runnable support pending; source questions are written practice with no Run.
Nodes, edges and weighted directed graphs
A graph models relationships that need not form a simple sequence or hierarchy.
Graph
A graph consists of vertices (nodes) and edges (arcs) joining them. A directed edge has an orientation; an undirected edge connects in both directions. In a weighted graph, each edge has an associated value such as distance, time or cost.
For a road network, nodes can be junctions and edges roads. A one-way road needs direction; its travel time can be a weight. In a social network, nodes are users and edges may represent friendship or directed follows. The meaning of an edge and its weight must be stated; a larger weight does not automatically mean a stronger relationship.
Our directed weighted graph has three nodes A, B and C and four arcs: A→B weight 4, A→C weight 2, B→C weight 1 and C→A weight 3. A→B does not imply B→A. The two arcs between A and C have different directions and weights. There is no self-loop in this example. A graph can contain cycles: A→C→A returns to the start.
[DIAGRAM: asset_slug: graph_representations; description: Directed weighted graph with A to B weight 4, A to C weight 2, B to C weight 1, and C to A weight 3]
Adjacency matrices
An adjacency matrix uses one row and one column for every node so a pair of indexes identifies an edge.
Use node order A, B, C, with rows as sources and columns as destinations. In this example zero means no arc, and every real weight is positive:
| From/to | A | B | C |
|---|---|---|---|
| A | 0 | 4 | 2 |
| B | 0 | 0 | 1 |
| C | 3 | 0 | 0 |
The C# rectangular array is int[,] weights = { {0,4,2}, {0,0,1}, {3,0,0} };. weights[0,1] is 4, but weights[1,0] is 0. An undirected weighted graph would have equal mirrored entries because each connection works both ways. For an unweighted graph, a Boolean matrix can record only presence/absence. If zero-weight edges are allowed, zero cannot also be the no-edge marker: use a separate Boolean presence matrix or a representation with a distinct absence value.
For nodes, the matrix stores cells even when few edges exist. Checking one specified pair is a direct array access. Finding all outgoing neighbours requires scanning the source row, including absent edges.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account