[ACE] Graphs

Graph

Definition of a graph

A graph is a set of nodes, or vertices, connected by edges.
Graphs can be
  • undirected - edges don’t have direction
  • directed - edges have direction
Undirected graphs can be represented as directed graphs where for each edge (X,Y) there is a corresponding edge (Y,X).
Graphs can also be
  • unweighted
  • weighted - edges have weights
  • enter image description here

Notation

  • Set V of vertices (nodes)
  • Set E of edges (E⊂V*V)
  • Node B is adjacent to A if there is an edge from A to B.(A —–>B)
  • enter image description here

Paths and reachability

A path from A to B is a sequence of vertices A1,…,An such that there is an edge from A to A1, from A1 to A2,… from An to B
Vertex B is reachable from A if there is a path from A to B

Other Terminology

  • A cycle is a path from a vertex to itself
  • Graph is acyclic if it does not have cycles
  • Graph is connected if there is a path between every pair of vertices
  • Graph is strongly connected if there is a path in both directions between every pair of vertices

how to implement a graph

As with lists, there are several approaches, but most common options are:
  • static indexed data structure –Adjacency matrix
  • dynamic data structure – Adjacency lists

    Adjacency matrix

  • Store node in an array: each node is associated with an integer(array index)
  • Represent information about the edges using a two dimensional array, where array[i][j] == 1 , iff there is an edge from node with index i to the node with index j.
  • For weighted graphs, place weights in the matrix(if there is no edge we use a value which can’t be confused with a weight, e.g. -1 or Integer.MAX_VALUE

Disadvantages of adjacency matrices

  • sparse graphs with few edges for number that are possible result in many zero entries in adjacency matrix
  • This wastes space and makes many algorithms less efficient
  • Also, if the number of nodes in the graph may change, matrix representation is too inflexible, especially if we don’t know the maximal size of the graph

Adjacency list

  • For every vertex, keep a list of adjacent vertices
  • Keep a list of vertices, or keep vertices in a Map (e.g. HashMap) as keys and lists of vertices as values
  • enter image description here

BFS and DFS

Graph traversals

Generally have three sets of nodes
1. Nodes that have not yet been discovered
2. “Working Set” - nodes we are currently processing in some way
3. Nodes that we have finished with

BFS

enter image description here

DFS

enter image description here
code here

Space complexity of BFS and DFS

For a general graph
  • Need a queue/stack of size |V|(the number of vertices)
  • Space complexity O(V)

If the graph is a tree

  • In DFS the stack will be the height, this can be as good as O(logn)
  • In BFS we still need to store all nodes of a level, hence is still O(n)
  • Hence in trees, DFS can be a lot more space efficient than BFS

Time complexity of BFS and DFS

  • In terms of the number of vertices V: two nested loops over V, hence at worst O(V^2).
  • More useful complexity estimate is in terms of the number of edges(usually, the number of edges is much less than V^2)
  • BFS time complexity : Gives a O(|V|+|E|) time complexity
  • Each vertex is enqueued and dequeued at most once. Scanning for all adjacent vertices takes O(|E|) time, since sum of lengths of adjacency lists is |E|.
  • DFS time complexity : Each vertex is pushed on the stack and popped at most once, For every vertex we check what the next unvisited neighbour is, so it is O(|V|+|E|) again

detect cycles in directed graph by DFS

  • Instead of visited and unvisited, use three “colors”
  • white = unvisited (not done)
  • grey = on the stack (half done)
  • black = finished
    enter image description here

评论

发表评论

此博客中的热门博文

[MLE] W2 Multivariate linear regression

图片
Multivariate linear regression What we have talked about in week 1 is linear regression with single feature. For example, in the house pricing predicting problem, we only use the size of house (x) to predict the price (y) . But what if there are other features like age, bedroom numbers and so on? Linear regression with multiple variables is also known as “multivariate linear regression” According to the graph above, we now have new representation symbols: n = number of features m = number of training examples \(x^{(i)}\) = \(i^{th}\) training example \(x^{(i)}_j\) = feature j in \(i^{th}\) training example 1416 is \(x_{1}^{(2)}\) in this case, m is 47 for example, n is 4. Hypothesis function The multivariable form of the hypothesis function accommodating these multiple features is as follows: if we make \(x_0\) to 1, the \(h_{\theta}(x)\) will be \(\theta^Tx\), which is \(\theta\) transpose matrix multiply by x, where \(\theta\) is a vector of 1 by(n+1) dimension an
阅读全文

[MLE] W1 Introduction

图片
Before get started The blog is based on the machine learning course on Coursera, taught by Andrew Ng . From today, i will begin my study trip on Machine learning, which will be labelled as MLE. This course will last 11 weeks and today is week 1. The application of machine learning is everywhere: Database mining Applications can’t program by hand Self-customizing program Understanding human learning(brain, real AI) Introduction What is Machine Learning Two definitions of machine learning are offered: Arthur Samuel described it as: “the field of study that gives computers the ability to learn without being explicitly programmed.” This is an older, informal definition. Tom Mitchell provides a more modern definition: “A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.” If we raise a example of what is machine learning: If
阅读全文

[AIM] MetaHeuristics

图片
Day2 Outline Metaheuristics -definition Single point based search method(simple stochastic local search) Iterated local search Scheduling Tabu Search Metaheuristic what is a metaheuristic? A metaheuristic is a high-level problem independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimization algorithms. what is the difference between heuristic and metaheuristic? Heuristic : Heuristics are problem-dependent techniques. As such, they usually are adapted to the problem at hand and they try to take full advantage of the particularities of this problem. However, because they are often too greedy, they usually get trapped in a local optimum and thus fail, in general, to obtain the global optimum solution. Metaheuristic : Meta-heuristics, on the other hand, are problem-independent techniques . As such, they do not take advantage of any specificity of the problem and, therefore, can be used as black boxes . In general, t
阅读全文