Graph Theory Flashcards
What is a graph??
A graph G is an ordered pair of a se V of vertices and a set E of edges
G = (V, E)
What is an ordered pair?
Two objects where the order matters.
(a,b) != (b,a) unless b === a
What is an unordered pair?
Where the order does not matter.
What are vertices?
Nodes that have arrays that contain in and out edges
How do I represent an edge?
Directed: two points in an order
Undirected: two unordered points
One point is an origin and the second is a destination/
What is the difference between a directed and undirected graph
Directed Graph has all directed edges with ordered pairs
Undirected Graph has all undirected edges with unordered pairs.
Why use a graph? Give an example
Graphs can be used to represent any collection of objects that have a pairwise relationship.
EX: Social network. Friendships are unordered pairs/undirected graphs. By virtue of, friendship works two-way.
EX: Wold Wide Web. This would make use of a directed graph. The pages arent required to link back to each other. Even if the pages go back and forth. it will be a case of using separate in and out edges.
What is weighted vs unweighted
Unweighted - all edges carry the same (none) weight. Weighted graph - all edges may have a different length/value/cost.
How do we create and store a graph in computer’s memory.
1) store all vertices - a list of strings
2) store all edges - (id by its two end points: start and end vertex): A struct Edge (edgelist[max_size])
3) if the graph is weighted, and there is a cost, store the car variable in the edgelist argument.
- This might not be the most cost efficient way to move forward.
- for our edgelists, we want to use pointers to the indexes respective vertices.
What is an adjacency matrix?
cost is heavy when trying to find nodes in a graph if we iterate through an edgelist. To solve this, we can store the edges in a 2D matrix.
Unweighted (and the idx are between 0 and v-1):
Aij = Within this matrix, we can create store Boolean values at the appropriate coordinates if there is indeed an edge between the two vertices.
Finding adjacent nodes:
When scanning the appropriate row, the cost is O(v)
Finding if two nodes are connected:
Look up the values of aij. O(1).
Use extra memory to create a hash table so that lookup is O(1)
however a lot of memory is wasted f the graph is particularly large
row index oftentimes represents the start point
to add an edge, we would flip the 0 to 1 and to delete: vice versa
What is an Adjacency List?
- generally the number of connections is far less than the number of possible connections.
- we want to keep the information that the nodes are connected and get rid of the information that the nodes are not connected.
- index represent nothing and the actual value of the nodes are what represent everything.
- we should use a linkedlist - a tree.
- each row can be a one dimensional array of different sizes
- keep rows sorted so we can perform a binary search which is a lot less costly.
- best example is using a social network.
To add edges, we would have to create a new array and wipe out he old array and port over the pertinent values…. but this is costly. We should use a linked list instead (it’ll have head/value ad a next). BTW, this is all for an unweighted graph. If the graph is weighted, we need to store the weight along side the head and next..
All searching can be one with a binary search tree
Depth First Traversal
1) Requires a stack/recursion
2) Take vertex A and push onto stack and mark it as visited.
3) Push B onto stack and mark as visited. So on and so forth.
4) If there are no adjacent unvisited vertices, pop the vertex off the stack.
Preferred when we want to visit every node in the stack.
Pre-Order and other forms of tree traversal are examples of DFS. Unlike a normal tree, we need to check if we’ve visited the graph.
function dfs(rootNode){
if(root ==== null){
return
}
visit(rootNode);
rootNode.visited = true;
rootNode.adjacent.forEach(e=> n.visited === false ? dfs(n) : )
Breadth First Traversal
*Key difference between DFS and BFS is the data structure used. DFS uses a stack/recursion, BFS uses a queue.
1) visit A
2) Add B to queue and marks as visited, but do not move off A (in other words, visit each of A’s neighbors before moving on)
3) Same with D and so forth. Add those to the queue.
4) Once all of A’s connections are exhausted, we will dequeue B and now start exploring connections from there.
5) Continue onward. If the next queued items have open connections, explore them, otherwise, dequeue and move on to the next.
Preferred when we want to find the shortest (or any) path between nodes.
function bfs(rootNode){
queue = queueDS . (array or linkedlist)
root.marked = true;
queue.enqueue(rootNode);
while(queue.length !== 0){
let r = queue.dequeue()
visit(r)
r.adjacent.forEach(node=> node.marked === false ? node.marked = true; queue.enqueue(node))
}
}
What is a main difference between traversing a tree vs traversing a graph
Because graphs are circular, we will need a boolean property to indicate whether or not a node has been visited in a graph.
Topological Sort
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.
