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.
Graph Paths Explained: Node vs Edge Based, Simple Paths, Cycles and DAGs
Posted inComputer Science Data Structures Graphs

Graph Paths Explained: Node vs Edge Based, Simple Paths, Cycles and DAGs

Paths in a graph show how to travel from a start node to a destination. Node-based paths list the nodes visited but cannot distinguish parallel edges with different weights. Edge-based paths use tuples of start node, destination node and weight so every route is exact. Simple paths repeat no edges or vertices. Cyclic paths start and end on the same node and prove the graph is cyclic. A DAG is a directed acyclic graph with no cycles. These ideas prepare for graph algorithms.