1、設有兩個集合a和集合b,要求設計生成集合c=a∩b的演算法,其中集合a、b和c用鏈式儲存結構表示。
typedef struct node lklist;
void intersection(lklist *ha,lklist *hb,lklist *&hc)}}
2、設指標變數p指向雙向鍊錶中結點a,指標變數q指向被插入結點b,要求給出在結點a的後面插入結點b的操作序列(設雙向鍊錶中結點的兩個指標域分別為llink和rlink)。
3、 將頂點放在兩個集合v1和v2。對每個頂點,檢查其和鄰接點是否在同乙個集合中,如是,則為非二部圖。為此,用整數1和2表示兩個集合。再用一佇列結構存放圖中訪問的頂點。
int bpgraph (adjmatrix g)
判斷以鄰接矩陣表示的圖g是否是二部圖。
//初始化,各頂點未確定屬於那個集合
q[1]=1; r=1; s[1]=1;//頂點1放入集合s1
while(f //鄰接點入佇列
else if (s[j]==s[v]) return(0);} //非二部圖
}//if (!visited[v])
}//while
return(1); }//是二部圖
[演算法討論] 題目給的是連通無向圖,若非連通,則演算法要修改。
2023年黑龍江省資料總結高階
1 二部圖 bipartite graph g v,e 是乙個能將其結點集v分為兩不相交子集v 1和v2 v v1的無向圖,使得 v1中的任何兩個結點在圖g中均不相鄰,v2中的任何結點在圖g中也均不相鄰。1 請各舉乙個結點個數為5的二部圖和非二部圖的例子。2 請用c或pascal編寫乙個函式bipa...
2023年黑龍江省資料總結高階
1 二部圖 bipartite graph g v,e 是乙個能將其結點集v分為兩不相交子集v 1和v2 v v1的無向圖,使得 v1中的任何兩個結點在圖g中均不相鄰,v2中的任何結點在圖g中也均不相鄰。1 請各舉乙個結點個數為5的二部圖和非二部圖的例子。2 請用c或pascal編寫乙個函式bipa...
2023年黑龍江省資料總結高階
1 二部圖 bipartite graph g v,e 是乙個能將其結點集v分為兩不相交子集v 1和v2 v v1的無向圖,使得 v1中的任何兩個結點在圖g中均不相鄰,v2中的任何結點在圖g中也均不相鄰。1 請各舉乙個結點個數為5的二部圖和非二部圖的例子。2 請用c或pascal編寫乙個函式bipa...