第一科大網路組: 2012

Stack 堆疊

JAVA 的Stack類別表示後進先出(LIFO)的物件堆疊空間，是一群相同資料型態的組合，堆疊可用在撰寫五則運算，以下是常用的放法：

1. push()：把物件放進堆疊(Stack)空間的頂部，並傳回新的堆疊。

2. pop()：移除堆疊(stack)空間頂部的物件，並做為此函數的值返回該物件傳回新的堆疊。

3. peek()：取堆疊(stack)空間頂點物件(不刪除)。

4. empty()：查看堆疊(stack)空間是否為空的方法。(true：代表堆疊為空值;false：代表堆疊不是空值)

範例

import java.util.Stack;
//測試push()、empty()、pop()方法
public class testStack{
    public static void main(String args[]){
        Stack st=new Stack();
        //加入堆疊a,b,c
        String a="a";   st.push(a);   
        String c="c";   st.push(c);
        String b="b";   st.push(b);
        while(!st.empty()){  //判斷是否為空值
            System.out.println(st.pop()); //刪除堆疊頂端物件，並回傳該物件的值。
        }
        
    }
}

執行結果：

run:
b
c
a
BUILD SUCCESSFUL (total time: 1 second)

第六講：圖形 Graphs

定義
Elementary Operation
MST
Shortest path
Activity networks

專有名詞；vertex (點)    V集合
edge (邊)      E集合
     沒箭頭 =>undirected(無方向)
     有箭頭 =>directed(有方向)

Definition: A graph G consists of two sets

a finite, nonempty set of vertices V(G)
a finite, possible empty set of edges E(G)
G(V,E) represents a graph

An undirected graph is one in which the pair of vertices in a edge is unordered, (v0, v1) = (v1,v0)

A directed graph is one in which each edge is a directed pair of vertices, <v0, v1> ≠ <v1,v0>

G1:Complete graph G2 G3

V(G1)={0,1,2,3} E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}

V(G2)={0,1,2,3,4,5,6} E(G2)={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)}

V(G3)={0,1,2} E(G3)={<0,1>,<1,0>,<1,2>}

Definition: A complete graph is a graph that has the maximum number of edges

n for undirected graph with n vertices, the maximum number of edges is n(n-1)/2

n for directed graph with n vertices, the maximum
number of edges is n(n-1)

Example: G1 is a complete graph

Adjacent and Incident

n If (v0, v1) is an edge in an undirected graph,

n v0 and v1 are adjacent

n The edge (v0, v1) is incident on vertices v0 and v1

n If <v0, v1> is an edge in a directed graph

n v0 is adjacent to v1, and v1 is adjacent from v0

n The edge <v0, v1> is incident on v0 and v1

Simple Path

n A simple path is a path in which all vertices, except possibly the first and the last, are distinct

n A cycle is a simple path in which the first and the last vertices are the same

n In an undirected graph G, two vertices, v0 and v1, are connected if there is a path in G from v0 to v1

n An undirected graph is connected if, for every pair of distinct vertices vi, vj, there is a path from vi to vj

Connected Component

n A connected component of an undirected graph is a maximal connected subgraph.

n A tree is a graph that is connected and acyclic.

n A directed graph is strongly connected if there is a directed path from vi to vj and also from vj to vi.

n A strongly connected component is a maximal subgraph that is strongly connected.

※從Vi到Vj所經過的edge(點)序列，組成path
Simple path =>簡單路徑(不能重複)
「()」 =>代表無方向「<>」 =>代表有方向

Ex:
V(G1)={0,1,2,3}

考題

下圖中邊之數字代表成本

(1) 利用相鄰矩陣表示此圖成本

(2) 利用相鄰串列表示此圖成本

ANS：(1) (2)

考題

DFS(先深後廣)→以點的編號做順序

DFS：V₁→V₂→V₄→V₈→V₅→V₁₀→V₉→V₆→V₃→V₇

考題(交大)

Given the following undireeted graph

(1) show its adjacency matrix

(2) show its adjacency list

(3) show the depth-first spanning tree. Starting from node 0 and in alphabeticral order.

(4) Show the breadth-first spanningtree

ANS：

1. DFS：0→1→3→2→5→6→4

2. BFS：0→1→2→3→4→6→5

3. spanning tree不能有”cycle”

考題(雲科大)

(1) DFS: 1→ 2→ 4→ 3→ 5→ 7→ 8→ 6

(2) BFS: 1→ 2→ 3→ 4→ 5→ 8→ 6→ 7

＊Kruskal’s Algrithm

Step1：挑選最小成本的邊而且不會造成cycle。

Step2：重覆執行step1，直到產生n-1邊(頂點個數為n)

(放圖)

＊ Prime’s Algorithm

假設全部點集合為U

一、設定初始點U→放入集合V中，U=U-{V}

二、重復由U-V中挑選與U有edge相連且edge cost最小的點P將P放入V中，U=U-{P}，直到n個頂點選完。

＊ Sollin’s Algorithm

一、最出與各頂點相鄰小cost 的edge

