Graphs Flashcards
Graph Definition
a collection of vertices (or nodes) and the connections between them
simple graph G = (V, E)
consists of a nonempty set V of vertices and a possibly empty set E of edges, each edge being a set of two vertices from V.
The number of vertices and edges is denoted by ___ and ____, respectively.
|V|, |E|
A directed graph, or a digraph, G = (V, E)
consists of a nonempty set V of vertices and a set E of edges (also called arcs), where each edge is a pair of verices from V.
One edge of a simple graph is of the form ___ and ____ = _____
{vi, vj}; {vi, vj} = {vj, vi}
In a digraph, each edge is of the form ___ and ____ != _____
(vi, vj); (vi, vj) != (vj, vi)
Miltigraph
- a graph in which two vertices can be joing by multiple edges
a multigraph G = (V, E, f) is composed of a set of vertices V, a set of edges E, and a function f: E → {{vi,vj} : vi,vj ∈ V and vi != vj}
Pseudograph
a multigraph that allows edges that connect vertices to themselves – these edges are known as loops
Path
a path from v1 to vn is a sequence of edges edge(v1 v2), edge(v2 v3), . . . ,
edge (vn-1 vn) and is denoted as a sequence of vertices v1, v2, v3, . . . , vn-1 , vn
Circiut
a path where v1 = vn and no edge is repeated
Cycle
path where all vertices in a circuit are different
Weighted Graph
A graph where each edge has an assigned number.
The number assigned to an edge is called its weight, cost, distance, length . . . depending on the context
Complete Graph
A graph with n vertices such that for each pair of distinct vertices there is exactly one edge connecting them; that is, each vertex can be connected to any other vertex.
degree of a vertex
The degree of a vertex v, deg(v), is the number of edges incident with v.
isolated vertex
vertex where degree is 0
( deg(v) = 0 )
Adjacent Vertices
Two vertices vi and vj if the edge(vi vj) is in E.
edge(v, w) in E:
* w is said to be adjacent to v
* if graph is undirected then v is also adjacent to w
* such an edge is called incident with the vertices v and w
Subgraph
A subgraph G’ of graph G = (V, E) such that V’ ⊆ V and E’ ⊆ E.
A subgraph _______ by vertices V’ is a graph (V’, E’) such that an edge e ∈ E if ______
induced, e ∈ E’
A path’s length
is the number of edges that compose it
Acyclic Graph (DAG)
A directed graph without cycles
A ____ in a directed graph is a path of lengtha at least __ such that v1 = vn
cycle, 1
Adjacency List
A simple representation of a graph which specifies all vertices adjacent to each vertex of the graph.
Implementations:
- Star representation: list implemented as a table
- Linked List
Adjacency Matrix of Graph G = (V, E)
a binary |V| x |V| matrix indexed form 0 to n-1 such that each entry of this matrix:
aij = 1 if edge ej is incident with vertex vi; 0 otherwise
*Each row i represents vertices adjacent to vertex vi, with
** order of vertices in adjacency matrix is arbitrary; there are n! possible adjacency matrices for the same graph G
An incidence matrix of graph G = (V, E)
Representation of a graph based on the incidence of vertices and edges.
|V| x |E| matrix such that a<strong>ij</strong> =
1 if edge ej is incident with vertex vi
0 otherwise
The density of the edges in a graph should drive the choice of adjacency representation: sparse, use _____; dense use ______
list, matrix
Two primary ways to traverse a graph
Depth-first search
Breadth-first search
Deapth-First Search
- each vertex is visited and then all the unvisited vertices adjacent to that vertex are visited
- If the vertex has no adjacent vertices, or if they have all been visited, we backtrack to that vertex’s predecessor
- This continues until returning to the vertex where the traversal started
- If any vertices remain unvisited at this point, the traversal restarts at one of the unvisited vertices
* “last visited, first explored” strategy (think stack)
Depth First Search Pseudocode (Recursive)
void Graph::dfs( Vertex v )
{
v.visited = true;
for each Vertex w adjacent to v
if ( !w.visited )
dfs( w );
}Depth First Search Implentation (Recursive)
vod DFS( Graph* G, int v )
{
PreVisit(G, v);
G->setMark(v, VISITED);
for (int w=G->first(v); w < G->n(); w = G->next(v,w))
if (G->getMark(w) == UNVISITED)
DEF(G, w);
PostVisit(G, v);
}Depth First Search Pseudocode (Iterative)
DFS(vertex s)
S = new stack
S.push(s)
while not S.empty
pop v from S
if not v.visited
v.visited = true
foreach edge(v, u)
if not u.visited
S.push(u)Breadth-First Search
- BFS places vertices in a queue as they are visited
- The first vertex in the queue is then removed, and the process repeated
- No visited nodes are revisted
- if a node has no accessible nodes, the next node in the queue is removed and processed
* “first visited, first explored” strategy (think queue)
BFS Pseudocode
BFS(vertex s)
Q = new queue
Q.enqueue(s)
s.visited = true
while not Q.empty
v = Q.dequeue
if not v.visited
v.visited = true
foreach edge (v, u)
if not u.visited
u.visited = true
Q.enqueue(u)BFS Implementation
void BFS(Graph* G, int start, Queue< int >* Q)
{
int v, w;
Q->enqueue(start);
G->setMark(start, VISITED);
while (Q->length() != 0) // Process all vertices on Q
{
v = Q->dequeue();
PreVisit(G, v);
for (w = G->first; w < G->n(); w = G->next(v, w))
if (G->getMark(w) == VISITED)
{
G->setMark(w, VISITED);
Q->enqueue(w);
}
}
}Dijkstra’s Algorithm is . . .
The general method to solve the single-source shortest-path problem
Two classic algorithms for finding MST of a graph
- Prim’s Algorithm
- Kruskal’s Algorithm
Spanning Tree of a graph G is . . .
a tree (=no cycles) that includes:
- All vertices of the G
- some or all of the edges G
Topological Sorting
Given an acyclic digraph G = (V, E), find a linear ordering of vertices such that:
for all edges (v, m) in E, v precedes w in the ordering.
