Graphs Flashcards
(25 cards)
What are graphs?
An ADT comprised of a network of nodes connected by edges used to model complex relationships between entities
What is a node?
Part of a graph that represents objects or entities
What is an edge?
Part of a graph that represents a relationship between entities
What is a weight in a graph?
A data value used to describe/label an edge.
What are the uses of graphs
Modelling and representing:
- Human (social) networks
- Transport networks , including road and rail networks
- Connections between devices on a network
- Planning telecommunications networks
What is an undirected graph?
A graph in which each relationship between nodes is two-way.
What is a directed graph?
A graph where each relationship between nodes can be one-way as shown by arrows on the edges or bidirectional.
What is a weighted graph?
A graph in which each edge is given a weight.
What are some possible graph operations?
- Adding/Removing a node
- Adding/Removing an edge between nodes
- Test if an edge exists between two nodes
- Getting and updating weights of an edge between two nodes
- Finding a valid path between two nodes
What are the two main ways of implementing a graph?
- Adjacency matrix - size of N^2 (N is number of nodes)
- Adjacency list - size of N + E (N is number of nodes and E is number of edges within graph)
How can an adjacency matrix be represented?
Static 2D array
How can an adjacency list be represented?
Dynamically as an array of graph nodes, each containing a pointer to a list of nodes
What are the advantages of adjacency matrices?
- Edges between nodes can be quickly identified due to random access of elements within arrays
What are the disadvantages of adjacency matrices?
-Less memory efficient and can be wasteful with memory
- Almost half of the matrix is repeated data
- Stores every possible edge between nodes, even those that don’t exist - more memory is used, as a value (1, 0, weight) is stored for every combination of nodes
When are adjacency matrices used?
- “Dense graphs” where there are a lot of edges
- Graphs where edges need to be frequently created,removed,identified or their weights changed
When are adjacency lists used?
- “Sparse graphs” where there are not many edges
- Graphs where nodes are frequently added/removed
What are the advantages of adjacency lists?
- Memory efficient as they only store edges that exist in the graph
What are the disadvantages of adjacency lists?
- They are slower to identify edges as the list has to be traversed to see if an edge exists between two nodes
What is graph traversal?
Visiting every node within the graph to achieve an purpose
What are the two different types of graph traversal?
- Depth-First Search
- Breadth-First Search
How does Depth First traversal work?
- Recursively visits nodes that are adjacent to a starting node
- Until a node is reached with no unvisited adjacent nodes
- At this point the algorithm backtracks to the previous node and visits any unvisited nodes from there
How is a stack used in depth first traversal?
Stack is used to keep track of the node being currently visited and the history of nodes required to get there.
What are the uses of a depth first traversal algorithm.
- Finding a solution to a maze, where the maze is modelled as a graph
- Finding the valid path from one node to another
- Determining the order with which processes that depend on one another should occur
How does breadth first traversal work?
Adds all adjacent nodes to a queue and uses iteration to repeat the process with the node at the front of the queue.
