Lecture 3: Graph Review Continued
CSC 226: Algorithms and Data Structures II Quinton Yong
quintonyong@ uvic.ca
Copyright By PowCoder代写 加微信 powcoder
A subgraph of 𝑮 = (𝑽,𝑬) is a graph 𝑮′ = (𝑽′,𝑬′) where
• 𝑽′ isasubsetof𝑽
• 𝑬′ consists of edges {𝒖,𝒗} in 𝑬 such that both 𝒖 and 𝒗 are in 𝑽′
A spanning subgraph 𝑮′ of 𝑮 contains all vertices of 𝑮
An induced subgraph 𝑮′ of 𝑮 contains all the edges of 𝑮 that have both endpoints in 𝑮′ (i.e. no edge of 𝑮 is
missing between all the vertices in 𝑮’) 𝑮=
Trees and Forests
A (free) tree is an undirected graph 𝑻 such that • 𝑻 is connected
• 𝑻 has no cycles
A rooted tree is a trees where one vertex is designated as the root
A forest is an undirected graph without cycles (collection of disconnected trees) • The connected components of a forest are trees
Rooted Tree
Spanning Trees and Forests
A spanning tree of a connected graph is a spanning subgraph that is a tree • A spanning tree is not unique unless the graph is a tree
Spanning Tree Spanning Tree A spanning forest of a graph is a spanning subgraph that is a forest
Graph Spanning Forest
Properties of Graphs, Trees, and Forests
Theorem: Let 𝑮 be an undirected simple graph with 𝒏 vertices and 𝒎 edges. Then have the following: • If𝑮isconnected,then𝒎≥𝒏−𝟏
• If 𝑮 is a tree, then 𝒎 = 𝒏 − 𝟏
• If 𝑮 is a forest, then 𝒎 ≤ 𝒏 − 𝟏
Number of Possible Spanning Subgraphs
How many possible spanning subgraphs are there for a given graph?
• Since all vertices must be included in the subgraph, we only have a “choice” about which edges to include
𝟐𝟏 = 𝟐 possibilities
𝟐𝟏 = 𝟐 possibilities
𝟐𝟐 = 𝟒 possibilities
Number of Possible Induced Subgraphs
How many possible induced subgraphs are there for a given graph?
𝟐𝟏 = 𝟐 possibilities
𝟐𝟐 = 𝟒 possibilities
Since all edges must be included between the vertices we choose, we only have a “choice” about which vertices to include
𝟐𝟑 = 𝟖 possibilities
Number of Possible Subgraphs
How many possible subgraphs are there for a given graph?
: =𝟏waytopick𝟎verticesoutof𝒏=𝟐vertices
• No edges included
= 𝟐 ways to pick 𝟏 vertex out of 𝒏 = 𝟐 vertices
• No edges included
= 𝟏 ways to pick 𝟐 vertices out of 𝒏 = 𝟐 vertices
We choose which vertices to include and which edges to include between those vertices
𝟏 subgraph 𝟐 subgraphs
𝟐 subgraphs
• For each way to pick 2 vertices (only one way), need to also consider which edges to include between those vertices
• Each edge (which are between the picked vertices) can be in or not
𝟓 possible subgraphs
Graph Representation: Set of Edges
Maintain a list of edges (array or linked list)
• Also have to store a separate list of vertices since some vertices have no edges
• Simple representation, but can be inefficient (e.g. traversal algorithms)
• To find all the vertices adjacent to a vertex, need to look through the entire list of edges (𝑶(𝒎))
• E.g. DFS will take 𝐎(𝒏 ⋅ 𝒎) time with this representation
Graph Representation: Adjacency Matrix
Maintain a 𝟐-dimensional 𝒏 × 𝒏 boolean array
• For each edge
𝒖, 𝒗 , 𝐚𝐝𝐣 𝒖
𝒖 = 𝐭𝐫𝐮𝐞 𝟏
𝟏 𝟐 𝟑 𝟒 𝟓 𝟔
• To find the vertices adjacent to a vertex, we need to look at a row in the matrix (𝑶(𝒏))
• Slightly more efficient than the edge list representation since there could be many more edges than
there are vertices
• e.g. DFS will take 𝑶(𝒏𝟐) time with this representation
• Best representation for querying if two vertices are adjacent (𝑶(𝟏))
• Requires a lot of storage space (𝑶(𝒏𝟐)), but good representation for dense graphs (many edges)
Graph Representation: Adjacency List
Maintain an array indexed by vertices which points to a list of adjacent vertices
𝟎 𝟏𝟑𝟐 𝟏𝟎𝟑 𝟐𝟎
• If the graph is sparse, the space required (𝑶(𝒏 + 𝒎)) is strictly less than the adjacency matrix representation
• To find the vertices adjacent to a vertex 𝒗, only takes 𝑶(deg(𝒗)) time
• Faster than both previous representations
• Adjacency lists are best for algorithms which involve finding all adjacent vertices
• DFS will take 𝑶(𝒏 + 𝒎) time with this representation
• Commonly used representation since it is the most efficient for most graphs
Note on Graph Implementations In Practice
What could you do to obtain the efficiency of adjacency lists while avoiding pointers / linked lists?
𝟎 𝟏𝟑𝟐 𝟏𝟎𝟑 𝟐𝟎
𝟑 𝟎𝟏𝟒 𝟒𝟑 𝟓𝟔
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com