Chapter 38 - Graphs Flashcards
What is a graph?
» An abstract data structure which are representing a complex relationship
» A set of vertices or nodes connected by adges or arcs
What is traversal?
» It is essentially the ‘cost’ of movement around the graph
What are the features of an undirected graph?
» Consists of nodes
» All edges are bidirectional - meaning they can go any direction
What is an edge?
» Represents a path/link between 2 nodes
What is an arc?
» Another name for an edge
What is a vertex?
» Each data item within a graph
What is a node?
» Another name for a vertex
What is a weighted edge?
» Edges that have some value, attached to them
» Shows the cost of traversing
What are the features of a directed graph?
» Shows direction - can be bidirectional
» Consists of nodes
What are the 2 possible implementations of a graph?
» Adjacency matrix
» Adjacency list
What does each row and column represent in a adjacency matrix?
» A node
What is the order of a matrix?
» Row then column
What is an adjacency matrix?
» A table showing which nodes in a graph are connected and if the edges are weighted
» Elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph
What will the adjacency matrix be in an undirect graph?
» Symmetric
How can an unweighted graph be represented in a matrix?
» May be represented with 1s instead of weights
How can a weighted graph be represented in a matrix?
» Instead of 1s, there can be the value of the weight
What are the advantages of an adjacency matrix?
» Very convenient to work with
» Adding edges is very simple
What are the disadvantages of an adjacency matrix?
» A sparse graph with not many connections will leave most of the cells empty, therefore wasting space
» Using a static 2D array for it, it is harder to add or delete nodes
What is an adjacency list?
» A collection of unordered lists used to represent a finite graph
» Each list describes the set of neighbours of a vertex in a graph
How does an adjacency list look like?
» A list of all the nodes are created
» Each node points to a list where all the adjacent nodes to which is directly linked
When should an adjacency list be implemented as a dictionary?
» When it is weighted, with each key in the dictionary being the node and the value, the edge weight
What are the advantages of an adjacency list?
» Good way of representing a sparsely connected graph
» More memory efficient
What are the disadvantages of an adjacency list?
» In the adjacency list, you need to list all the nodes that the node is connected to, in order to find the other node of the edge required.
» Not time efficient
What is the page rank algorithm?
» An algorithm used by Google search to rank website in their search engine results
What are the 2 ways to traverse a graph so that every node is visited?
» A depth - first traversal
» A breadth - first traversal
What is a Depth-first traversal?
» We go as far down one route as we can before backtracking and taking the next route
» Visit the first node atatched to starting node
» Visited all the nodes connected directly or indirectly to this first node
» Visit the second node directly atteched to the starting node
What is the data structure used for depth-first traversal?
» A stack
What are the applications for depth-first searches?
» Finding a path between 2 vertices
» Solving a puzzles such as navigating a maze
Is there a unique way to visit all the nodes in a depth-first search?
» No as the sequence involves some choices
What is a breadth-first search?
» We visit all the neighbours of a node, then all the neighbours of the first node visited, and so on before moving further away from the start node
What is the data structure used for breadth-first searches?
» A queue
What are the applications for a breadth-first search?
» Finding the shortest path between 2 points
» Facebook used a breadth-first search to find all the friends of a given individual
What are some applications for graphs?
» Computer networks
» Roads between towns
» Web pages and links
How does a graph differ from a linked list?
» Each vertex can have more than 2 edges
What does a 1 represent in an adjacency matrix?
» Represents an edge between 2 vertices
What is abstraction?
» Using only the necessary detail and discarding unecessary detail
In an undirected graph, what are the edges?
» Bidirectional
