0
$\begingroup$

I've been reading: https://en.wikipedia.org/wiki/Adjacency_list

enter image description here

It says that that graph can be constructed with the list $\{b, c\}, \{a, c\}, \{a, b\}$.

However, what if I wanted to construct a directional list? Does $\{b, c\}$ point to $b$ or $c$?

How can you use a list to represent a directional graph?

$\endgroup$
2
$\begingroup$

Your graph is actually undirected. The notation is a list of edges in the graph. Since edges are undirected, each edge is a set of two vertices. Your lists contains three edges, since a triangle has three edges. It actually contains all possible edges involving the vertices $a,b,c$.

A directed graph is one in which edges consist of two ordered vertices. The edge points from the first vertex to the second. You can represent such a graph using a list of pairs.

Adjacency lists are a different data structure, which is described in the Wikipedia page you link to, so I skip its description here. It can be used for both undirected and directed graphs, in the natural way.

$\endgroup$
2
$\begingroup$

Does $\{b,c\}$ point to $b$ or $c$?

Neither. The adjacency list representation of a graph, you are given, for each vertex $x$, a list of the vertices adjacent to $x$. Thus, the lists $\{b,c\}$, $\{a,c\}$, $\{a,b\}$, tell you that $a$ is adjacent to $b$ and $c$, $b$ is adjacent to $a$ and $c$ and $c$ $is$ adjacent to $a$ and $b$.

You shouldn't confuse this with the notation $\{x,y\}$ for the undirected edge connecting $x$ and $y$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.