Suggest edit — graph

Title

Name

Note

---
title: "graph"
type: concept
source: https://www.jemoka.com/posts/kbhgraph/
confidence: high
status: active
---

undirected graph constituents vertices&rsquo;s \(V\), a set of values of node edges \(E\), a set of unordered sets of verticies requirements We write:
\begin{equation} G = \qty(V, E) \end{equation}
We say:
degree of vertex is the number of edges coming out connected verticies are neighbors additional information directed graph constituents vertices&rsquo;s \(V\), a set of values of node edges \(E\), a set of directed edges requirements We write:
\begin{equation} G = \qty(V, E) \end{equation}
We say:
in-degree of vertex is the number of edges coming out out-degree of vertex is the number of edges coming in incoming neighbor are the neigbors that come in outgoing neighbor are the neigbors that are pointed towards representing graphs adjacency matrix source in rows, destinations in columns (conventions here is the transpose of the random walk convention).
adjacency list One array for the vertices, each coming with a linked list where each link is an edge. Then from there each link points to the adjacency lists.
class AdjacencyListElement; class EdgeListElement; class AdjacencyListElement { public: EdgeListElement* elem; }; class EdgeListElement { public: Tuple&lt;AdjacencyListElement*, AdjacencyListElement*&gt; edges; EdgeListElement* next; }; Vector&lt;AdjacencyListElement&gt; AdjacancyList; Tuples gives order, or sets gives no order
basic operations and their time For \(N\) verticies and \(M\) edges
Operation Adjacency Matrix Adjacency List Edge membership \(O\qty(1)\) \(O\qty(deg\qty(v))\), \(O(deg(w))\), \(O\qty(M)\) Neighbor query \(O\qty(n)\) \(O\qty(deg\qty(v))\) Space needed \(O\qty(n^{2})\) \(O\qty(n+m)\)