8.2 夕議贋刈燕幣!惣俊燕
惣俊燕(Adjacency List)頁夕議匯嶽乏會贋刈嚥全塀贋刈潤栽議贋刈圭隈。惣俊燕燕幣隈窃貌噐峯議頃徨全燕燕幣隈。祥頁斤噐夕G 嶄議耽倖競泣vi?繍侭嗤惣俊噐vi 議競泣vj 全撹匯倖汽全燕?宸倖汽全燕祥各葎競泣vi 議惣俊燕?壅繍侭嗤泣議惣俊燕燕遊慧欺方怏嶄?祥更撹阻夕議惣俊燕。壓惣俊燕燕幣嶄嗤曾嶽潤泣潤更?泌夕8.9 侭幣。
匯嶽頁競泣燕議潤泣潤更?万喇競泣囃?vertex?才峺?及匯訳惣俊円議峺寞囃?firstedge?更撹?総匯嶽頁円燕?軸惣俊燕?潤泣?万喇惣俊泣囃(adjvex)才峺?和匯訳惣俊円議峺寞囃(next)更撹。斤噐利夕議円燕俶壅奐譜匯倖贋刈円貧佚連?泌幡峙吉?議囃?info??利夕議円燕潤更泌夕8.10 侭幣。
惣俊燕燕幣議侘塀宙峰泌和?
?define MaxVerNum 100 /*恷寄競泣方葎100*/
typedef struct node{ /*円燕潤泣*/
int adjvex; /*惣俊泣囃*/
struct node * next; /*峺?和匯倖惣俊泣議峺寞囃*/
/*飛勣燕幣円貧佚連?夸哘奐紗匯倖方象囃info*/
}EdgeNode;
typedef struct vnode{ /*競泣燕潤泣*/
VertexType vertex; /*競泣囃*/
EdgeNode * firstedge; /*円燕遊峺寞*/
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum]; /*AdjList 頁惣俊燕窃侏*/
typedef struct{
AdjList adjlist; /*惣俊燕*/
int n,e; /*競泣方才円方*/
}ALGraph; /*ALGraph 頁參惣俊燕圭塀贋刈議夕窃侏*/
秀羨匯倖嗤?夕議惣俊燕贋刈議麻隈泌和?
void CreateALGraph(ALGraph *G)
{/*秀羨嗤?夕議惣俊燕贋刈*/
int i,j,k;
EdgeNode * s;
printf("萩補秘競泣方才円方(補秘鯉塀葎:競泣方,円方)?\n");
scanf("%d,%d",&(G->n),&(G->e)); /*響秘競泣方才円方*/
printf("萩補秘競泣佚連(補秘鯉塀葎:競泣催<CR>)?\n");
for (i=0;i<G->n;i++) /*秀羨嗤n 倖競泣議競泣燕*/
{scanf("\n%c",&(G->adjlist[i].vertex)); /*響秘競泣佚連*/
G->adjlist[i].firstedge=NULL; /*競泣議円燕遊峺寞譜葎腎*/
}
printf("萩補秘円議佚連(補秘鯉塀葎:i,j)?\n");
for (k=0;k<G->e;k++) /*秀羨円燕*/
{scanf("\n%d,%d",&i,&j); /*響秘円<Vi,Vj>議競泣斤哘會催*/
s=(EdgeNode*)malloc(sizeof(EdgeNode)); /*伏撹仟円燕潤泣s*/
s->adjvex=j; /*惣俊泣會催葎j*/
s->next=G->adjlist[i].firstedge; /*繍仟円燕潤泣s 峨秘欺競泣Vi 議円燕遊何*/
G->adjlist[i].firstedge=s;
}
}/*CreateALGraph*/
麻隈8.2
飛涙?夕嶄嗤n 倖競泣、e 訳円?夸万議惣俊燕俶n 倖遊潤泣才2e 倖燕潤泣。?堡撮t擶瀟(?(e<<n(n-1)/2)議秤趨和?喘惣俊燕燕幣夕曳惣俊裳專准福贋刈腎寂?輝才円屢購議佚連熟謹扮厚頁泌緩。
壓涙?夕議惣俊燕嶄?競泣vi 議業如葎及i 倖全燕嶄議潤泣方?遇壓嗤?夕嶄?及i倖全燕嶄議潤泣倖方峪頁競泣vi 議竃業?葎箔秘業?駅倬演煽屁倖惣俊燕。壓侭嗤全燕嶄凪惣俊泣囃議峙葎i 議潤泣議倖方頁競泣vi 議秘業。嗤扮?葎阻宴噐鳩協競泣議秘業賜參競泣vi 葎遊議察?辛參秀羨匯倖嗤?夕議剃惣俊燕?軸斤耽倖競泣vi 秀羨匯倖全俊參vi葎遊議察議全燕。箭泌夕8.12 侭幣葎嗤?夕G2?夕8.2?議惣俊燕才剃惣俊燕。 壓秀羨惣俊燕賜剃惣俊燕扮?飛補秘議競泣佚連軸葎競泣議園催?夸秀羨惣俊燕議鹸墫業葎O?n+e??倦夸?俶勣宥狛臥孀嘉嬬誼欺競泣壓夕嶄了崔?夸扮寂鹸墫業葎O?n·e?。
壓惣俊燕貧否叟孀欺販匯競泣議及匯倖惣俊泣才和匯倖惣俊泣?徽勣登協販吭曾倖競泣?vi 才vj?岻寂頁倦嗤円賜察屢銭?夸俶朴沫及i 倖賜及j 倖全燕?咀緩?音式惣俊裳專圭宴。
惣俊燕燕幣議侘塀宙峰泌和?
?define MaxVerNum 100 /*恷寄競泣方葎100*/
typedef struct node{ /*円燕潤泣*/
int adjvex; /*惣俊泣囃*/
struct node * next; /*峺?和匯倖惣俊泣議峺寞囃*/
/*飛勣燕幣円貧佚連?夸哘奐紗匯倖方象囃info*/
}EdgeNode;
typedef struct vnode{ /*競泣燕潤泣*/
VertexType vertex; /*競泣囃*/
EdgeNode * firstedge; /*円燕遊峺寞*/
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum]; /*AdjList 頁惣俊燕窃侏*/
typedef struct{
AdjList adjlist; /*惣俊燕*/
int n,e; /*競泣方才円方*/
}ALGraph; /*ALGraph 頁參惣俊燕圭塀贋刈議夕窃侏*/
秀羨匯倖嗤?夕議惣俊燕贋刈議麻隈泌和?
void CreateALGraph(ALGraph *G)
{/*秀羨嗤?夕議惣俊燕贋刈*/
int i,j,k;
EdgeNode * s;
printf("萩補秘競泣方才円方(補秘鯉塀葎:競泣方,円方)?\n");
scanf("%d,%d",&(G->n),&(G->e)); /*響秘競泣方才円方*/
printf("萩補秘競泣佚連(補秘鯉塀葎:競泣催<CR>)?\n");
for (i=0;i<G->n;i++) /*秀羨嗤n 倖競泣議競泣燕*/
{scanf("\n%c",&(G->adjlist[i].vertex)); /*響秘競泣佚連*/
G->adjlist[i].firstedge=NULL; /*競泣議円燕遊峺寞譜葎腎*/
}
printf("萩補秘円議佚連(補秘鯉塀葎:i,j)?\n");
for (k=0;k<G->e;k++) /*秀羨円燕*/
{scanf("\n%d,%d",&i,&j); /*響秘円<Vi,Vj>議競泣斤哘會催*/
s=(EdgeNode*)malloc(sizeof(EdgeNode)); /*伏撹仟円燕潤泣s*/
s->adjvex=j; /*惣俊泣會催葎j*/
s->next=G->adjlist[i].firstedge; /*繍仟円燕潤泣s 峨秘欺競泣Vi 議円燕遊何*/
G->adjlist[i].firstedge=s;
}
}/*CreateALGraph*/
麻隈8.2
飛涙?夕嶄嗤n 倖競泣、e 訳円?夸万議惣俊燕俶n 倖遊潤泣才2e 倖燕潤泣。?堡撮t擶瀟(?(e<<n(n-1)/2)議秤趨和?喘惣俊燕燕幣夕曳惣俊裳專准福贋刈腎寂?輝才円屢購議佚連熟謹扮厚頁泌緩。
壓涙?夕議惣俊燕嶄?競泣vi 議業如葎及i 倖全燕嶄議潤泣方?遇壓嗤?夕嶄?及i倖全燕嶄議潤泣倖方峪頁競泣vi 議竃業?葎箔秘業?駅倬演煽屁倖惣俊燕。壓侭嗤全燕嶄凪惣俊泣囃議峙葎i 議潤泣議倖方頁競泣vi 議秘業。嗤扮?葎阻宴噐鳩協競泣議秘業賜參競泣vi 葎遊議察?辛參秀羨匯倖嗤?夕議剃惣俊燕?軸斤耽倖競泣vi 秀羨匯倖全俊參vi葎遊議察議全燕。箭泌夕8.12 侭幣葎嗤?夕G2?夕8.2?議惣俊燕才剃惣俊燕。 壓秀羨惣俊燕賜剃惣俊燕扮?飛補秘議競泣佚連軸葎競泣議園催?夸秀羨惣俊燕議鹸墫業葎O?n+e??倦夸?俶勣宥狛臥孀嘉嬬誼欺競泣壓夕嶄了崔?夸扮寂鹸墫業葎O?n·e?。
壓惣俊燕貧否叟孀欺販匯競泣議及匯倖惣俊泣才和匯倖惣俊泣?徽勣登協販吭曾倖競泣?vi 才vj?岻寂頁倦嗤円賜察屢銭?夸俶朴沫及i 倖賜及j 倖全燕?咀緩?音式惣俊裳專圭宴。