美文网首页
Lecture 3-4

Lecture 3-4

作者: zju_dream | 来源:发表于2019-01-15 00:30 被阅读0次

P4-

  • 连通图、有向图、计算出度入度

有向图的定义

  • If the edges are directed, the graph is said to be a directed graph. + 画图举例

无向图的定义

  • An undirected graph is a graph that is not directed. + 画图解释

入度 indegree

  • The indegree of vertex v is the number of edges that ends in v.
  • P6 有例子

P7.Path

  • A path in a graph is a sequence of vertices
  • A simple path(简单路径) is a path that does not contains same vertex more than once(except for the first and last vertices, which may be the same).
  • The length of a path is the number of edges in a path.

P8.Cycle in directed graph

  • 回路存在即不能进行拓扑排序
  • A cycle is a path of length at least one, and it starts and ends in the same vertex.

DAG

  • a directed graph contains no cycles

P10.Connected undirected graph

  • 概念判断、什么是强连通图、连通图、判断这个图是不是强连通的、判断是不是完全图
  • 完全的无向图里面的边数的关系

连通图(针对无向图而言的)

  • A connected graph is an undirected graph where is at least one path between each pair of vertices.

强连通图(针对有向图而言的)

  • A strongly connected graph is a directed graph where is at least one path between each pair of vertices.

弱连通图(针对有向图而言)

  • A directed graph is a weakly connected graph that is not strongly connected, but its underlaying graph is an undirected that is connected.

完全图(注意,此处是edge)

  • A complete graph is a graph where there is an edge between each pair of vertices.

P15.Tree

什么是树、判断是不是树
什么是树

  • 两种定义方式
    • A tree is an undirected graph where each pair of vertices is connected by exactly one path.
    • A tree connected with n vertices and n-1 edges.

判断是不是树🎄

  • A directed tree is a directed graph which would be a tree if the
    directions on the edges were ignored.(有向树不算树)

P18.Graph representation

  • 图的两种存储方式、把选择的那一种画出来
  • 各自的优缺点
    • 矩阵索引快,但是空间消耗大(存储较多无用的值0)
    • 链表查找慢,但是节省空间,没有无效存储
  • There are two different ways to represent graphs:
    • Adjacency matrix(还可细分为有向,无向,带权,带权的把1改成对应权值即可)
      • Space requirement: O(n^2)
    • Adjacency list P.22 具体是怎么样的要会画
      • Space requirement: O(v+n)
        Which of the representations that is best depends on the density of the network.
    • Adjacency matrix is best if the graph is dense(|E|约等于V^2)
    • Adjacency list is best if the graph is sparse(E<V^2)

The Shortest Path Problem

  • 算法要求
    • 无环
    • 有向
  • Dijkstra's algorithm

P29.Spanning Tree

  • A spanning tree of a graph is a subgraph of that graph, which:
    • Is a tree
    • connects to all vertices(如果是树,不是已经满足这个条件了吗?)

P30.MST最小生成树

根据这两个算法、画出MST、会画就可以了

Kruskal's algorithm

在不构成环的情况下,依次选择最短边。

Prim's algorithm

首先任意选择一个节点放入集合V,在不构成环的情况下,选择与这个集合中的点形成最短边的那个点。

P35.Topological ordering

  • 找出拓扑排序、并且解释为什么不能有环、彼此是彼此的依赖结点
  • A topological ordering of a DAG is an ordering of vertices such that if there is an edge(u, v) between u and v, then u comes before v in the ordering.

怎么求拓扑排序

  1. 求各个点的入度
  2. 将入度为0加入列表(顺序)
  3. 循环1.2,直到求完所有点

P42有例子

相关文章

网友评论

      本文标题:Lecture 3-4

      本文链接:https://www.haomeiwen.com/subject/vhzsdqtx.html