graphs

vertex

node in the graph

edge

connection between two vertices

bipartite

can be split into 2 groups with no internal edges

use bfs with 2 colors to test, if no adjacenent nodes have same color it is biparttie

acylic

no cycles

cylic

at least one cycle

DAG

direct acylic graph

how do trees connect to DAGs

trees are special DAGs with exactly 1 path between any 2 nodes (ie do not go both dirs)

minimum edges in connected graph with n vertices

n-1

its connected, so every vertex is connect vro

how does depth fs detect cycle

visiting node that already is in recursion stack

how does breadth fs detect cycle

if visits node that isnt parent

is every tree bipartite

yes, trees are acyclic so always bipartite

can complete graph be bipartite

only if it has 2 vertices/nodes

is every DAG a tree?

no, DAGs can have multiple roots and disconnected components

Can a graph be both directed and cyclic?

yes bro… thats what a cycle is (question was copied directly vro… did not copy it wrong)

weighted graph

every edge has a numerical value

unweighted graph

edges have no numerical value

directed graph

edges have direction

undirected graph

edges go both ways (a-b == b-a)

loop

edge that connects a vertex to itself

simple graph

no loops, no duplicate edges

connected graph

each vertex is reachable from every other vertex eventually

does NOT mean an edge exists between each vertex, rather a PATH exists between each

complete vertex

every vertex is DIRECTLY connected to every other vertex

an edge DOES EXIST between EACH vertex

adjacency matrix

2d array stores edge connections

space complexity o(V²)

what does a symmetric AM mean

means undirected graph

BFS uses what data structure

queue

DFS uses what structure

stack (either literal or call stack thru recursion)

BFS define

level by level, outward from the path

DFS define

deep along one path before backtracking and branching out the paths until get back to the root

BFS use case

shortest path in unweighted graph

DFS use case

path finding, cycle detection

can a directed graph be connected

yes, if there is a path between all nodes

what does diagonal 1 mean in AM

loop

max edges in complete undirected graph with n vertices

n(n-1)/2

what if DFS is implemented with a queue

becomes a BFS