Schematic representation of the edge list structure for an undirected graph:
Schematic representation of adjacency list for an undirected graph:
Schematic representation of adjacency map for an undirected graph:
Schematic representation of adjacency matrix for an undirected graph:
Consider the graph represented by the following adjacency matrix.
Answer: 4. Outgoing edge (c) and incoming edges (a, d, f) are incident to vertex 1.
Answer: 2. The second graph correctly portrays the six directed edges from the matrix, for example with edge f going from 3 to 1.
Graph
implementation based on the adjacency map representation.
Graph traversal is a systematic procedure for exploring a graph by examining all vertices and edges. A traversal is efficient if it visits all the vertices and edges in linear time.
Graph traversal algorithms are key to answering questions about graphs involving reachability, that is, in determining how to travel from one vertex to another while following paths of a graph.
We will focus on two efficient graph traversal algorithms -- depth-first search and breadth-first search.
DFS explores as far as possible along each branch before backtracking.
Let's think of DFS as wandering in a maze with a string and a can of paint without getting lost. We begin at a starting vertex s in G, which we initialize by fixing one end of our string to s and painting s as "visited." The vertex s is now our "current" vertex. In general, if we call our current vertex u, we traverse G by considering an arbitrary edge (u, v) incident to the current vertex u. If the edge (u, v) leads to an unvisited vertex v, then we go to v and paint v as "visited", making v the current vertex and repeating the computation above. Eventually, we will get to a "dead end," that is, a vertex with no unvisited neighbors. At this point, we backtrack to a previously visited vertex u. We make u our current vertex and repeat the computation above for any edges incident to u that we have not yet considered. If all of u's incident edges lead to visited vertices, we again roll up our string and backtrack to the vertex that led us to u. We continue this process until we have visited all vertices reachable from the starting vertex s.
Algorithm DFS(G, u) Input: Graph G and a starting vertex u of G Output: A collection of vertices reachable from u in G Mark vertex u as visited For each of u's outgoing edges e = (u, v): If vertex v is not visited: Record edge e as the discovery edge for vertex v Recursively call DFS(G, v)
When performing DFS, these are the different kinds of edges:
Let's perform DFS on the following graph:
While DFS is similar to a single person traversing through a maze, breadth-first search is more akin to sending out, in all directions, many explorers who collectively traverse a maze in a coordinated fashion.
A BFS proceeds in rounds and subdivides the vertices into levels.
Algorithm BFS(G, s): Input: Graph G and a starting vertex s of G Output: A collection of vertices reachable from s in G visited ← empty map level ← empty list next_level ← empty list // Initialize the first level with the start vertex level.push_back(s) visited[s] ← s // Mark the start vertex as visited (can mark itself as parent) while level is not empty do: next_level ← empty list // Explore each vertex in the current level for each u in level do: for each v in neighbors(u) of G do: if v is not in visited then: visited[v] ← u // Mark v as visited via u next_level.push_back(v) // Add v to the next level // Move to the next level level ← next_level
Another way to implement BFS is to use a FIFO queue to represent the current fringe of the search. Starting with the source vertex in the queue, we repeatedly remove the vertex from the front of the queue and insert any of its unvisited neighbors to the back of the queue:
Algorithm BFS(G, s): Input: Graph G and a starting vertex s of G Output: A collection of vertices reachable from s in G Create an empty queue Q Enqueue s onto Q Mark s as visited While Q is not empty: Dequeue vertex u from Q For each of u's outgoing edges e = (u, v): If vertex v is not visited: Mark v as visited Enqueue v onto Q
Let's consider a breadth-first search starting at vertex A of the following directed graph:
Answer: {B, D}.
Answer: {G, E, F}.
Answer: ABDFEGC.
A is added to L0. B is then added to L1 followed by D. Because B is the first vertex in L1, outgoing edge (B -> F) is used to add F to L2
before edges (D -> E) and (D -> G) are used to add E and G to L2. Finally, C is added to L3 using edge F -> C.