[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] Linear Classification

图片
Linear Classification Discriminant functions Least squares for classification Fisher’s linear discriminant K-Nearest Neighbour(KNN) Classification What’s decision boundaries/linearly separable? The goal in classification is to take an input vector x and to assign it to one of K discrete classes \(C_k\) where k = 1,…,K. In the most common scenario, the classes are taken to be disjoint, so that each input is assigned to one and only one class. The input space is thereby divided into decision regions whose boundaries are called decision boundaries or decision surfaces. In this blog, we consider linear models for classification , by which we mean that the decision surfaces are linear functions of the input vector x and hence are defined by (D-1) -dimensional hyperplanes within the D-dimensional input space. For example: in 3D input space, the decision boundary will be a 2D surface What is Linear Separability Linearly separable data: Datasets whose classes can be separated by
阅读全文

[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
阅读全文

[CS231] Neural Networks

图片
Neural Network Table of Contents: Quick intro without brain analogies Modeling one neuron Biological motivation and connections Single neuron as a linear classifier Commonly used activation functions Neural Network architectures Layer-wise organization Summary Additional references Quick intro It is possible to introduce neural networks without appealing to brain analogies. In the section on linear classification we computed scores for different visual categories given the image using the formula \( s = W x \), where \(W\) was a matrix and \(x\) was an input column vector containing all pixel data of the image. In the case of CIFAR-10, \(x\) is a [3072x1] column vector, and \(W\) is a [10x3072] matrix, so that the output scores is a vector of 10 class scores. An example neural network would instead compute \( s = W_2 \max(0, W_1 x) \). Here, \(W_1\) could be, for example, a [100x3072] matrix transforming the image into a 100-dimensional intermediate vector. The funct
阅读全文