Graphs
Modified 2023-07-02
- cycle
start at node, follow the links, end back at the initial node
- acyclic
no cycles
- connected
every node has path to another node
- directed
if the links have specific directions (Twitter)
- undirected
links can go both ways
- weighted
edges of weights associated with them (Google Maps)
- dag
directed, acyclic graph
- node
point or vertex on the graph
- edge
connection between two nodes
- O(V * E)
checking all vertices, and on every vertex check every node
(1) --- (4) ---- (5)
/ | | /|
(0) | ------|------- |
\ |/ | |
(2) --- (3) ---- (6)
BFS on Adjacency Matrix
The adjacency matrix is a matrix with weighted edges to each node on the graph. It's one way to represent a graph.
Typescript
The graph represented as a 2D array:
const matrix2 = [
[0, 3, 1, 0, 0, 0, 0], // 0
[0, 0, 0, 0, 1, 0, 0],
[0, 0, 7, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 5, 0, 2, 0],
[0, 0, 18, 0, 0, 0, 1],
[0, 0, 0, 1, 0, 0, 1],
];We have to keep track of the path as well when walking through the matrix.
export default function bfs(graph: WeightedAdjacencyMatrix, source: number, needle: number): number[] | null {
const seen = new Array(graph.length).fill(false)
const prev = new Array(graph.length).fill(-1)
seen[source] = true
const q: number[] = [source]
do {
const curr = q.shift()!
if (curr === needle) {
break;
}
const adjs = graph[curr]
for (let i = 0; i < graph.length; ++i) {
if (adjs[i] === 0) continue
if (seen[i]) continue
seen[i] = true
prev[i] = curr
q.push(i)
}
seen[curr] = true
} while (q.length) {
let curr = needle
const out: number[] = []
while (prev[curr] !== -1) {
out.push(curr)
curr = prev[curr]
}
if (out.length) {
return [source].concat(out.reverse())
} else {
return null
}
}
}DFS on Adjacency List
function walk(graph: WeightedAdjacencyList, curr: number,
needle: number, seen: boolean[], path: number[]): boolean {
//base
if (seen[curr]) return false
seen[curr] = true
path.push(curr) //pre
if (curr === needle) {
return true
};
//recurse
const list = graph[curr]
for (let i = 0; i < list.length; i++) {
const edge = list[i]
if (walk(graph, edge.to, needle, seen, path)) {
return true
};
}
path.pop() //post
return false
}
export default function dfs(graph: WeightedAdjacencyList, source: number, needle: number): number[] | null {
const seen = new Array(graph.length).fill(false)
const path: number[] = []
walk(graph, source, needle, seen, path)
if (path.length === 0) return null
return path
}