1

Transcription

1 基本練習題 1. 答 : 鄰接矩陣 : D E D E D E D E 鄰接串列 : List[] List[] E List[] E List[] D E List[D] E List[E] D List[] List[] D List[] List[] E List[D] E List[E]

2 2. 答 : D E D E D E D E List[] List[] List[] List[] List[D] 1 4 E D 2 E 5 2 E 2 List[E] 3 5 D 2 List[] List[] List[] List[] List[D] List[E] E 3 5 D E 2

3 3. 答 : 動作說明 佇列 (queue) 已拜訪頂點 初始狀態 front rear 拜訪, Enqueue() Dequeue 得, 將所有與 相鄰 且未被拜訪的頂點一一拜訪且 Enqueue,(,),, Dequeue 得, 將所有與 相鄰且未被拜訪的頂點一一拜訪且 Enqueue,(D,E) D E,,,D,E Dequeue 得, 將所有與 相鄰且未被拜訪的頂點一一拜訪且 Enqueue,(F,G) D E F G,,,D,E, F,G Dequeue 得 D, 將所有與 D 相鄰且未被拜訪的頂點一一拜訪且 Enqueue,(H) E F G H,,,D,E,F G,H Dequeue 得 E, 將所有與 E 相鄰且未被拜訪的頂點一一拜訪且 Enqueue,( 無 ) F G H,,,D,E,F G,H Dequeue 得 F, 將所有與 F 相鄰且未被拜訪的頂點一一拜訪且 Enqueue,(I) G H I,,,D,E,F G,H,I Dequeue 得 G, 將所有與 G 相鄰且未被拜訪的頂點一一拜訪且 Enqueue,( 無 ) H I,,,D,E,F G,H,I

4 Dequeue 得 H, 將所有與 H 相鄰且未被拜訪的頂點一一拜訪且 Enqueue,( 無 ) I,,,D,E,F G,H,I Dequeue 得 I, 將所有與 I 相鄰且 未被拜訪的頂點一一拜訪且 Enqueue,( 無 ),,,D,E,F G,H,I 佇列已空, 停止 4. 答 : 動作說明 堆疊 ( stack ) 已拜訪頂點 初始狀態 top 將起點 推入堆疊 拜訪, 將所有與 相鄰且未被拜訪的頂點一一推入堆疊 Push(,) Pop 得, 拜訪, 將所有與 相鄰且未被拜訪的頂點一一 Push,(E,F,G) Pop 得 G, 拜訪 G, 將所有與 G 相鄰且未被拜訪的頂點一一 Push,(I) Pop 得 I, 拜訪 I, 將所有與 I 相鄰且未被拜訪的頂點一一 Push,(F) Pop 得 F, 拜訪 F, 將所有與 F 相鄰且未被拜訪的頂點一一 Push,( 無 ) G F E I F E F F E F E,,,G,,G,I,,G,I,F

5 Pop 得 F, F 已拜訪過 E,,G, I, F Pop 得 E, 拜訪 E, 將所有與 E 相鄰且未被拜訪的頂點一一 Push,() Pop 得, 拜訪, 將所有與 相鄰且未被拜訪的頂點一一 Push,(D) Pop 得 D, 拜訪 D, 將所有與 D 相鄰且未被拜訪的頂點一一 Push,(H) Pop 得 H, 拜訪 H, 將所有與 H 相鄰且未被拜訪的頂點一一 Push,( 無 ) Pop 得, 已被拜訪, 堆疊已空, 停止 D H,,G, I, F, E,,G, I, F, E,,G, I, F, E,D,,G, I, F, E,D,H,,G, I, F, E,D,H 5. 答 : D 3 F 2 E 6. 答 : D F 2 E

6 7. 答 : D E F G 進階練習題 1. 答 : 不一定是唯一的 當有多個邊加權相同而且任選一邊加入都不會構成環路時, 任選一邊均可, 但可能因而造成不同的最少花費展開樹 例如下圖, 邊 (,) 和 (,D) 邊長均為 2, 選擇任一個都是正確的, 但會造成兩棵不同的最少花費展開樹 D 2 2 圖形 G D 1 D 2 2 最少花費展開樹 1 最少花費展開樹 2 2. 答 : Decided vertices V1 V2 V3 V4 V5 V6 V0 4/0 5/0 3/0 /0 /0 /0 V0,V1 4/0 4/3 /0 9/3 11/3 V0,V1,V2 4/3 8/1 9/3 11/3 V0V1V2V3 8/1 6/2 11/3 V0V1V3V2V4 8/1 10/5 V0V1V3V2V4V5 10/5 V0 到 V6 的最短距離為 :10 V0 到 V6 的最短路徑為 :V6 <- V5 <- V2 <-V3<- V0, 亦即 V0 -> V3 -> V2 ->

