数据结构_图的遍历

深度优先搜索遍历

遍历思想

邻接矩阵上的遍历算法

void Map::DFSTraverse()
{int i, v;for (i = 0; i < MaxLen; i++){visited[i] = false;}for (i = 0; i < Vexnum; i++){// 如果顶点未访问，则进行深度优先搜索if (visited[i] == false){DFS(i);}}cout << endl;
}// 从第v个顶点出发递归地深度优先遍历图G
void Map::DFS(int v)
{int w, i, k;visited[v] = true; // 标记已访问cout << v << " ";// 找出与v相连接的其他所有顶点，存放在AdjVex数组中int* AdjVex = new int[Vexnum]; // 存放连接的顶点编号for (i = 0; i < Vexnum; i++){AdjVex[i] = -1;}// k是数组AdjVex的空位置下标，初始化为0表示数组AdjVex一开始没有数据k = 0;for (i = 0; i < Vexnum; i++){// 如果顶点i与v连接if (Maxtrix[v][i] == 1){AdjVex[k] = i;k++;}}i = 0;w = AdjVex[i];while (w != -1){// 如果顶点w未访问if (visited[w] == false){DFS(w);}i++;w = AdjVex[i];}delete[] AdjVex;
}

广度优先搜索遍历及其实现

实现

void Map::BFS(Graph G, int v)
{int w, u;queue<int> Q;visited[v] = true; // 访问第v个顶点cout << v << " ";  // 输出访问的顶点Q.push(v);while (!Q.empty()){u = Q.front();Q.pop();for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)){if (!visited[w]){cout << w << " ";visited[w] = true;Q.push(w);}}}
}

int Map::FirstAdjVex(Graph& G, int v)
{for (int i = 0; i < G.num; i++){if (G.arcs[v][i] != 0){return i;}}return -1;
}int Map::NextAdjVex(Graph& G, int v, int w)
{for (int i = w + 1; i < G.num; i++){if (G.arcs[v][i] != 0)return i;}return -1;
}