• A graph is a finite set of nodes with edges between nodes
• Formally, a graph G is a structure (V,E) consisting of
– a finite set V called the set of nodes, and
– a set E that is a subset of VxV. That is, E is a set of pairs of the form (x,y) where x and y are nodes in V
Graph Representation
• For graphs to be computationally useful, they have to be conveniently represented in programs
• There are two computer representations of graphs:
– Adjacency matrix representation
– Adjacency lists representation
Adjacency Matrix Representation
• In this representation, each graph of n nodes is represented by an n x n matrix A, that is, a two-dimensional array A
• The nodes are (re)-labeled 1,2,…,n
• A[i][j] = 1 if (i,j) is an edge
• A[i][j] = 0 if (i,j) is not an edge
Pros and Cons of Adjacency Matrices
• Pros:
– Simple to implement
– Easy and fast to tell if a pair (i,j) is an edge: simply check if A[i][j] is 1 or 0
• Cons:
– No matter how few edges the graph has, the matrix takes O(n2) in memory
Adjacency Lists Representation
• A graph of n nodes is represented by a one-dimensional array L of linked lists, where
– L[i] is the linked list containing all the nodes adjacent from node i.
– The nodes in the list L[i] are in no particular order
Pros and Cons of Adjacency Lists
• Pros:
– Saves on space (memory): the representation takes as many memory words as there are nodes and edge.
• Cons:
– It can take up to O(n) time to determine if a pair of nodes (i,j) is an edge: one would have to search the linked list L[i], which takes time proportional to the length of L[i].
Graph Traversal Techniques
• The previous connectivity problem, as well as many other graph problems, can be solved using graph traversal techniques
• There are two standard graph traversal techniques:
– Depth-First Search (DFS)
– Breadth-First Search (BFS)
• In both DFS and BFS, the nodes of the undirected graph are visited in a systematic manner so that every node is visited exactly one.
• Both BFS and DFS give rise to a tree:
– When a node x is visited, it is labeled as visited, and it is added to the tree
– If the traversal got to node x from node y, y is viewed as the parent of x, and x a child of y
Depth-First Search
• DFS follows the following rules:
1. Select an unvisited node x, visit it, and treat as the current node
2. Find an unvisited neighbor of the current node, visit it, and make it the new current node;
3. If the current node has no unvisited neighbors, backtrack to the its parent, and make that parent the new current node;
4. Repeat steps 3 and 4 until no more nodes can be visited.
5. If there are still unvisited nodes, repeat from step 1.
Implementation of DFS
• Observations:
– the last node visited is the first node from which to proceed.
– Also, the backtracking proceeds on the basis of "last visited, first to backtrack too".
– This suggests that a stack is the proper data structure to remember the current node and how to backtrack.
Breadth-First Search
• BFS follows the following rules:
1. Select an unvisited node x, visit it, have it be the root in a BFS tree being formed. Its level is called the current level.
2. From each node z in the current level, in the order in which the level nodes were visited, visit all the unvisited neighbors of z. The newly visited nodes from this level form a new level that becomes the next current level.
3. Repeat step 2 until no more nodes can be visited.
4. If there are still unvisited nodes, repeat from Step 1.
Implementation of DFS
• Observations:
– the first node visited in each level is the first node from which to proceed to visit new nodes.
• This suggests that a queue is the proper data structure to remember the order of the steps.
No comments:
Post a Comment