121 Week 18 - Graphs Flashcards
Graph
A set of nodes (or vertices) and edges (or arcs or links)
Simple graph
A graph that has no self-loop.
If a graph has a self-loop, graph analysis calculations change.
Directed and undirected graphs
Undirected graph: edges can be traversed either way.
Directed graph: each edge can only be traversed in its specified direction.
Natural setting for a graph
Integers for edges called weights.
Names for nodes called identifiers.
Hypergraph
A graph with nodes and hyperedges that capture k-wise relationships where k>2.
Why are graphs useful
They represent the concept of entities and relationships where relationships are pair-wise relationships.
E.g., graphs can represent the internet, social media networks, transit systems, artificial neural networks.
Subgraph
A subset of a graph G which contains some nodes and edges from G.
Induced subgraph
A subset of a graph G which contains some nodes and all edges that connect these nodes.
Spanning subgraph/tree
A spanning subgraph is a subset of a graph G which contains all the nodes in G and some edges.
A spanning tree is a spanning subgraph where all nodes are connected, there are no cycles and, where n is the number of nodes, there are n-1 edges.
Minimum spanning tree
A spanning tree with the minimum total sum of edge weights.
Complementary graph
A subset of G which includes all nodes in G and all edges that are not in G.
Can be found by creating a graph with all nodes from G and edges connecting every node to all other nodes then removing all edges in G.
Density of a graph
A value between 0 and 1 that represents how well connected the graph is.
Density for undirected = 2e/n(n-1)
Density for directed = e/n(n-1)
Connectivity in undirected graphs
A undirected graph is connected if there is a path between any 2 vertices.
Connectivity in directed graphs
A directed graph is strongly connected if any node can be reached from any other node.
A directed graph is weakly connected if it is not strongly connected but its undirected version is connected
Graph ADT operations
void addNode(Node n)
void removeNode(Node n)
void addEdge(Node n, Node m)
void removeEdge(Node n, Node m)
boolean adjacent(Node n, Node m)
Node[] getNeighbours(Node n)
Representing graphs through lists
A graph can be represented as a list of lists. Each list item is made up of a list where the first element is the name of the node and the second element is a list of its adjacent nodes.
Time and space complexity of using lists
Time complexity:
- Adding node: O(1).
- O(N) for removing and finding nodes
- O(N) for adding and removing edges
- O(N) for adjacency check
Space complexity: O(N+E) for graphs with N nodes and E edges.
Lists are memory efficient but are not time efficient.
Representing graphs through an adjacency matrix
A graph can be represented using a 2D array where each dimension is the number of nodes in the graph.
An element A[i][j] will be 1 if there is an edge between node i and node j and 0 if there is no edge.
An adjacency matrix is symmetric for undirected graphs: A[i][j] = A[j][i].
Modifying an undirected graph will change 2 cells. Modifying a directed graph will change 1 cell.
Rows and columns in an adjacency matrix
The sum value of a collum in the matrix represents how many edges go into this node.
The sum value of a row in the matrix represents how many edges go out of this node.
Time and space complexity of using adjacency matrix
Time complexity:
- O(N2) for adding a node.
- O(N2) for removing and finding nodes
- O(1) for adding and removing edges
- O(1) for adjacency check
Space complexity: O(n^2).
Adjacency matrices are time efficient but not memory efficient.
Graph traversals
Graph traversals are used to discover whether, from a source node S, you can reach a specific node V and what the shortest path between the two nodes is.
Depth first search traversal (DFS)
- Start at the source, and visit a neighbour (and mark it as visited),
- From that neighbour, visit one of its neighbours.
- Repeat until you hit an already visited node.
- At which point, you backtrack (i.e., go back), and visit another neighbour instead.
- Until you go back to the source.
A stack can be used to keep track of the nodes to be visited next.
Breadth first search traversal (BFS)
- Start at the source.
- Visit all nodes at distance 1 from source.
- Visit all nodes at the distance from source of depth.
- Repeat step 3 until all nodes have been visited.
A queue can be used to keep track of the nodes to be visited next.
When a BFS traversal is done, the traversed edges form a BFS tree. BFS trees give the shortest path from s, assuming now edge weights.
