16-08-2013, 04:47 PM
GRAPH SEARCH ALGORITHMS
GRAPH SEARCH.pptx (Size: 203.85 KB / Downloads: 19)
Graph Search Algorithms
Systematic search of every edge and every vertex of a graph.
Graph G=(V,E) is either directed or undirected.
Applications
Compilers
Networks
Routing, Searching, Clustering, etc.
Breadth-First Search
Breadth-first search starts at a given vertex s, which is at level 0.
In the first stage, we visit all the vertices that are at the distance of one edge away. When we visit there, we paint as "visited," the vertices adjacent to the start vertex s - these vertices are placed into level 1.
In the second stage, we visit all the new vertices we can reach at the distance of two edges away from the source vertex s. These new vertices, which are adjacent to level 1 vertices and not previously assigned to a level, are placed into level 2, and so on.
The BFS traversal terminates when every vertex has been visited.
BFS Algorithm
Inputs: Inputs are a graph(directed or undirected) G =(V, E) and a source vertex s, where s is an element of V. The adjacency list representation of a graph is used in this analysis.
Outputs:
The outputs are a predecessor graph, which represents the paths travelled in the BFS traversal, and a collection of distances, which represent the distance of each of the vertices from the source vertex.
Analysis of Breadth-First Search
Shortest-path distance (s,v) : minimum number of edges in any path from vertex s to v. If no path exists from s to v, then (s,v) = ∞
The ultimate goal of the proof of correctness is to show that d[v] = (s,v) when the algorithm is done and that a path is found from s to all reachable vertices.
Bipartite Graph
A bipartite graph is an undirected graph G = (V, E) in which V can be partitioned into two sets V1 and V2 such that (u, v) E implies either u in V1 and v in V2 or u in V2 and v in V1. That is, all edges go between the two sets V1 and V2.
whenever the BFS is at a vertex u and encounters a vertex v that is already 'gray' our modified BSF should check to see if the depth of both u and v are even, or if they are both odd. If either of these conditions holds which implies d[u] and d[v] have the same parity, then the graph is not bipartite.