# Graph Agos Flashcards

How to get connected components in undirected graph G

Run DFS and keep track of component #

DFS inputs and outputs

input: G=(V,E) in adjacency list representation

Outputs:

prev[z]: The parent index of vertex z in the DFS visitation

pre[z]:The pre number of the vertex z in the DFS visitation

post[z]: The post number of vertex z in the DFS visitation

ccnum[z]:The connected components number IF vertices are passed in as highest post number

lowest number after running DFS on a reversed directed graph that is processed this way, the ccnum also be the topological sort order in reverse

DFS algorithm

DFS(G): cc = 0 for all v in V, visited(v) = FALSE for all v in V if not visited(v) then c++ explore(v)

DFS Explore

Explore(z) ccnum(z) = cc visited(z) = TRUE for all (z,w) in E: if not visited(w) Explore(w)

Running time for DFS

O(n+m)

How to find a path between connected vertices?

We add an initialization of prev(v) = NULL to the base case for DFS and in Explore we set prev(w)=z after running Explore(w)

We use the prev array to backtrack. For a pair of certices in the same connected component, we can use the prev array to find a path between this pair of connected vertices.

How can we get connectivity info for directed G?

use dfs: add pre/postorder numbers for the tree or forest of explored edges

DFS on directed graphs

DFS(G): clock =1 for all v in V, visited(v) = FALSE for all v in V if not visited(v) then explore(v)

Explore(z) for directed graphs

Explore(z) pre(x) = clock; clock++ visited(z) = TRUE for all (z,w) in E: if not visited(w) Explore(w) post(z) = clock, clock++

Do we use postorder numbers or pre order numbers for directed graphs?

postorder

How is a graph represented?

We can represent a graph by an adjacency matrix; if there are n = |V | vertices v1, . . . , vn, this is an n × n array whose (i, j)th entry is

aij =

1 if there is an edge from vi to vj

0 otherwise.

For undirected graphs, the matrix is symmetric since an edge (u,v) can be taken in any direction.

Tree edges

Part of the forest. post(z) > post(w)

Forward Edges

lead from a node to a nonchild descendant in the DFS tree. Goes down multiple steps. post(z) > post(w)

Back Edges

lead to an ancestor in the DFS tree. The post order number of post(z) < post(w)

Cross Edges

lead to neither descendant not ancestor; they therefore lead to a node that has already been completely explored. post(z) > post(w)

Cycle

A circular path v0->v1->v2….->vk->v0.

G has a cycle iff its DFS tree has a back eddge

How to know if a directed hraph has a cycle?

if its depth first search reveals a back edge

How is a dag linearized?

Decreasing post numbers

DAG

Directed Acylclic graph

No cycles = No back edges

Topologically sort inputs and outputs

Input: Graoh G = (V,E), directed acycic graoh(DAG)

Outut:topo[i]: the vertex number of the ith vetex in topological order from left to right

Topologically sorting runtime

O(n+m)

DAG Structure -

Source Vertex = no incoming edges

Sink Vertex = no outgoing edges

There is always at least one source and one sink

Source Vertex

ight have some outgoing edges, but No incoming edges = highest post #

Sink vertex

Might have some edges in, but it has no outgoing edges = lowest post #

Alternative topological sorting algorithm

1) Find a sink, output it and delete it

2) Repeat 1 until the graph is empty

Connectivity in directed graphs. How do we know v and w are strongly connected?

Vertices v and w are strongly connected if:

there is a path v->w and w->v

SCC

Strongly connected component

Maximal set of strongly connected vertices

How do we know a vertex is in a sink in a dag?

It has the lowest post order #

Does the vertex with a the lowest order # for a general graph exist in a sink

no

what characteristic of v will cause to live in a source for a general directed graph

highest post number