or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Syncing
xxxxxxxxxx
Operacijske raziskave - vaje 11.5.2020
Iskanje v globino
Časovna zahtevnost: \(O(m) + O(n)\) klicev
previsit
inpostvisit
Naloga 1
Na sledečem grafu izvedi iskanje v globino. V primerih, ko imaš več enakovrednih izbir, upoštevaj abecedni vrstni red. Za vsako povezavo določi, ali se nahaja v drevesu iskanja v globino.
Bellman-Fordov algoritem
Časovna zahtevnost: \(O(mn)\)
Naloga 2
S pomočjo Bellman-Fordovega algoritma določi razdalje od vozlišča \(A\) do ostalih vozlišč.
Topološko urejanje
Časovna zahtevnost: \(O(m)\)
Naloga 3
Dan je sledeči usmerjen acikličen graf.
Topološka ureditev: G, A, H, B, C, D, F, E
Časovna zahtevnost: \(O(m)\)
Naloga 4
Oviratlon je tekalna preizkušnja na 8 do 10 kilometrov dolgi poti z različnimi ovirami. Zanima nas, na koliko različnih načinov lahko pridemo od štarta do cilja. Dan je utežen usmerjen acikličen graf \(G\) ter vozlišči \(s\) in \(t\), ki predstavljata štart oziroma cilj. Uteži na povezavah nam predstavljajo, na koliko načinov jih lahko prečkamo.
Reši nalogo za sledeči graf.
Zapiši algoritem, ki reši dani problem. Kakšna je njegova časovna zahtevnost?