Graph Algorithm
express | Algorithm代做 | 代做oop – 这是一个关于graph的题目, 主要考察了关于graph算法的内容,是一个比较经典的题目, 涵盖了graph/Algorithm/oop等代做方面
An undirected graph is specified byG= (V, E).Vdenotes the set of vertices (sometimes called nodes).E denotes the edges between pairs of nodes. By convention,n=|V|, m=|E|.
Aself-loopis an edge to and from the same node.
ASimple graphis a graph with no self-loops and no parallel edges.
Thedegreeof a node in an undirected graph is the number of edges connected to it. A self-l oop counts twice towards the degree of itsincidentvertex.
Nodesu, vareneighbors, oradjacentif they are connected by an edge. Given any set of nodesA, N(A) is the set of nodes which are neighbors to a node inA.
A
B
C D
E
F
Exercise 1.In the above graph, how many neighbors doesBhave? Name them.
Exercise 2.You have a graph with 10 vertices, and each node has degree 6. How many edges are there?
Exercise 3.Can you draw a graph with 5 vertices, each with degree 1?
Handshaking Theorem: Given an undirected graph withmedges, 2m=
P
vV deg(v).
Corollary to the Handshaking Theorem: An undirected graph has an even number of vertices with odd degree.
1 Representations of graphs
Two common ways to represent a graph areadjacency listandadjacency matrix. How would the graph above be represented in each format?
I & C SCI 46 Summer 2022 Daniel Frishberg University of California, Irvine Some of the documents in this course are either partly or completely a reproduction, with permission, of documents written by Professor Michael Shindler. This document may not be reposted without the express written permission of the instructor
2 Graph Traversals
2.1 Depth-First Search
Given a graphGand two nodessandt, how could we find a path fromstot?
For example, how do we find a path fromV 1 toV 6 in the following graph?
V 4
V 2
V 6
V 5
V 1
V 3
V 8
V 7
Depth-first search creates a tree, rooted at the starting vertex. Because the path between two vertices in a tree is unique, we can say that the path found is the unique path from the root to any given vertex. We can express the code iteratively or recursively:
DFS-recursive(u)
Markuas discovered
foreach edge (u, v)do
ifvis not marked discoveredthen
DFS-recursive(v)
end if
end for
DFS-iterative(s)
vdiscovered[v] =false
InitializeSto be a stack withsas its only element
whileSis not emptydo
upop(S)
ifdiscovered[u] =falsethen
discovered[u] =true
for alledges (u, v)do
push(S, v)
end for
end if
end while
Question 1.We can see that depth-first search findssome pathbetweenv 1 andv 6 ; does this find the shortest path?
I & C SCI 46 Summer 2022 Daniel Frishberg University of California, Irvine Some of the documents in this course are either partly or completely a reproduction, with permission, of documents written by Professor Michael Shindler. This document may not be reposted without the express written permission of the instructor
2.2 Breadth-First Search
Like DFS, this Algorithm will create a tree rooted at the start vertex.
BFS(G, s)
Setdiscovered[s] =trueanddiscovered[v] =falsefor all otherv
L[0]{s}
i 0
while L[i] is not emptydo
Make L[i+ 1] as empty list
for allverticesuL[i]do
for alledges (u, v)do
ifdiscovered[v] =falsethen
discovered[v]true
Addvto list L[i+ 1]
end if
end for
end for
ii+ 1
end while
Liconsists of all nodes whose shortest path tosis length exactlyi. If (x, y)E, thenx, ydiffer by at most one level. Question 2.Does Breadth-First Search find the shortest path between the start vertex and any other vertex? Do you have to make any assumptions about the edges relative importance to say this?
2.3 Graph Coloring
Thegraph coloringproblem is as follows. We are given a graphG= (V, E) and a positive integerk. We want to find out if we can assign each vertex one ofkcolors in such a way that no edge has both of its endpoints the same color. Sometimes, we are not given the valuek, and instead we want to find the smallest value ofkfor which the answer is yes. Question 3.A graph for whichk= 2 is possible is known as bipartite. Which of the following two graphs is bipartite?
C 4 C 5
Question 4.How can you use BFS to determine if a graph is bipartite?
I & C SCI 46 Summer 2022 Daniel Frishberg University of California, Irvine Some of the documents in this course are either partly or completely a reproduction, with permission, of documents written by Professor Michael Shindler. This document may not be reposted without the express written permission of the instructor