7 V5->V6 V0 至其餘各點以此類推 3. 答 : 先算出每個頂點的最早時間和最晚時間 頂 點 D E F G 最早時間 最晚時間 因此到達頂點 G 的最早時間為 16 再算出每個工作的最早時間和最晚時間 工 作 D E D D DF DG EG FG 最早時間 最晚時間 最早時間和最晚時間相等的, 即為關鍵路徑上的邊 因此關鍵路徑為 : -> -> D -> F -> G n 4. 答 :(D) M ( i, j) /2 n i= 1 j = 1 5. 答 :(D) 程式題 1. 答 : #include <stdio.h> #include <stdlib.h> #define MX_ITEM 20 #define MX_V 20 /* 最多頂點數目 */

8 void FS(); void Visit(); int Enqueue(); int Dequeue(); int IsEmpty(); char Find_dj(); void ReaddjMatrix(); typedef struct tagqueue int item[mx_item]; int front; int rear; QUEUE; QUEUE q; int RealV; int ol; int Visited[MX_V]; int [MX_V][MX_V]; void main(void) int V0; ReaddjMatrix(); printf(" 請輸入起點 : "); scanf("%d",&v0); FS(V0); void ReaddjMatrix(void) int i,j; FILE *fin; if ((fin=fopen("fs.dat","r")) == NULL ) printf("fs.dat Not Found!\n"); exit(1); fscanf(fin,"%d",&realv); if (RealV>MX_V)

9 RealV = MX_V; for ( i=0 ; i<realv; i++) for (j=0; j<realv; j++) fscanf(fin,"%d",&[i][j]); fclose(fin); void FS (int V0) int Vx,Vy; Visit(V0); Enqueue(V0); while(!isempty()) Dequeue(&Vx); Vy=Find_dj(Vx,1); while(vy!=-1) Visit(Vy); Enqueue(Vy); Vy=Find_dj(Vx,0); void Visit(int Vx) Visited[Vx]=1; printf("v%2d\n",vx); int Enqueue(int Vx) if ((q.rear+1)%mx_item==q.front) return(0); q.rear=(q.rear+1)%mx_item; q.item[q.rear]=vx; return(1); int Dequeue(int *Vx)

10 if(isempty()) return(0); q.front=((q.front+1)%mx_item); *Vx=q.item[q.front]; return(1); int IsEmpty() if(q.front == q.rear) return (1); return (0); char Find_dj(int Vx,char first) if (first) ol=0; ol++; while(ol < RealV) if ([Vx][ol]==0 Visited[ol]) ol++; return (ol); return (-1); FS.dat 的內容

11 答 : #include <stdio.h> #include <stdlib.h> #define MX_ITEM 20 #define MX_V 20 /* 最多頂點數目 */ typedef struct tagstk int item[mx_item]; /* 資料欄位 */ int top; STK; STK S; void DFS(); void Visit(); char Find_dj(); int PUSH(),IsFull(),POP(),IsEmpty(); void ReaddjMatrix(); int RealV; int ol; int Visited[MX_V]; int [MX_V][MX_V];

12 void main(void) int V0; ReaddjMatrix(); printf(" 請輸入起點 :"); scanf("%d",&v0); DFS(V0); void ReaddjMatrix(void) int i,j; FILE *fin; if ((fin=fopen("dfs.dat","r")) == NULL ) printf("dfs.dat Not Found!\n"); exit(1); fscanf(fin,"%d",&realv); if (RealV>MX_V) RealV = MX_V; for ( i=0 ; i<realv; i++) for (j=0; j<realv; j++) fscanf(fin,"%d",&[i][j]); fclose(fin); void DFS(int V0) int Vx,Vy; PUSH (V0); while(!isempty(&s)) POP (&Vx); if(!visited[vx]) Visit(Vx); Vy=Find_dj(Vx,1); while(vy!=-1) PUSH(Vy); Vy=Find_dj(Vx,0);

13 void Visit(int Vx) Visited[Vx]=1; printf("v%2d\n",vx); char Find_dj(int Vx,char first) if (first) ol=0; ol++; while(ol < RealV) if ([Vx][ol]==0 Visited[ol]) ol++; return (ol); return(-1); int PUSH(int X) if(isfull(&s)) return(0); S.top=S.top+1; S.item[S.top]=X; return(1); int IsFull(STK *s) if (s->top == (MX_ITEM-1)) return(1);

14 return(0); int POP(int *X) if(isempty(&s)) return (0); *X=S.item[S.top]; S.top--; return(1); int IsEmpty(STK *s) if(s->top == -1) return(1); return(0); DFS.dat 的內容

