对外经济贸易大学《C++程序设计》课件-lecture11Graphs.pptVIP

CS 1031Graphs Definition of Graphs and Related ConceptsRepresentation of GraphsThe Graph Class Graph TraversalGraph Applications对外经济贸易大学《C++程序设计》 CS 1032Definition of GraphsA graph is a finite set of nodes with edges between nodesFormally, a graph G is a structure (V,E) consisting of a finite set V called the set of nodes, anda set E that is a subset of VxV. That is, E is a set of pairs of the form (x,y) where x and y are nodes in V CS 1033Examples of GraphsV={0,1,2,3,4}E={(0,1), (1,2), (0,3), (3,0), (2,2), (4,3)}01423When (x,y) is an edge,we say that x is adjacent to y, and y is adjacent from x.0 is adjacent to 1.1 is not adjacent to 0.2 is adjacent from 1. CS 1034A “Real-life” Example of a GraphV=set of 6 people: John, Mary, Joe, Helen, Tom, and Paul, of ages 12, 15, 12, 15, 13, and 13, respectively.E ={(x,y) | if x is younger than y}JohnJoeMaryHelenTomPaul CS 1035Intuition Behind GraphsThe nodes represent entities (such as people, cities, computers, words, etc.)Edges (x,y) represent relationships between entities x and y, such as:“x loves y” “x hates y”“x is a friend of y” (note that this not necessarily reciprocal)“x considers y a friend”“x is a child of y”“x is a half-sibling of y”“x is a full-sibling of y”In those examples, each relationship is a different graph CS 1036Graph RepresentationFor graphs to be computationally useful, they have to be conveniently represented in programsThere are two computer representations of graphs:Adjacency matrix representationAdjacency lists representation CS 1037Adjacency Matrix RepresentationIn this representation, each graph of n nodes is represented by an n x n matrix A, that is, a two-dimensional array AThe nodes are (re)-labeled 1,2,…,nA[i][j] = 1 if (i,j) is an edgeA[i][j] = 0 if (i,j) is not an edge CS 1038Example of Adjacency Matrix014230 1 0 1 00 0 1 0 00 0 1 0 01 0 0 0 00 0 0 4 0A = CS 1039Another Example of Adj. MatrixRe-label the nodes with numerical labelsJohn 2Joe 3Mary 0Helen 1Tom 4Paul 50