3.3Implementing Graph Traversal Using Queues and Stacks

A graph can be represented as either an adjacency matrix or an adjacency list. with a graph G = (V,E), the number of nodes |V| is denoted as n and the number of edges |E| is denoted as m. When discussing the representations of graphs, our aim is to get a representation that allows us to implement the graph in a polynomial running time. The number of edges m is always less than or equal to n₂. Since most of graphs are connected, the graphs considered in the discussion of the representation of graphs have at least m≥ n-1 edges. The goal we have in the implementation of graphs is O(m+n), and is called linear time.
Some Definitions:

• Adjacency matrix: it's an n X n matrix A where A[u,v] is equal to 1 if the graph contains the edge (u,v), and 0 otherwise. This representation allows us to represent graphs in O(1) time if a the edge (u,v) is in the graph.
• Disadvantages:
  • The representation takes Θ(n₂) space.However, when the graph has many fewer edges than n₂, more compact (and better) representations are possible
  • Many graph algorithms need to examine all edges incident to a given node v. With the adjacency matrix, this operation takes Θ(n) time. More efficient algorithms exist solve this problem.