Graphs and Trees PDF

# علوم الحاسب ## الفرقة الثانية ### Session 8 ### هياكل البيانات ### Data Structures *** # Q.1. What is graph, state different types of graph. A graph: a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, connecting the pairs of vertices.(arcs) - a - b -...

# علوم الحاسب ## الفرقة الثانية ### Session 8 ### هياكل البيانات ### Data Structures *** # Q.1. What is graph, state different types of graph. A graph: a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, connecting the pairs of vertices.(arcs) - a - b - c - d - e - **Nodes/Vertices** - **Edge** - A - B - E - D → V = {a, b, c, d, e} E = {ab, ac, bd, cd, de} ## Graph types: 1) Directed graph (di-graph) if all the edges are directed. 2) Undirected graph (graph) if all the edges are undirected. 3) Mixed graph if edges are both directed and undirected. - (a) Directed graph - **A** - **B** - **E** - **F** - **C** - **D** - (b) Undirected graph - **A** - **B** - **E** - **F** - **C** - **D** # Q.2. Define each of the following. End-vertices of an edge are the endpoints of the edge. Two vertices are adjacent if they are endpoints of the same edge. An edge is incident on a vertex if the vertex is an endpoint of the edge. Outgoing edges of a vertex are directed edges that the vertex is the origin. Incoming edges of a vertex are directed edges that the vertex is the destination. Degree of a vertex, v, denoted deg(v) is the number of incident edges. Out-degree, outdeg(v), is the number of outgoing edges. In-degree, indeg(v), is the number of incoming edges. Parallel edges or multiple edges are edges of the same type and end-vertices. Self-loop is an edge with the end vertices the same vertex. Note: Simple graphs have no parallel edges or self-loops. Note: Simple graph with n vertices has O(n²) edges at most. # End points (or end vertices) of an edge - U and V are the endpoints of a - **V** - **a** - **b** - **h** - **j** - **U** - **d** - **X** - **Z** - **C** - **e** - **i** - **W** - **g** - **f** - **Y** # Edges incident on a vertex - a, d, and bare incident on V # Adjacent vertices - U and V are adjacent # Degree of a vertex - X has degree 5 # Parallel (multiple) edges - hand i are parallel edges # self-loop - jis a self-loop # outgoing edges of a vertex - hand bare the outgoing edges of X - **V** - **b** - **h** - **j** - **d** - **X** - **Z** - **e** - **W** - **g** - **f** - **Y** # incoming edges of a vertex - e, g, and i are incoming edges of X # in-degree of a vertex - X has in-degree 3 # out-degree of a vertex - X has out-degree 2 # Q.3. Define each of the following. Path sequence of edges which joins a sequence of vertices. Cycle is a path that starts and end at the same vertex. Simple path is a path with distinct vertices. Directed path is a path of only directed edges. Directed cycle is a cycle of only directed edges. Sub-graph is a subset of vertices and edges. Spanning sub-graph contains all the vertices. Connected graph has all pairs of vertices connected by at least one path. Connected component is the maximal connected sub-graph of a unconnected graph Forest is a graph without cycles. Tree is a connected forest. Spanning tree is a spanning subgraph that is also a tree. - Subgraph - Spanning subgraph - Connected graph - Tree - Forest # Path - sequence of alternating vertices and edges - begins with a vertex - ends with a vertex - each edge is preceded and followed by its endpoints # Simple path - path such that all its vertices and edges are distinct - **V** - **a** - **b** - **P₁** - **d** - **U** - **X** - **Z** - **P₂** - **h** - **C** - **e** - **W** - **g** - **f** - **Y** # Cycle - circular sequence of alternating vertices and edges - each edge is preceded and followed by its endpoints # Simple cycle - cycle such that all its vertices and edges are distinct # Examples - C₁=(V,b,X,g,Y,f,W,c,U,a, ) is a simple cycle - C₂=(U,c,W,e,X,g,Y,,,,,, ) is a cycle that is not simple - **V** - **a** - **b** - **d** - **U** - **X** - **Z** - **C₂** - **h** - **e** - **C₁** - **1** - **W** - **g** - **f** - **Y** # Exercise: Properties of Undirected Graphs ## Property 1 - Total degree - Σ₁deg(v) = 2m - Proof: each edge is counted twice ## Property 2 - Total number of edges - In an undirected graph with no self-loops and no multiple edges - m≤ n (n-1)/2 - Proof: each vertex has degree at most (n - 1) | Notation | Description | |-----------------------|-------------| | **n** | number of vertices | | **m** | number of edges | | **deg(v)** | degree of vertex v | | **Example** | n = 4, m=6, deg(v) = 3 | | **A graph** | A graph with given number of vertices (4) and maximum number of edges | # Exercise: Properties of Directed Graphs ## Property 1 - Total in-degree and out-degree - ∑,in-deg(v) = m - Σout-deg(v) = m ## Property 2 - Total number of edges - In a directed graph with no self-loops and no multiple edges - m≤ n (n-1) | Notation | Description | |-----------------------|-------------| | **n** | number of vertices | | **m** | number of edges | | **deg(v)** | degree of vertex v | | **Example** | n = 4, m = 12, deg(v) = 6 | | **A graph** | A graph with given number of vertices (4) and maximum number of edges | # Q.4. Describe graph representation and graph traverse. Graph representation - Adjacency matrix - Adjacency list - **0** - **1** - **2** - **3** - **4** - **0** - **0** - **0** - **1** - **1** - **0** - **1** - **1** - **0** - **0** - **1** - **1** - **1** - **1** - **0** - **0** - **0** - **1** - **0** - **1** - **0** - **0** - **1** - **1** - **0** - **1** - **0** - **1** - **0** - **1** - **0** - **1:LGA** - **2:PVD** - **0:ORD** - **849** - **802** - **1387** - **3:DFW** - **1120** - **1099** - **4:MIA** - **i/j** - **1** - **2** - **3** - **4** - **1** - **0** - **1** - **0** - **0** - **2** - **0** - **0** - **0** - **1** - **3** - **1** - **0** - **0** - **1** - **4** - **0** - **1** - **0** - **0** - **1** - **2** - **3** - **4** ## Graph traverse - **Depth First Search** (using stack) - **Breadth First Search** (using queue) - **S** - **A** - **B** - **C** - **2** - **D** - **E** - **F** - **7** - **3** - **6** - **G** - **1** - **4** - **5** - **7** - **S** - **A** - **B** - **C** - **5** - **2** - **D** - **E** - **F** - **3** - **6** - **G** - **1** # Depth- first Search. - **S** - **A** - **B** - **C** - **D** - **Stack** - **S** - **S** - **A** - **B** - **C** - **top- S** - **D** - **Stack** - **S** - **A** - **B** - **C** - **top- A** - **D** - **Stack** - **S** - **A** - **B** - **C** - **top- D** - **A** - **S** - **D** - **Stack** - **Depth-** - **S** - **A** - **B** - **C** - **top- B** - **A** - **S** - **D** - **Stack** - **S** - **A** - **B** - **C** - **top- C** - **D** - **A** - **S** - **D** - **Stack** # Depth- first Search - Implementation. ``` #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX 5 struct Vertex { char label; bool visited; }; //stack variables int stack[MAX] int top = -1; //graph variables //array of vertices struct Vertex* IstVertices [MAX]; //adjacency matrix int adjMatrix[MAX][MAX]; //vertex count int vertexCount = 0; //stack functions void push(int item) { stack[++top] = item; } int pop() { return stack[top--]; } int peek() { return stack[top]; } bool isStackEmpty() { return top == -1; } //graph functions //add vertex to the vertex list void addVertex(char label) { struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex)); vertex->label = label; vertex->visited = false; IstVertices[vertexCount++] = vertex; } //add edge to edge array void addEdge(int start, int end) { adj Matrix[start][end] = 1; adjMatrix[end][start] = 1; } //display the vertex void display Vertex(int vertexIndex) { printf("%c", IstVertices [vertexIndex]->label); } //get the adjacent unvisited vertex int getAdjUnvisitedVertex(int vertexIndex) { int i; for (i = 0; i < vertexCount; i++) { if (adjMatrix[vertexIndex][i] == 1 && IstVertices[i]->visited == false) { return i; } } } return -1; void depthFirstSearch() { int i; //mark first node as visited IstVertices[0]->visited = true; //display the vertex display Vertex(0); //push vertex index in stack push(0); while (!isStackEmpty()) { int unvisitedVertex = getAdjUnvisitedVertex(peek()); if (unvisitedVertex == -1) { pop(); } else { IstVertices[unvisitedVertex]->visited = true; display Vertex(unvisitedVertex); push(unvisitedVertex); } } //stack is empty, search is complete, reset the visited flag for (i = 0;i < vertexCount;i++) { IstVertices[i]->visited = false; } } int main() { int i, j; for (i = 0; i < MAX; i++) { // set adjacency for (j = 0; j < MAX; j++) // matrix to O adjMatrix[i][j] = 0; } addVertex('S'); //0 addVertex('A'); //1 addVertex('B'); //2 addVertex('C'); //3 addVertex('D'); //4 addEdge(0, 1); // S-A addEdge(0, 2); // S - B addEdge(0, 3); // S-C addEdge(1, 4); // A-D addEdge(2, 4); // B-D addEdge(3, 4); //C-D printf("Depth First Search: "); depthFirst Search(); return 0; } ``` # Breadth First Search - **S** - **A** - **B** - **C** - **D** - **Queue** - **S** - **A** - **B** - **C** - **Queue** - **S** - **A** - **B** - **C** - **A** - **D** - **Queue** - **S** - **A** - **B** - **C** - **B** - **A** - **D** - **Queue** - **S** - **A** - **B** - **C** - **C** - **B** - **A** - **D** - **Queue** - **S** - **A** - **B** - **C** - **D** - **C** - **B** - **A** - **Queue** # Breadth First Search-Implementation ``` #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX 5 struct Vertex { char label; bool visited; }; //queue variables int queue[MAX]; int rear = -1; int front = 0; int queueItemCount = 0; //graph variables //array of vertices struct Vertex* IstVertices [MAX]; //adjacency matrix int adjMatrix[MAX][MAX]; //vertex count int vertexCount = 0; //queue functions void insert(int data) { queue[++rear] = data; queueItemCount++; } int removeData() { queueItemCount--; return queue[front++]; } bool isQueueEmpty() { return queueItemCount == 0; } //graph functions //add vertex to the vertex list void addVertex(char label) { struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex)); vertex->label = label; vertex->visited = false; IstVertices[vertexCount++] = vertex; } //add edge to edge array void addEdge(int start, int end) { adj Matrix[start][end] = 1; adjMatrix[end][start] = 1; } //display the vertex void display Vertex(int vertexIndex) { printf("%c", IstVertices[vertexIndex]->label); } //get the adjacent unvisited vertex int getAdjUnvisitedVertex(int vertexIndex) { int i; for (i = 0; i<vertexCount; i++) { if (adjMatrix[vertexIndex][i] == 1 && IstVertices[i]->visited == false) return i; } return -1; } void breadth FirstSearch() { int i; //mark first node as visited IstVertices[0]->visited = true; //display the vertex display Vertex(0); //insert vertex index in queue insert(0); int unvisitedVertex; while (!isQueueEmpty()) { int tempVertex = removeData(); while ((unvisitedVertex = getAdjUnvisitedVertex(tempVertex)) != -1) { IstVertices[unvisitedVertex]->visited = true; display Vertex(unvisitedVertex); insert(unvisitedVertex); } } //queue is empty, search is complete, reset the visited flag for (i = 0;i<vertexCount;i++) { IstVertices[i]->visited = false; } } int main() { int i, j; for (i = 0; i<MAX; i++) { // set adjacency for (j = 0; j<MAX; j++) // matrix to 0 adjMatrix[i][j] = 0; } addVertex('S'); //0 addVertex('A'); //1 addVertex('B'); //2 addVertex('C'); //3 addVertex('D'); //4 addEdge(0, 1); // S-A addEdge(0, 2); // S-B addEdge(0, 3); // S-C addEdge(1, 4); // A-D addEdge(2, 4); // B-D addEdge(3, 4); //C-D printf("\nBreadth First Search: "); breadthFirstSearch(); return 0; } ```