15 3 答 : #include <stdio.h> #include <stdlib.h> #define MX_ITEM 20 #define MX_V 20 /* 最多頂點數目 */ void FS(int); void Visit(int); int Enqueue(); int Dequeue(); int IsEmpty(); char Find_dj(); void ReaddjList(); void InsertNode(int,int); typedef struct tagqueue int item[mx_item]; int front; int rear; QUEUE; QUEUE q; int RealV; int Visited[MX_V]; typedef struct tagnode int data; struct tagnode *next; NODE; NODE [MX_V]; NODE *ol; void main(void) int V0; ReaddjList();

16 printf(" 請輸入起點 : "); scanf("%d",&v0); FS(V0); void InsertNode(int Row,int ol) NODE *p,*newnode; for( p=&[row]; (p->next!=null)&&(p->data<ol); p=p->next); if ((NewNode=(NODE *)malloc(sizeof(node))) ==NULL) return; NewNode->data=ol; NewNode->next=p->next; p->next = NewNode; void ReaddjList(void) int i,j,indata; FILE *fin; if ((fin=fopen("fs.dat","r")) == NULL ) printf("fs.dat Not Found!\n"); exit(1); fscanf(fin,"%d",&realv); if (RealV>MX_V) RealV = MX_V; for ( i=0 ; i<realv; i++) [i].next = NULL; for (j=0; j<realv; j++) fscanf(fin,"%d",&indata); if (InData==1) InsertNode(i,j); fclose(fin); void FS (int V0)

17 int Vx,Vy; Visit(V0); Enqueue(V0); while(!isempty()) Dequeue(&Vx); Vy=Find_dj(Vx,1); while(vy!=-1) Visit(Vy); Enqueue(Vy); Vy=Find_dj(Vx,0); void Visit(int Vx) Visited[Vx]=1; printf("v%2d\n",vx); int Enqueue(int Vx) if ((q.rear+1)%mx_item==q.front) return(0); q.rear=(q.rear+1)%mx_item; q.item[q.rear]=vx; return(1); int Dequeue(int *Vx) if(isempty()) return(0); q.front=((q.front+1)%mx_item); *Vx=q.item[q.front]; return(1);

18 int IsEmpty() if(q.front == q.rear) return (1); return (0); char Find_dj(int Vx,char first) if (first) ol=[vx].next; ol=ol->next; while(ol!= NULL) if (Visited[ol->data]) ol=ol->next; return (ol->data); return (-1); 4 答 : #include <stdio.h> #include <stdlib.h> #include <conio.h> #define MX_ITEM 20 #define MX_V 20 /* 最多頂點數目 */ void FS(); void ddedge(int,int); void Visit(); int Enqueue(); int Dequeue(); int IsEmpty(); char Find_dj();

19 void ReaddjMatrix(); typedef struct tagqueue int item[mx_item]; int front; int rear; QUEUE; QUEUE q; int RealV; int ol; int Visited[MX_V]; int [MX_V][MX_V]; void main(void) int V0; ReaddjMatrix(); printf(" 請輸入起點 : "); scanf("%d",&v0); FS(V0); getch(); void ReaddjMatrix(void) int i,j; FILE *fin; if ((fin=fopen("fs.dat","r")) == NULL ) printf("fs.dat Not Found!\n"); exit(1); fscanf(fin,"%d",&realv); if (RealV>MX_V) RealV = MX_V; for ( i=0 ; i<realv; i++) for (j=0; j<realv; j++) fscanf(fin,"%d",&[i][j]); fclose(fin);

20 void FS (int V0) int Vx,Vy; Visit(V0); Enqueue(V0); while(!isempty()) Dequeue(&Vx); Vy=Find_dj(Vx,1); while(vy!=-1) Visit(Vy); ddedge(vx,vy); Enqueue(Vy); Vy=Find_dj(Vx,0); void ddedge(int Vx,int Vy) printf("dd Edge (V%2d,V%2d)\n",Vx,Vy); void Visit(int Vx) Visited[Vx]=1; printf("v%2d\n",vx); int Enqueue(int Vx) if ((q.rear+1)%mx_item==q.front) return(0); q.rear=(q.rear+1)%mx_item; q.item[q.rear]=vx; return(1);

21 int Dequeue(int *Vx) if(isempty()) return(0); q.front=((q.front+1)%mx_item); *Vx=q.item[q.front]; return(1); int IsEmpty() if(q.front == q.rear) return (1); return (0); char Find_dj(int Vx,char first) if (first) ol=0; ol++; while(ol < RealV) if ([Vx][ol]==0 Visited[ol]) ol++; return (ol); return (-1);

