GRAPHS Flashcards
What is graph
Mathematically, a graph is a set V of vertices and a set E of edges, such that each edge in E connects two of the vertices in V
We use node as a synonym for vertex
Draw unlabeled, labeled and weighted graphs
*See notes for graph
When are vertices adjacent to each other?
One vertex is adjacent to another vertex if there is an edge connecting the two vertices (neighbors)
What is a path?
Sequence of edges that allows one vertex to be reached from another vertex in a graph
What is the length of a path and the degree of a vertex?
Length of a path: Number of edges on the path
Degree of a vertex: Number of edges connected to it
Define and illustrate simple path and cycles
Simple path: Path that does not pass through the same vertex more than once
Cycle: Path that begins and ends at the same vertex
When is a graph said to be connected?
A graph is connected if there is a path from each vertex to every other vertex
*See notes for pic
When is a graph said to be complete?
A graph is complete if there is an edge from each vertex to every other vertex
What are the two types of graphs? Illustrate each
Graphs can be undirected or directed (digraph)
*See notes for pic
Define: Directed edges and incident edges
A directed edge has a source vertex and a destination vertex
Edges emanating from a given source vertex are called its incident edges
How does one convert an undirected graph to a directed graph
To convert undirected graph to equivalent directed graph, replace each edge in undirected graph with a pair of edges pointing in opposite directions
What is a DAG?
A special case of digraph that contains no cycles is known as a directed acyclic graph, or DAG
Give examples of graph applications?
A roadmap
A map of airline routes
A schematic of the computers and connections that make up the Internet
The links between pages on the Web
The relationship between students and courses i.e courses and their pre-requisites
A diagram of the flow capacities in a communications or transportation network
What are the common ways to represent graphs?
The adjacency matrix
The adjacency list
What is an adjacency list?
The adjacency list for the graph is an array of N linked lists
Each individual list shows what vertices a given vertex is adjacent to.
Adjacency list shows which vertices are adjacent to—that is, one edge away from—a given vertex, not paths from vertex to vertex.
*See notes for illustration
What are the different types of graph traversal
A depth-first search (DFS), uses a stack
A breadth-first search (BFS), uses a queue
List the rules of Depth First Search
RULE 1: If possible, visit an adjacent unvisited vertex, mark it, and push it on the stack
RULE 2: If you can’t follow Rule 1, then, if possible, pop a vertex off the stack.
RULE 3: If you can’t follow Rule 1 or Rule 2, you’re done
List the rules of Breadth First Search
1: Visit the next unvisited vertex(if there is one) that’s adjacent to the current vertex, mark it and insert it into the que
2: If you can’t carry out rule 1 because there are no more unvisited vertices remove a vertex from the queue(if possible) and make it the current vertex
3: If you can’t follow Rule 1 or Rule 2, you’re done
Describe the minimum spanning tree
Subset of edges whose sum of edge weights is as small as possible
In a weighted graph, you can sum the weights for all edges in a spanning tree and attempt to find a spanning tree that minimizes this sum
There are several algorithms for finding a minimum spanning tree for a component.
For example, to determine how an airline can service all cities, while minimizing the total length of the routes it needs to support
Describe the topological sort
A directed acyclic graph (DAG) has an order among the vertices
A topological order assigns a rank to each vertex such that the edges go from lower- to higher- ranked vertices
Topological sort: process of finding and returning a topological order of vertices in a graph
*See notes for examples
What is a subgraph?
A subgraph consists of a subset of a graph’s vertices and a subset of its edges
Write down java code to create a graph
*See notes for code
Discuss two types of algorithms that have been used by taxi hailing applications to improve the customer experience today
Dijkstra’s search algorithm to find out the best route
DFS to find shortest route
