How to represent a set of arcs as an adjacency matrix and an adjacency table?

Figure representation: Arc to adjacency matrix and adjacency table conversion

This article demonstrates how to convert a set of directed arcs into two common representations of graphs: adjacency matrix and adjacency table. We will use the following arc set as an example:⟨v0,v1 , v1,v1 , v1,v3 , v2,v3 . This set of arcs describes a directed graph with four vertices (v0, v1, v2, v3).

First, let's interpret these arcs:⟨v0,v1 denoted by a directed edge pointing from v0 to v1;⟨v1,v1 denoted by a self-loop on a vertex of v1;⟨v1,v3 denoted by a directed edge pointing from v1 to v3;⟨v2,v3 denoted by a directed edge pointing from v2 to v3.

Adjacent matrix representation:

The adjacency matrix uses a two-dimensional array to represent the graph. The rows and columns of the array correspond to the vertices in the graph respectively. If there is an edge from vertex i to vertex j, the matrix element a _ij is 1, otherwise it is 0. For weighted graphs, a _ij can store the weight of edges.

Based on the given arc set, we can build a 4x4 adjacency matrix:

<code> v0 v1 v2 v3 v0 0 1 0 0 v1 0 1 0 1 v2 0 0 0 1 v3 0 0 0 0</code>

Adjacent table representation:

Adjacent tables are a more space-saving graph representation method, especially for sparse graphs. It uses an array where each element of the array corresponds to a vertex and points to a linked list that stores vertices adjacent to that vertex.

Based on the given set of arcs, the corresponding adjacency table is as follows:

 <code>v0: v1 v1: v1, v3 v2: v3 v3:</code>

This means v0 is connected to v1; v1 is connected to itself (self-loop) and v3; v2 is connected to v3; v3 has no out-of-date edges.

Summary: This article shows how to convert a set of arcs into an adjacency matrix and an adjacency table. These two representation methods have their own advantages and disadvantages. Which method is chosen depends on the specific application scenario and the characteristics of the graph (for example, the sparseness of the graph).

The above is the detailed content of How to represent a set of arcs as an adjacency matrix and an adjacency table?. For more information, please follow other related articles on the PHP Chinese website!