Graph Algos:

Know when to use adjacency list vs adjacency matrices: mostly adjacency lists are used

Directed and undirected graphs: Undirected have vertex linked to both the nodes i.e. we need to insert edge for both nodes

Initialization of graph will set edge matrix to null, degree matrix to zero, number of vertices to zero.

Edgenode data structure is created which saves the node, weight of edge and the next edgenode reference.

Reading the graph:

Insert the edge into the graph that we just initialized:

Inserting takes the graph object, nodes and directed FLAG.

We make an edgenode structure instance, allocate memory for it, give info about edge it’s connected to, set wt to NULL.

The next edgenode reference is given to the edges list for the node.

Edge list of the node is updated by appending the new edgenode to the list at start.

Now degree is increased by 1. If directed, another insert edge is done with x and y node reversed.

Now number of edges is also increased for graph.

Printing the graph:

For i in number of vertices in graph:

get the i’th edgenode.

While we get some edgenode:

Get the next node for i’th edgenode.

Breadth first search:

Parent list maintained in bfs can be used to calculate the path to the top. This must be done from bottom towards up.

Connected components: Is a maximal set of vertices such that there is a path between every pair of vertices.

Can be done using discovered nodes list: you take a node, find all that are connected to it via BFS. Then go to unexplored node and do that thing again. Need to have a componentID which marks new component when one BFS finishes.

Bipartite graphs can be verified by making small modification to BFS where we change the color of a node as we process any edge present in graph. If both nodes have same color assigned to them, we can set one node’s color as complement of another node.

Depth First Search:

It uses concept of time as an element in graph.

It uses stack as element for storing nodes to process.

Time changes as we enter or exit any vertex. We keep track of entry and exit time for each vertex.

It can be used without need of stack using recursive implementation.

Set state of node to undiscovered

Process vertex if anything you want to do

Entry time of node is entered into entry list

increment time by 1

for each edge in adjacency list do :

process edge if desired

if state of node with which we have edge is undiscovered then do DFS of the node

Mark the node as Processed

mark exit time in list of exit times

Increment time by 1 again.

Why use time intervals:

Know who is an ancestor in the graph: We cannot exit an ancestor before child in DFS. So, time interval of child must be nested within ancestor.

How many descendants: The difference between entry and exit time for parent divided by two will mark number of descendants.

In case of DFS, we need to be able to do different tasks on entry and exit of a node. So , we have two functions namely process edge early and process edge late for our applications that we require.

Depth first tree partitions tree into:

Back edges:

Tree edges: Discovers new edges

Cycles are easy to be found using DFS: By modifying the process edge function.

Articulation vertex or cut node: Having an articulation matrix makes the graph extremely fragile.

Connectivity of a graph is the smallest number of vertices’s whose deletion will disconnect the graph.