Root at 3
1 3
Back edge and cross edge 2
6
5
9
10
4
5
0
4 1
3
1
2
3
4
8
9
7 8
6 5
7 6
3
7
2
6
4
8
1
7
5
9
10
0
8
9
2
dfn() and low()
Observation
– 若root有兩個以上child, 則為articulation point – 若vertex u有任一child w, 使得w及w後代無法透
visited[w->vertex] = TRUE;
}
}
} 例如:地毯式搜索
}
Connected component
Is it a connected graph?
– BFS(v) or DFS(v)
Find out connected component
void connected(void){ int i; for (i=0;i<n;i++){
過back edge到u的祖先, 則為 articulation point
low(u): u及後代,其back edge可達vertex之最 小dfn()
– low(u) = min{ dfn(u), min{low(w)|w是u的child}, min{dfn(w)|(u,w)是back edge}}
A example: dfs() and low()
1
3
Vertex 0 1 2 3 4 5 6 7 8 9
2
6
dfn 5 4 3 1 2 6 7 8 9 10 4
5
low 5 1 1 1 0
2
6
0
4 1
3
1
2
3
4 2
8
9
4
8
1
7
7
8
5
9
10
6
0
8
9
5
•請自行Trace Biconnected() 7 •Hint: 將Unvisited edge跟back edge送 6 入Stack, 到Articulation Point 再一次輸出
Definition: Biconnected graph
– 定義為無Articulation point的connected graph
Definition: Biconnected component
– Graph G中的Biconnected component H, 為G中最 大的biconnected subgraph; 最大是指G中沒有其 他subgraph是biconnected且包含入H
typedef struct node {
int vertex;
0
node_ptr link; } node;
1
2
node_ptr graph[MAX_VERTICES]; 3
int n = 0; /* number of nodes */
G1
312 230 130 012
Adjacency lists, by array
int marked; int vertex1; int vertex2; edge_ptr path1; edge_ptr path2; } edge; edge_ptr graph[MAX_VERTICES];
N1
0 2 N2 N3
N2
0 3 NIL N4
N3
1 2 N4 N5
N4
1 3 NIL N5
if(!visited[i]){ dfs(i); printf(“\n”);
} }
Spanning Tree
A spanning tree is a minimal subgraph
G’, such that V(G’)=V(G) and G’ is
connected
312
Weight and MST 0
N5
2 3 NIL NIL
Weighted edges
Cost Weight field Network
6.2 Elementary graph operations
Outlines
Operations similar to tree traversals
– Depth-First Search (DFS) – Breadth-First Search (BFS)
6.1.3 Graph representation
常見的表示法
Adjacency matrices Adjacency lists Adjacency multilists
0
4
2
15
6
3
7
G4
0
1
2
3
G1
0 1
2 G3
Adjacency matrix
n*n 陣列 n*(n-1),即 O(n2) If the matrix is sparse ?
queue_ptr front, rear;
typedef struct queue {
front=rear=NULL;
int vertex;
printf(“%5d”,v);
queue_ptr link;
visited[v]=TRUE;
};
addq(&front, &rear, v);
void addq(queue_ptr *, queue_ptr *, int);
A connected graph and its biconnected components
0
8
9
0
1
7
1
2
3
5
4
6
1
8 9
7 7
7
2
33
55
4
6
為何沒有任一個邊可能存在於兩個或多個biconnected component中?
DFS spanning tree of the graph in 6.19(a)
Is it a connected graph? Spanning trees Biconnected components
Depth-First Search
int visited[MAX_VERTICES]; void dfs(int v) {
node_ptr w; visited[v] = TRUE; printf(“%5d”, v); for (w = graph[v]; w; w = w->link)
230
1
2
130
0
0
3
1
2
1
2
G1
012
3
3
DFS(0)
BFS(0)
Biconnected components
Definition: Articulation point (關節點)
– 原文請參閱課本 – 如果將vertex v以及連接的所有edge去除,產生
graph G’, G’至少有兩個connected component, 則 v稱為 articulation point
while(front) {
Int deleteq(queue_ptr);
v = deleteq(&front);
for(w=graph[v]; w; w=w->link)
if(!visited[w->vertex]) {
printf(“%5d”, w->vertex);
addq(&front, &rear, w->vertex);
0
0 1 0
1
1 0 1
2
0 0 0
G3
1 20
0123456 4577120
0
Adjacency multilists 1 2 3
m vertex1 vertex2 list1 list2
G1
N0
0 1 N1 N3
typedef struct edge *edge_ptr; Typedef struct edge {
– 大部分元素是0 – e << (n2/2)
0
1 3 G1
0
0 1 0 1 1 0 1 2 0 0 0
G3
0 1 1 1 2 1 0 1 1
1 1 0 1 1 1 1 0
Adjacency lists 0
1
n個linked list
1 20
2
#define MAX_VERTICES 50
G3
typedef struct node *node_ptr;
if(!visited[w->vertex]) dfs(w->vertex);
}
Adjacency list: O(e) Adjacency Mtx: O(n2) 例如:老鼠走迷宮
Breadth-First Search
void bfs(int v) {
node_ptr w;
typedef struct queue *queue_ptr;