Representing a Directed Unweighted Graph with an Adjacency Matrix
Posted inComputer Science Data Structures Graphs

Representing a Directed Unweighted Graph with an Adjacency Matrix

A directed unweighted graph can be stored in an adjacency matrix where each row is a starting node and each column is an ending node. A value of 0 means no edge and 1 means an edge exists. Because the structure is really a contiguous one dimensional array under the hood, reading or writing any cell is constant time. Self connections are not implied unless explicitly added, and the matrix is not symmetric the way an undirected graph matrix would be.
How to Represent an Undirected Unweighted Graph with an Adjacency Matrix
Posted inComputer Science Data Structures Graphs

How to Represent an Undirected Unweighted Graph with an Adjacency Matrix

Represent an undirected unweighted graph as an adjacency matrix of ones and zeros. A one in the cell at row i and column j means an edge exists between those nodes. Because the graph is undirected the matrix is symmetric across the diagonal. Changing a cell from zero to one adds an edge and changing it back removes the edge. Self-loops appear on the diagonal. This representation stores only the connection relationships and supports constant-time edge checks.
How to Represent Undirected Weighted Graphs Using Edge Lists
Posted inComputer Science Data Structures Graphs

How to Represent Undirected Weighted Graphs Using Edge Lists

Learn the edge list representation for undirected weighted graphs. Build a vertex list and an edge list of triples that store both endpoints and the weight of each edge. Convert the list to use indexes so node lookups become constant time when the vertices are stored in a vector or array. This approach keeps each undirected edge only once and improves the speed of operations that need both edges and nodes.