図の深さ優先ループと広さ優先ループ
3911 ワード
ここ数日、データ構造を復習する試験も、欠陥を調べて漏れを補う過程なので、手書きコードで記録します.また、c/c++クラスの中で実参与形参は再名できないほうがいいという問題で、長い間悩んでいたが、酔っ払っていた.
関数ポインタvoid(*visit)は、pythonの関数式プログラミングに類似したパラメータとして関数名を受信することができる.ポインタ関数int*visitの戻り値はアドレス値です.関数の戻り値は、同じタイプのポインタ変数で受け入れなければなりません.つまり、ポインタ関数には必ず関数の戻り値があります.また、プライマリコール関数では、関数の戻り値は同じタイプのポインタ変数に割り当てなければなりません.
次に、c/c++では、メンバー関数とメンバーパラメータは同じ名前にできません.
次に図の2つの遍歴方法1つ目はDFS(深さ優先遍歴)であり、1つの頂点から最も近い隣接頂点に再帰的にアクセスし続け、末端が他の隣接点のある頂点に戻るまで再帰的に行う.
2つ目は、BFS(広さ優先ループ)である、1つの頂点のすべての隣接頂点をエンキューしてアクセスし、順次デキューし、次に隣接頂点の隣接頂点をエンキューし続け、順次デキューしてアクセスが終了するまで繰り返している.
関数ポインタvoid(*visit)は、pythonの関数式プログラミングに類似したパラメータとして関数名を受信することができる.ポインタ関数int*visitの戻り値はアドレス値です.関数の戻り値は、同じタイプのポインタ変数で受け入れなければなりません.つまり、ポインタ関数には必ず関数の戻り値があります.また、プライマリコール関数では、関数の戻り値は同じタイプのポインタ変数に割り当てなければなりません.
次に、c/c++では、メンバー関数とメンバーパラメータは同じ名前にできません.
class A
{
private:
int a;
public:
A(int a){a=a;} // , a , a
}
次に図の2つの遍歴方法1つ目はDFS(深さ優先遍歴)であり、1つの頂点から最も近い隣接頂点に再帰的にアクセスし続け、末端が他の隣接点のある頂点に戻るまで再帰的に行う.
template<class T>
void AdjListUndirGraph::DFS(int v,void (*(visit)(const T &e)))const
{
SetTag(v,true);
T e;
GetElem(v,e);
(*visit)(e);
for(int w=FirstAdjVex(v);w>=0;w=NextAdjVex(v,w))
if(!GetTag(w))
DFS(w);
}
template<class T>
void AdjListUndirGraph::DFSTraverse(void (*(visit)(const T &e)))const
{
int v;
for(v=0;vfalse);
for(v=0;vif(!GetTag(v))
DFS(v,visit);
}
2つ目は、BFS(広さ優先ループ)である、1つの頂点のすべての隣接頂点をエンキューしてアクセスし、順次デキューし、次に隣接頂点の隣接頂点をエンキューし続け、順次デキューしてアクセスが終了するまで繰り返している.
template<class T>
void AdjListDirGraph::BFS(int v,void (*visit)(const T &e))const
{
SetTag(v,true);
T e;
GetElem(v,e);
(*visit)(e);
LinkQueue q;
q.InQueue(v);
while(!q.Empty())
{
int u,w;
q.OutQueue(u);
for(w=FirstAdjVex(u);w>=0;w=NextAdjVex(u,w))
if(!GetTag(w))
{
SetTag(w,true);
GetElem(w,e);
(*visit)(e);
q.InQueue(w);
}
}
template<class T>
void AdjListDirGraph::BFSTraverse(void (*visit)(const T &e))const
{
int v;
for(v=0;vfalse);
for(v=0;vif(!GetTag(v))
BFS(v,visit);
}