Name: 22.圖形優化 (22. Graph Optimization)
Uploaded: 2021-01-14T10:27:03.000Z
Duration: 1 h 18 min 40 s
Description: 【看影片學英語】數萬部 YouTube 影片，搭配英漢字典即點即查，輕鬆掌握單字發音與用法，長久累積看電影不必再看字幕。

基礎被動語態

The following content is provided under a Creative

Your support will help MIT OpenCourseWare

continue to offer high-quality educational resources for free.

To make a donation or to view additional materials

from hundreds of MIT courses, visit MIT OpenCourseWare

JULIAN SHUN: Hi, good afternoon, everyone.

going to have a guest lecture by Professor Johnson of the MIT

So please be sure to attend the guest lecture on Thursday.

So we're first going to remind ourselves what a graph is.

And then we're going to talk about various ways

And then we'll talk about how to implement

an efficient breadth-first search algorithm, both serially

And then I'll talk about how to use graph compression and graph

reordering to improve the locality of graph algorithms.

where vertices represent certain objects of interest,

and edges between objects model relationships between the two

For example, you can have a social network,

where the people are represented as vertices

and edges between people mean that they're

The edges in this graph don't have to be bi-directional.

So you could have a one-way relationship.

For example, if you're looking at the Twitter network,

Alice could follow Bob, but Bob doesn't necessarily

The graph also doesn't have to be connected.

But, for example, there could be some people

And then they're just off in their own component.

You can also use graphs to model protein networks, where

the vertices are proteins, and edges between vertices

means that there's some sort of interaction

So this is useful in computational biology.

so their relationship can go one way or both ways.

In this graph here, we have some directed edges and then also

some edges that are directed in both directions.

And then Alice follows Bob, and Bob also follows Alice.

If you use a graph to represent the world wide web,

and then the edges would denote that there is a hyperlink

And again, the edges here don't have to be bi-directional

because website A could have a link to website B.

So you can have a weight on the edge that

or some sort of distance measure corresponding

So here, I have an example where I am using a graph

a weight that corresponds to the distance between the two

And if I want to find the quickest way to get from city A

to city B, then I would be interested in finding

the shortest path from A to B in this graph here.

Here's another example, where the edge weights now

are the costs of a direct flight from city A to city B.

a flight from San Francisco to LA for $45.

way to get from one city to another city,

then, again, I would try to find the shortest path in this graph

Vertices and edges can also have metadata on them,

So, for example, here's the Google Knowledge Graph,

which represents all the knowledge on the internet

And here, the nodes have metadata on them.

So, for example, the node corresponding to da Vinci

is labeled with his date of birth and date of death.

corresponding to the type of knowledge that they refer to.

So you can see that some of these nodes are blue,

some of them are red, some of them are green,

and some of them have other things on them.

字幕列表影片播放

22.圖形優化 (22. Graph Optimization)

approach

access

constant

negative