22 5. 答 : #include <stdio.h> #include <stdlib.h> #define MX_ITEM 20 #define MX_V 20 /* 最多頂點數目 */ typedef struct tagstk int item[mx_item]; /* 資料欄位 */ int top; STK; STK S; void DFS(); void ddedge(int,int); void Visit(); char Find_dj(); int PUSH(),IsFull(),POP(),IsEmpty(); void ReaddjMatrix(); int RealV; int ol; int Visited[MX_V]; int [MX_V][MX_V]; void main(void) int V0; ReaddjMatrix(); printf(" 請輸入起點 :"); scanf("%d",&v0); DFS(V0); void ReaddjMatrix(void) int i,j; FILE *fin; if ((fin=fopen("dfs.dat","r")) == NULL )

23 printf("dfs.dat Not Found!\n"); exit(1); fscanf(fin,"%d",&realv); if (RealV>MX_V) RealV = MX_V; for ( i=0 ; i<realv; i++) for (j=0; j<realv; j++) fscanf(fin,"%d",&[i][j]); fclose(fin); void DFS(int Vs) int Vx,Tempol; Visit(Vs); Vx=Find_dj(Vs,1); while(vx!=-1) Tempol=ol; ddedge(vs,vx); DFS(Vx); ol=tempol; Vx=Find_dj(Vs,0); void ddedge(int Vx,int Vy) printf("dd Edge (V%2d,V%2d)\n",Vx,Vy); void Visit(int Vx) Visited[Vx]=1; printf("v%2d\n",vx); char Find_dj(int Vx,char first)

24 if (first) ol=0; ol++; while(ol < RealV) if ([Vx][ol]==0 Visited[ol]) ol++; return (ol); return(-1); int PUSH(int X) if(isfull(&s)) return(0); S.top=S.top+1; S.item[S.top]=X; return(1); int IsFull(STK *s) if (s->top == (MX_ITEM-1)) return(1); return(0); int POP(int *X) if(isempty(&s)) return (0); *X=S.item[S.top]; S.top--; return(1);

25 int IsEmpty(STK *s) if(s->top == -1) return(1); return(0); 6. 答 : #define MX_V 20 /* 最多頂點數目 */ int RealV; typedef struct tagnode int data; struct tagnode *next; NODE; NODE [MX_V]; void InsertNode(int Row,int ol) NODE *p,*newnode; for( p=&[row]; (p->next!=null)&&(p->data<ol); p=p->next); if ((NewNode=(NODE *)malloc(sizeof(node))) ==NULL) return; NewNode->data=ol; NewNode->next=p->next; p->next = NewNode; void ReaddjList(void) int i,j,indata; FILE *fin; if ((fin=fopen("fs.dat","r")) == NULL ) printf("fs.dat Not Found!\n");

26 exit(1); fscanf(fin,"%d",&realv); if (RealV>MX_V) RealV = MX_V; for ( i=0 ; i<realv; i++) [i].next=null; for (j=0; j<realv; j++) fscanf(fin,"%d",&indata); if (InData==1) InsertNode(i,j); fclose(fin); 7. 答 : #include <stdio.h> #include <stdlib.h> #define MX_V 20 int Real_V; int OST[MX_V][MX_V]; int [MX_V][MX_V],P[MX_V][MX_V]; void Floyd(void); void SearchPath(); void ReadWeightedM(void); // Read Weighted djacency Matrix from file Floyd.dat void main(void) ReadWeightedM(); Floyd(); SearchPath(P);

27 void ReadWeightedM(void) int i,j; FILE *fin; if ((fin=fopen("floyd.dat","r")) == NULL) printf("floyd.dat Not Found!"); exit(1); fscanf(fin,"%d",&real_v); for (i=0; i<real_v; i++) for (j=0; j<real_v;j++) fscanf(fin,"%d",&ost[i][j]); fclose(fin); void Floyd(void) int i,j,k; for(i=0;i <Real_V;i++) for(j=0;j < Real_V;j++) [i][j]=ost[i][j]; P[i][j]=j; for(k=0;k < Real_V;k++) for(i=0;i < Real_V;i++) for(j=0;j < Real_V;j++) if([i][j] > [i][k]+[k][j]) [i][j]=[i][k]+[k][j]; P[i][j]=P[i][k]; void SearchPath(int P[][MX_V])

28 int i,j,row; for(i=0;i < Real_V;i++) for(j=0;j < Real_V;j++) printf("shortest Path from V%d to V%d cost is:%d\n",i,j,[i][j]); printf("shortest path is:\n from v%d",i); row=p[i][j]; while(row!= j) printf(" to V%d",row); row=p[row][j]; printf(" to V%d\n",row);