figure directed acyclic graph vertices agm are sources and vertices lfhn are sinks the ordering habcedghkijflmni is topological ordering of the vertices figure an undirected graph if is an undirected graphvertices and are said to be connected if contains path from to votherwiseu and are said to be disconnected graph is said to be connected if every pair of vertices in the graph is connected connected component is maximal set of vertices such that each pair of vertices in is connected in every vertex belongs to exactly one connected component for examplethe graph in figure is connectedand it has single connected component if edge (hiis removedit remains connected if additionally fiis removedit becomes disconnected and there are two connected components directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces an undirected graph that is connected it is connected if it contains directed path from to or directed path from to for every pair of vertices and it is strongly connected if it contains directed path from to and directed path from to for every pair of vertices and graphs naturally arise when modeling geometric problemssuch as determining connected cities howeverthey are more generaland can be used to model many kinds of relationships graph can be implemented in two ways--using adjacency lists or an adjacency matrix in the adjacency list representationeach vertex vhas list of vertices to which it has an edge the adjacency matrix representation uses |vx |vboolean-valued matrix indexed by verticeswith indicating the presence of an edge the time and space complexities of graph algorithm are usually expressed as function of the number of vertices and edges tree (sometimes called free treeis special sort of graph--it is an undirected graph that is