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

CS 1031lecture9 Trees A Quick Introduction to GraphsDefinition of TreesRooted Trees Binary TreesBinary Search Trees对外经济贸易大学《C++程序设计》 CS 1032Introduction to 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={1,2,3,4,5}E={(1,2), (2,3), (2,4), (4,2), (3,3), (5,4)}12534When (x,y) is an edge,we say that x is adjacent to y. 1 is adjacent to 2.2 is not adjacent to 1.4 is not adjacent to 3. 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 as smart as y”“x is a sibling of y”“x is bigger than y”‘x is faster than y”, … CS 1036Directed vs. Undirected GraphsIf the directions of the edges matter, then we show the edge directions, and the graph is called a directed graph (or a digraph)The previous two examples are digraphsIf the relationships represented by the edges are symmetric (such as (x,y) is edge if and only if x is a sibling of y), then we don’t show the directions of the edges, and the graph is called an undirected graph. CS 1037Examples of Undirected GraphsV=set of 6 people: John, Mary, Joe, Helen, Tom, and Paul, where the first 4 are siblings, and the last two are siblingsE ={(x,y) | x and y are siblings}JohnJoeMaryHelenTomPaul CS 1038Definition of Some Graph Related Concepts (Paths)A path in a graph G is a sequence of nodes x1, x2, …,xk, such that there is an edge from each node the next one in the sequenceFor example, in the first example graph, the sequence 4, 1, 2, 3