Chapter 4: Graph Data Structure PDF

Chapter 4 A Graph Data Structure  Graph Definitions and Notation Graph Data Structure is a non-linear data structure consisting of vertices (singular: vertex) and edges (lines or links) that connects pairs of vertices. A graph G is denoted G = (V, E), where V is a finite nonempty set, called...

Chapter 4 A Graph Data Structure  Graph Definitions and Notation Graph Data Structure is a non-linear data structure consisting of vertices (singular: vertex) and edges (lines or links) that connects pairs of vertices. A graph G is denoted G = (V, E), where V is a finite nonempty set, called the set of vertices (nodes) of G or V(G), and E(G) set of edges, E ⊂ V × V is a set of pairs/couples {v1, v2} with v1, v2 ∈ V. In an undirected graph, the pairs (v1, v2) and (v2, v1) represent the same edge.  A Directed Graph A directed graph G is represented by a pair (V, E) where V is a finite set and E is a binary relation on V. The set V is the set of vertices of G and E is the set of edges of G. Example1: the directed graph G = (V, E) with the vertex set V = {1, 3, 4, 5} and the edge set E = {(5,3), (5,4), (3,1), (4,1)}; we say the edge (5, 3) is not the same as (3, 5). The directed edge (i,j) is incident to vertex j and incident from vertex i. Two vertices v1 and v2 are adjacent (or neighbors) if they are connected by an adge. We say Vertex v1 is adjacent to vertex v2, and vertex v2 is adjacent from vertex v1/or the adge (v1, v2) starts from vertex v1 and arrives at vertex v2. Note that loops are possible here, a loop being an edge that connects a vertex to itself. loop v u and v are adjacent (u, v) v and w are not adjacent u w  An Undirected Graph By convention, we represent the edge between vertices v1 and v2 by the notations (v1,v2) or (v2, v1), the relationship between the vertices is symmetrical. Two vertices v1 and v2 are adjacent (or neighbors) if they are connected by an adge. A vertex incident to an edge if it is connect to that edge. In an undirected graph, loops are forbidden and each edge is therefore made up of two distinct vertices. Example: undirected graph G = (V, E) with the vertex set S = {1, 3, 4, 5} and the edge set A = {(5, 3), (5, 4), (3, 1), (4, 1)}; we say the edge (3, 1) or (1, 3), are is the same. In an undirected graph, the degree of a vertex is the number of edges incident to it. If a vertex has degree 0, it is said to be isolated. In a directed graph, the out-degree of a vertex is the number of edges that come out of it, the in-degree is the number of edges that come in, and the degree is the sum of the in-degree and the out-degree. Vocabulary A path is a sequence of vertices in which each vertex is adjacent to the next one. Example: (a,b,c,d) is one path. A loop is a special cas of a cycle of length =1. A path forms a cycle if consisting at least 3 vertices and starts and ends with the same vertex. Example: (a,b,c,d,b, a) is a cycle. This cycle is elementary if the vertices u0,...,uk which compose it are distinct, except the beginning and end of the path are the same. Example: (a,b,f,a) is an elementary cycle. A Vocabulary An undirected graph is connected if for any pair of vertices , there exists a path connecting them. A directed graph is connected if the associated undirected graph is connected. A directed graph is strongly connected if for any pair of vertices there exists a path connecting them otherwise it is weakly connected. G1 G2 Cyclic graph: contain at least one cycle. Acyclic graph: contains no cycles. Vocabulary Strongly Connected: Every vertex is reachable from every other vertex, considering the direction of the edges. Weakly Connected: If you ignore the direction of the edges, there is a path between every pair of vertices, but it does not require the directed paths to exist. G1 is strongly connected while G2 is weakly connected. G1 G2 Vocabulary Strongly Connected: Every vertex is reachable from every other vertex, considering the direction of the edges. Weakly Connected: If you ignore the direction of the edges, there is a path between every pair of vertices, but it does not require the directed paths to exist. G1 is strongly connected while G2 is weakly connected. Otherwise the graph is disjoint or disconnected. Vocabulary Vocabulary A Complete graph: for every paire/couple of vertices there exists an edge (one direct link not a path). An undirected graph that is connected and acyclic (has no cycle) is a tree. Complete Graph A tree Representation of Graphs by an Adjacency Matrix An adjacency matrix is a way of representing a graph as a matrix of boolean (0’s and 1’s) Let G = (V,E) G can be represented by an n × n matrix M, in which the rows represent the starting vertices and the columns represent the arrival vertices. The adjacency matrix is a two-dimensional n × n matrix such that the (i, j)th entry of A is 1 if there is an edge from vi to vj; otherwise, the (i, j) th entry is zero. In undirected graph a matrix must be symmetric. 1 If (i, j)∈ E Mi,j= 0 Otherwise Representation of Graphs by an Adjacency Matrix 0 0 0 0 0 0 Representation of Graphs by an Adjacency Matrix 0 0 0  Representation of Graphs by an Incidence Matrix Let G = (V,E) G can be represented by a matrix M of dimension n × p, where n is the number of vertices and p is the number of arcs/edges. Directed Graph Undirected Graph 1 if,the arc Ei sort of vertex Si 1 if vertex Si is an extremity of Mi,j the edge Aj Mi,j -1 if, the arc Ei enter into vertex Si 0 Otherwise 0 Otherwise  Representation of Graphs by an Adjacency List An array of Lists is used to store edges between two vertices. The size of array is equal to the number of vertices (i.e, n). Each index in this array represents a specific vertex in the graph. The entry at the index i of the array contains a linked list containing the vertices that are adjacent to vertex i. Let’s assume there are n vertices in the graph So, create an array of list of size n as adjList[n]. adjList will have all the nodes which are connected (neighbour) to vertex 0. adjList will have all the nodes which are connected (neighbour) to vertex 1 and so on.  Representation of Graphs by an Adjacency List Representation of Undirected Graph as Adjacency list: The below undirected graph has 3 vertices. So, an array of list will be created of size 3, where each indices represent the vertices. Now, vertex 0 has two neighbours (i.e, 1 and 2). So, insert vertex 1 and 2 at indices 0 of array. Similarly, For vertex 1, it has two neighbour (i.e, 2 and 0) So, insert vertices 2 and 0 at indices 1 of array. Similarly, for vertex 2, insert its neighbours in array of list.  Representation of Graphs by an Adjacency List Representation of Directed Graph as Adjacency list: The below directed graph has 3 vertices. So, an array of list will be created of size 3, where each indices represent the vertices. Now, vertex 0 has no neighbours. For vertex 1, it has two neighbour (i.e, 0 and 2) So, insert vertices 0 and 2 at indices 1 of array. Similarly, for vertex 2, insert its neighbours in array of list. Graph Traversal: Breadth First Search (BFS) Is a fundamental graph traversal algorithm. It begins with a node, then first traverses all its adjacent. Once all adjacent are visited, then their adjacent are traversed. We mainly traverse vertices level by level. BFS itself can be used to detect cycle in a directed and undirected graph, find shortest path in an unweighted graph and many more problems. The algorithm starts from a given source and explores all reachable vertices from the given source. Like tree, we begin with the given source (in tree, we begin with root) and traverse vertices level by level using a queue data structure. The only catch here is that, unlike trees, graphs may contain cycles, so we may come to the same node again. Graph Traversal: Breadth First Search (BFS) 1. Initialization: Enqueue the given source vertex into a queue and mark it as visited. 2. Exploration: While the queue is not empty: Dequeue a node from the queue and visit it (e.g., print its value). For each unvisited neighbors of the dequeued node: Enqueue the neighbors into the queue. Mark the neighbors as visited. 3. Termination: Repeat step 2 until the queue is empty. Graph Traversal: Breadth First Search (BFS) Graph Traversal: Breadth First Search (BFS) Graph Traversal: Breadth First Search (BFS) Graph Traversal: Breadth First Search (BFS) Graph Traversal: Breadth First Search (BFS) Graph Traversal: Breadth First Search (BFS) Graph Traversal: Breadth First Search (BFS) Graph Traversal: Depth First Search (DFS) Like trees, we traverse all adjacent vertices one by one. When we traverse an adjacent vertex, we completely finish the traversal of all vertices reachable through that adjacent vertex. After we finish traversing one adjacent vertex and its reachable vertices, we move to the next adjacent vertex and repeat the process. This is similar to a tree, where we first completely traverse the left subtree and then move to the right subtree. The key difference is that, unlike trees, graphs may contain cycles (a node may be visited more than once). To avoid processing a node multiple times, we use a boolean visited array. Graph Traversal: Depth First Search (DFS) DFS from a Given Source: The algorithm starts from a given source and explores all reachable vertices one by one from the given source. It is similar to preorder tree traversal where we visit the root, then recur for its children. The working of Depth First Search of the following illustration: for the source as 0. Graph Traversal: Depth First Search (DFS) Graph Traversal: Depth First Search (DFS) Graph Traversal: Depth First Search (DFS) Graph Traversal: Depth First Search (DFS) Graph Traversal: Depth First Search (DFS) Graph Traversal: Depth First Search (DFS) Graph Traversal: Traversal itself follows the same core principles in both types of graphs, but in directed graphs, you are restricted by the edge direction, whereas in undirected graphs, you have more freedom to move in both directions. In graph traversal, you must consider the direction of the edges to determine the valid neighbors of a node. You only follow edges that go in the direction from the current node to its neighbors, and you only visit each node once when it is reached for the first time. If the graph were undirected, you would just look at all neighbors without considering direction, but that’s not the case for directed graphs. If we change the node source, we can form a different traversal version.