# Graphs

## Terminology

| `node`       | A point or vertice on the graph. *(Also stated as* `V`*)*                                                                                                                                                                               |
| ------------ | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| `edge`       | The connection between two nodes. *(Also stated as* `E`*)*                                                                                                                                                                              |
| `connected`  | When every node has a path to another node.                                                                                                                                                                                             |
| `cycle`      | When you start at $$Node\_X$$, follow the links, and end back at $$Node\_X$$. *(Can't be only 2 nodes)*                                                                                                                                 |
| `acyclic`    | A graph that contains no `cycles`.                                                                                                                                                                                                      |
| `directed`   | <p>When there is a direction to the connections. <br><em>(This helps making asymetric connections, Ex.:</em> <span class="math">A \rightarrow\_{10} B</span> <em>but</em> <span class="math">B \rightarrow\_{20} A</span><em>)</em></p> |
| `undirected` | Not `directed`. *(The default) (Ex.:* $$A \rightarrow B$$ *has the same* `weight` *as* $$B \rightarrow A)$$                                                                                                                             |
| `weighted`   | The edges have a weight associated with them.                                                                                                                                                                                           |
| `dag`        | Directed, acyclic graph.                                                                                                                                                                                                                |

## Representing Graphs

### Adjacent List

A list, where each main index of the list points to a node of the graph, describing its connections to the other nodes.

{% hint style="info" %}
This representation is more commonly used.
{% endhint %}

<img src="https://977358640-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FgbsUv4FfxUwe5ihs1aG5%2Fuploads%2FJRI2BboBFsydsYhqy1ue%2Ffile.excalidraw.svg?alt=media&#x26;token=87df1833-7473-4a64-bb3e-fd37ca1dc515" alt="" class="gitbook-drawing">

```typescript
// Default one as Above
type WeightedAdjList = {
    to: number;
    weight: number;
}[][]

// An adaptation to include `seen`
interface WeightedAdjNode {
    seen?: boolean;
    edges: {
        to: number;
        weight: number;
    }[]
}
type WeightedAdjListWithSeen = WeightedAdjNode[];
```

#### Traversing/Searching with `BFS`

```typescript
function bfs(graph: WeightedAdjListWithSeen, source: number, needle: number): boolean {
    const queue: number[] = [source];
    
    while (queue.length) {
        const currNode = queue.shift();
        if (currNode === needle) return true;
        graph[currNode].seen = true;
        for (let neighbor of graph[currNode].edges) {
            if (!graph[neighbor.to]?.seen) queue.push(neighbor.to);
        }
    }
    return false;
}
```

#### Traversing/Searching with `DFS`

Easier to preserve the `path`.

{% hint style="info" %}
Runs on $$O(V+E)$$.
{% endhint %}

```typescript
function dfs(graph: WeightedAdjListWithSeen, source: number, needle: number): boolean {
    const stack: number[] = [source];
    
    while (stack.length) {
        const currNode = stack.pop();
        if (currNode === needle) return true;
        graph[currNode].seen = true;
        for (let neighbor of graph[currNode].edges) {
            if (!graph[neighbor.to]?.seen) stack.push(neighbor.to);
        }
    }
    return false;
}
```

### Adjacent Matrix

A matrix, where each main index of the first array points to a node of the graph, describing in a second array the weights to the other nodes or `zero` if there is no connection.

{% hint style="danger" %}
Uses more memory, since it represents non-existent connections with `zero`.
{% endhint %}

<img src="https://977358640-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FgbsUv4FfxUwe5ihs1aG5%2Fuploads%2FJ2hBOBMmoiLhM15TwHXb%2Ffile.excalidraw.svg?alt=media&#x26;token=ecac5671-9edd-433a-9d76-68a032de33f9" alt="" class="gitbook-drawing">

#### Traversing/Searching with `BFS`

```typescript
type WeightedAdjMatrix = number[][];

function bfs(graph: WeightedAdjMatrix, source: number, needle: number): boolean {
    const queue: number[] = [source];
    const seen: boolean[] = new Array(graph.length).fill(false);
    
    while (queue.length) {
        const currNode = queue.shift();
        if (currNode === needle) return true;
        seen[currNode] = true;
        for (let neighbor=0; neighbor < graph[currNode].length; neighbor++) {
            if (graph[currNode][neighbor] !== 0 && !seen[neighbor]) queue.push(neighbor);
        }
    }
    return false;
}
```