undirected graph

constituents

• vertices’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’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<AdjacencyListElement*, AdjacencyListElement*> edges;
    EdgeListElement* next;
};

Vector<AdjacencyListElement> AdjacancyList;

Tuples gives order, or sets gives no order

basic operations and their time

For \(N\) verticies and \(M\) edges