二、刪除重覆的edge(只保留一個)

三、替每棵數挑選最小cost edge重復直到只剩一棵樹或無可挑為止

考題

Consider the following graph by performing minimum spanning tree algorithms by

(1) Kruskal’s

(2)Prim’s(start from vertex a)

(3) Sollin’s

(1)、(2)

(3)

＊最短路徑演算法(Dijkstra)

單一起點，distance[i]代表從頂點U到頂點i的最短距離

原理：甲→乙最短距離=Min{Dist(甲,乙),Min[Dist(甲,丙_i)+ Dist(丙_i,乙)]}

例題：

求甲→乙最短路徑

Dijkstra

疊代次數	挑選的點	丙₁	丙₂	丙₃	乙
初始	─	10	3	8	28
1	丙₂	10	3	5	28
2	丙₃	10	3	5	20
3	丙₁	10	3	5	20

說明：挑n-2次中間點

1.沒被挑過

2.所有U-i中最短距離

＊考題

Q：求V5到其他頂點的最短路徑長度

A：

疊代次數	挑選點	1	2	3	4	5	6	7	8
初始	V₅	無限大	無限大	無限大	1500	0	250	無限大	無限大
1	V₆	無限大	無限大	無限大	1250	0	250	1150	1650
2	V₇	無限大	無限大	無限大	1250	0	250	1150	1650
3	V₄	無限大	無限大	2450	1250	0	250	1150	1650
4	V₈	3350	無限大	2450	1250	0	250	1150	1650
5	V₃	3350	3250	2450	1250	0	250	1150	1650
6	V₂	3350	3250	2450	1250	0	250	1150	1650

＊考題

Q：求下最圖中，點b到g的最短路徑 A：b→g最短路徑為 b→c→a→d→g

疊代次數	挑選點	a	b	C	d	e	f	g
初始	B	7	0	2	無限大	無限大	無限大	無限大
1	C	6	0	2	無限大	7	無限大	無限大
2	A	6	0	2	10	7	無限大	16
3	E	6	0	2	10	7	14	16
4	D	6	0	2	10	7	14	12
5	F	6	0	2	10	7	14	12

如何找尋AOV-network的拓樸排序呢？

步驟1：在AOV-network中任意挑選沒有前行者的頂點

步驟2：輸出此頂點，並將此頂點所連接的邊刪除。重覆步驟1及步驟2，一值到全部的頂點皆輸出為止

例：拓樸排序過程如下，假設有一圖形：

A：V₁→V₂→V₆→V₃→V₄→V₅→V₇→V₈

＊考題(元智)

Q：For the graph below, illustrate each step to determine an order by topological sorting

(1)輸出1 (2)輸出2 (3)輸出3 (4)輸出5 (5)輸出4

A：12354

//============================================================

＊臨界路徑

(1)AOE網路上的活動是可以並行處理的，而一個計畫所需完成的最短時間，是從起始點到結束點間最長的路徑來算。長度為最長的路徑稱為臨界路徑

(2)臨界路徑可能不止一條

＊AOE-network上活動的時間

(1)最早開始時間(Early Start time)表示一活動最早開始的時間，以ES(i)表示活動ai最早開始時間

(2)最晚開始時間(Lastest Start time)指一活動在不影響整個計畫完成之下，最晚能夠開始進行的時間，以LS(i)表示活動ai最晚開始的時間

例：

AOE：頂點代表事件，邊代表工作，ai代表工作所需的時間

Q：(1)求計畫完成所需最少天數(2)求critical path?(3)每件工作Ai最早/晚開始

A：(1)23天

(2)最長路徑(臨界路徑)

(3)

天數	A₁	A₂	A₃	A₄	A₅	A₆	A₇	A₈	A₉	A₁₀	A₁₁	A₁₂	A₁₃	A₁₄
最早開始	0	0	5	6	6	9	12	12	9	9	16	13	16	21
最晚開始	4	0	9	6	6	9	15	12	15	15	16	19	19	21
	12-8		12-3		23-8				16-1	21-6		21-2	23-4

紅→可delay

＊考題(台北大學)

Q：(1)求計畫完成所需最少天數?

(2)求critical path?

(3)每件工作ai最早/晚開始

A：(1)23天

(2)最長路徑(臨界路徑)

(3)

天數	A₀	A₁	A₂	A₃	A₄	A₅	A₆	A₇	A₈	A₉	A₁₀	A₁₁	A₁₂	A₁₃
最早開始	0	0	5	6	6	12	12	12	15	15	16	19	16	21
最晚開始	1	0	6	6	12	12	15	12	15	15	16	19	19	21

紅→可delay

＊

第一科大網路組

2012年12月27日星期四

JAVA Stack(推疊)

PHP update

2012年12月26日星期三

資料結構Chapter6

第六講：圖形 Graphs

總網頁瀏覽量

2012年12月27日 星期四

JAVA Stack(推疊)

PHP update

2012年12月26日 星期三

資料結構Chapter6

第六講：圖形 Graphs

2012年12月27日星期四

2012年12月26日星期三