Graphs
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Graphs as PDF for free.
More details
- Words: 1,260
- Pages: 6
Chapter 9
Graphs
Graphs Definitions: •
A graph: consists of a set of nodes (or vertices) and a set of arcs (or edges). Each arc in graph is specified by a pair of nodes.
• Types of graphs: 1. Directed graph: Arc tail
head
A
B
2. Undirected graphs: Arc (A,B)
A
B
A graph need not be a tree, but a tree must be a graph. A node n is incident to an arc x if n is one of the two nodes in the ordered pair of nodes that constitute x. (we also say x is incident to n)
• • •
Degree: the number of arcs incident to the node. Indegree: the number of arcs that have the node as a head. Outdegree: the number of arcs that have the node as a tail. Degree = indegree + outdegree.
• •
Node n is adjacent to m if there is an arc from m to n. If n is adjacent to m, n is called a successor of m, and m a predecessor of n predecessor
m • • • •
36
successor
n
Weighted graph: is a graph that has a number associated with each arc. A path of a graph: is a sequence of nodes and arcs that start at a node and end at a node. A cycle is a path that its start and end nodes are the same.(path from a node to itself). If a graph contains a cycle ,it is cyclic, otherwise it is acyclic.
Fatemah Ba_hareth
Chapter 9
Graphs
Primitive Operations on graph: 1. 2. 3. 4.
join(a,b): add arc from a to b if not exist. joinwt(a,b,x): add arc from a to b with weight x in weighted graph. remv(a,b) and remvwt(a,b,x): remove an arc from a to b if exist. adjacent(a,b): returns true if b is adjacent to a, and false otherwise.
Application of Graphs: • Relations and graphs: p.517 • Cities and find path example: p.518 – p.520
C Representation of Graphs: •
Suppose that the number of nodes in the graph is constant: that is, arcs may be added or deleted but nodes may not. #define MAXNODES 50 struct node { /* information associated with each node*/ }; struct arc { int adj; /* information associated with each arc*/ }; struct graph { struct node nodes [MAXNODES]; struct arc arcs[MAXNODES][ MAXNODES]; }; struct graph g;
• • • • •
•
37
Each node of the graph is represented by an integer between 0 and MAXNODE-1. The array field nodes represents the appropriate information assigned to each node. The array field arcs is a two-dimensional array representing every possible ordered pair of nodes. And is called adjacency matrix. In case of a weighted graph, each arc can also be assigned information. If the arcs of graph are not weighted and no other information assigned to arcs and nodes also, the graph declared simply by: int adj [MAXNODES][ MAXNODES]; the graph is totally described by its adjacency matrix.
Fatemah Ba_hareth
Chapter 9
Graphs
Primitive Operation Codes: • Non weighted graph: join(a,b) void join (int adj[][MAXNODES], int node1, int node2 ) { adj[node1][node2] = TRUE; }
remv(a,b)
void remv (int adj[][MAXNODES], int node1, int node2 ) { adj[node1][node2] = FALSE; }
adjacent(a,b)
void adjacent (int adj[][MAXNODES], int node1, int node2 ) { return (( adj[node1][node2] == TRUE)? TRUE:FALSE); } • Weighted graph: A weighted graph with a fixed number of nodes may be declared by: struct arc { int adj; int weight; }; struct arc g [MAXNODES][ MAXNODES];
joinwt(a,b,x)
void joinwt (struct arc g [ ][MAXNODES], int node1, int node2, int wt) { g[node1][node2].adj = TRUE; g[node1][node2].weight = wt; }
38
Fatemah Ba_hareth
Chapter 9
Graphs
Transitive Closure: Assume that a graph is completely describe by its adjacency matrix. The logical expression adj[i][k] && adj[k][j] equal TRUE if and only if there is a path of length 2 from i to j passing through k . Let us consider adj2 such that adj2 [i] [j] =TRUE if there is a path of length 2between i and j. that means adj2 is the path matrix of length 2. adj2 is the Boolean product of adj with itself. adj3 is the Boolean product of adj2 with adj. and so on..
Path matrix: In the graph of n nodes path [i][ j] = adj[i][ j] || adj2[i][ j] || ….. adjn[i][ j] the matrix path is often called the transitive closure of the matrix adj. void transclose ( int adj[ ] [MAXNODES], int path[ ][ MAXNODES]) { int i, j, k; int newprod[MAXNODES][ MAXNODES], adjprod[MAXNODES][ MAXNODES]; for( i= 0; i< MAXNODES; ++i) for( j=0; j< MAXNODES; ++j) adjprod[i][ j] = path[i][ j] = adj [i][ j]; for( i= 0; i< MAXNODES; ++i) { prod (adjprod, adj, adjprod); for( j=0; j< MAXNODES; ++j) for(k=0;k< MAXNODES; ++k) path[ j][k] = path[ j][k] || newprod[ j][k]; for( j=0; j< MAXNODES; ++j) for(k=0;k< MAXNODES; ++k) adjprod[i][j] = newprod [ j][k]; }/* end for */ } /* end transclose*/ The routine prod may be written as follows: void prod ( int a[ ] [MAXNODES], int b[ ][ MAXNODES], int c[ ][ MAXNODES]) { int i, j, k, val; for( i= 0; i< MAXNODES; ++i) for( j=0; j< MAXNODES; ++j) { val =FALSE; for(k=0;k< MAXNODES; ++k) val = val || ( a[i][k] && b[k][ j] ); c[i][ j] = val; }/* end for j*/ } /* end prod*/ 39
Fatemah Ba_hareth
Chapter 9
Graphs
Finding the Boolean product by the method prod is O(n3), where n is the number of graph nodes. In transeclose, this process (the call to prod) is embedded in a loop that is repeated n-1 times, so that the entire transitive closure routine is O(n4) .
Warshall's Algorithm: Let us define the matrix pathk such that pathk [i][ j] is true if and only if there is a path from node i to node j that does not pass through any nodes higher than k. How can the value of pathk+1 obtained from pathk ? pathk+1 [i][ j] = TRUE if and only if one of the following conditions holds: 1. pathk [i][ j] == TRUE 2. pathk [i][ k+1] == TRUE and pathk [ k+1] [ j]== TRUE void transclose ( int adj[ ] [MAXNODES], int path[ ][ MAXNODES]) { int i, j, k; for( i= 0; i< MAXNODES; ++i) for( j=0; j< MAXNODES; ++j) path[i][ j] = adj [i][ j]; for(k=0;k< MAXNODES; ++k) for( i=0; i< MAXNODES; ++i) if (path [i][k] ==TRUE) for( j=0; j< MAXNODES; ++j) path[ i][ j] = path[ i][ j] || path[k][ j]; } /* end transclose*/
This technique increase the efficiency of finding the transitive closure to O(n3).
40
Fatemah Ba_hareth
Chapter 9
Graphs
Shortest-Path Algorithm #define INFINITY … #define MAXNODES … #define MEMBER 1 #define NONMEMBER 0 void shortpath(int weight[][MAXNODES], int s, int t, int *pd, int precde[]) { int distance[MAXNODES],perm[MAXNODES]; int current, I, k, dc; int smalldist, newdist; for(i=0 ; i< MAXNODES; i++) { perm[i]= NONMEMBER; distance[i] = INFINITY; }/* end for */ perm[s]=0; distance[s]=0; current=s; while(current != t) { smalldist= INFINITY; dc = distance[current]; for(i=0 ; i< MAXNODES; i++) { if (perm[i] == NONMEMBER) { newdist = dc + weight[current][i]; if(newdist < distance[i]) { distance[i] = newdist; precede[i] = current; }/*end if */ if(distance[i] < smalldist) { smalldist = distance[i]; k=i; }/*end if */ }/* end for …. If */ current = k ; perm[current] = MEMBER; }/* end while */ *pd = distance[t]; }/* end shortpath */
41
Fatemah Ba_hareth
Graphs
Graphs Definitions: •
A graph: consists of a set of nodes (or vertices) and a set of arcs (or edges). Each arc in graph is specified by a pair of nodes.
• Types of graphs: 1. Directed graph: Arc
head
A
B
2. Undirected graphs: Arc (A,B)
A
B
A graph need not be a tree, but a tree must be a graph. A node n is incident to an arc x if n is one of the two nodes in the ordered pair of nodes that constitute x. (we also say x is incident to n)
• • •
Degree: the number of arcs incident to the node. Indegree: the number of arcs that have the node as a head. Outdegree: the number of arcs that have the node as a tail. Degree = indegree + outdegree.
• •
Node n is adjacent to m if there is an arc from m to n. If n is adjacent to m, n is called a successor of m, and m a predecessor of n predecessor
m • • • •
36
successor
n
Weighted graph: is a graph that has a number associated with each arc. A path of a graph: is a sequence of nodes and arcs that start at a node and end at a node. A cycle is a path that its start and end nodes are the same.(path from a node to itself). If a graph contains a cycle ,it is cyclic, otherwise it is acyclic.
Fatemah Ba_hareth
Chapter 9
Graphs
Primitive Operations on graph: 1. 2. 3. 4.
join(a,b): add arc from a to b if not exist. joinwt(a,b,x): add arc from a to b with weight x in weighted graph. remv(a,b) and remvwt(a,b,x): remove an arc from a to b if exist. adjacent(a,b): returns true if b is adjacent to a, and false otherwise.
Application of Graphs: • Relations and graphs: p.517 • Cities and find path example: p.518 – p.520
C Representation of Graphs: •
Suppose that the number of nodes in the graph is constant: that is, arcs may be added or deleted but nodes may not. #define MAXNODES 50 struct node { /* information associated with each node*/ }; struct arc { int adj; /* information associated with each arc*/ }; struct graph { struct node nodes [MAXNODES]; struct arc arcs[MAXNODES][ MAXNODES]; }; struct graph g;
• • • • •
•
37
Each node of the graph is represented by an integer between 0 and MAXNODE-1. The array field nodes represents the appropriate information assigned to each node. The array field arcs is a two-dimensional array representing every possible ordered pair of nodes. And is called adjacency matrix. In case of a weighted graph, each arc can also be assigned information. If the arcs of graph are not weighted and no other information assigned to arcs and nodes also, the graph declared simply by: int adj [MAXNODES][ MAXNODES]; the graph is totally described by its adjacency matrix.
Fatemah Ba_hareth
Chapter 9
Graphs
Primitive Operation Codes: • Non weighted graph: join(a,b) void join (int adj[][MAXNODES], int node1, int node2 ) { adj[node1][node2] = TRUE; }
remv(a,b)
void remv (int adj[][MAXNODES], int node1, int node2 ) { adj[node1][node2] = FALSE; }
adjacent(a,b)
void adjacent (int adj[][MAXNODES], int node1, int node2 ) { return (( adj[node1][node2] == TRUE)? TRUE:FALSE); } • Weighted graph: A weighted graph with a fixed number of nodes may be declared by: struct arc { int adj; int weight; }; struct arc g [MAXNODES][ MAXNODES];
joinwt(a,b,x)
void joinwt (struct arc g [ ][MAXNODES], int node1, int node2, int wt) { g[node1][node2].adj = TRUE; g[node1][node2].weight = wt; }
38
Fatemah Ba_hareth
Chapter 9
Graphs
Transitive Closure: Assume that a graph is completely describe by its adjacency matrix. The logical expression adj[i][k] && adj[k][j] equal TRUE if and only if there is a path of length 2 from i to j passing through k . Let us consider adj2 such that adj2 [i] [j] =TRUE if there is a path of length 2between i and j. that means adj2 is the path matrix of length 2. adj2 is the Boolean product of adj with itself. adj3 is the Boolean product of adj2 with adj. and so on..
Path matrix: In the graph of n nodes path [i][ j] = adj[i][ j] || adj2[i][ j] || ….. adjn[i][ j] the matrix path is often called the transitive closure of the matrix adj. void transclose ( int adj[ ] [MAXNODES], int path[ ][ MAXNODES]) { int i, j, k; int newprod[MAXNODES][ MAXNODES], adjprod[MAXNODES][ MAXNODES]; for( i= 0; i< MAXNODES; ++i) for( j=0; j< MAXNODES; ++j) adjprod[i][ j] = path[i][ j] = adj [i][ j]; for( i= 0; i< MAXNODES; ++i) { prod (adjprod, adj, adjprod); for( j=0; j< MAXNODES; ++j) for(k=0;k< MAXNODES; ++k) path[ j][k] = path[ j][k] || newprod[ j][k]; for( j=0; j< MAXNODES; ++j) for(k=0;k< MAXNODES; ++k) adjprod[i][j] = newprod [ j][k]; }/* end for */ } /* end transclose*/ The routine prod may be written as follows: void prod ( int a[ ] [MAXNODES], int b[ ][ MAXNODES], int c[ ][ MAXNODES]) { int i, j, k, val; for( i= 0; i< MAXNODES; ++i) for( j=0; j< MAXNODES; ++j) { val =FALSE; for(k=0;k< MAXNODES; ++k) val = val || ( a[i][k] && b[k][ j] ); c[i][ j] = val; }/* end for j*/ } /* end prod*/ 39
Fatemah Ba_hareth
Chapter 9
Graphs
Finding the Boolean product by the method prod is O(n3), where n is the number of graph nodes. In transeclose, this process (the call to prod) is embedded in a loop that is repeated n-1 times, so that the entire transitive closure routine is O(n4) .
Warshall's Algorithm: Let us define the matrix pathk such that pathk [i][ j] is true if and only if there is a path from node i to node j that does not pass through any nodes higher than k. How can the value of pathk+1 obtained from pathk ? pathk+1 [i][ j] = TRUE if and only if one of the following conditions holds: 1. pathk [i][ j] == TRUE 2. pathk [i][ k+1] == TRUE and pathk [ k+1] [ j]== TRUE void transclose ( int adj[ ] [MAXNODES], int path[ ][ MAXNODES]) { int i, j, k; for( i= 0; i< MAXNODES; ++i) for( j=0; j< MAXNODES; ++j) path[i][ j] = adj [i][ j]; for(k=0;k< MAXNODES; ++k) for( i=0; i< MAXNODES; ++i) if (path [i][k] ==TRUE) for( j=0; j< MAXNODES; ++j) path[ i][ j] = path[ i][ j] || path[k][ j]; } /* end transclose*/
This technique increase the efficiency of finding the transitive closure to O(n3).
40
Fatemah Ba_hareth
Chapter 9
Graphs
Shortest-Path Algorithm #define INFINITY … #define MAXNODES … #define MEMBER 1 #define NONMEMBER 0 void shortpath(int weight[][MAXNODES], int s, int t, int *pd, int precde[]) { int distance[MAXNODES],perm[MAXNODES]; int current, I, k, dc; int smalldist, newdist; for(i=0 ; i< MAXNODES; i++) { perm[i]= NONMEMBER; distance[i] = INFINITY; }/* end for */ perm[s]=0; distance[s]=0; current=s; while(current != t) { smalldist= INFINITY; dc = distance[current]; for(i=0 ; i< MAXNODES; i++) { if (perm[i] == NONMEMBER) { newdist = dc + weight[current][i]; if(newdist < distance[i]) { distance[i] = newdist; precede[i] = current; }/*end if */ if(distance[i] < smalldist) { smalldist = distance[i]; k=i; }/*end if */ }/* end for …. If */ current = k ; perm[current] = MEMBER; }/* end while */ *pd = distance[t]; }/* end shortpath */
41
Fatemah Ba_hareth
