1 图的遍历
1.1 广度优先搜索
算法思想：以v为起点，由近至远一次访问和v有路劲相通且路径长度为1，2，3…的点
算法：
bool visited[MAX_VERTEX_NUM];
void BFSTraverse(Graph G){
for(int i=0;i<G.vexnum;i++)
visited[i]=false;
for(int i=0;i<G.vexnum;i++){
if(!visited[i])
BFS(G,i);
}
}
void BFS(Graph G, int v){
visit(v);
visited[v]=true;
Enqueue(Q,v);
while(! isEmpty(Q)){
Dequeue(Q,v);
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)
if(!visited(w)){
visit(w);
visited[w]=true;
Enqueue(Q,w);
}
}
}
1.2 深度优先搜索
算法思想：首先访问某一起始顶点v，再依次访问与v邻接的v1，与v1邻接的v2，…。直到不能再往下访问，退回到最近访问过的点，重复执行上述操作
bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G){
for(int i=0;i<G.vexnum;i++)
visited[i]=false;
for(int i=0;i<G.vexnum;i++){
if(!visited[i])
DFS(G,i);
}
}
void DFS(Graph G, int v){
visit(v);
visited[v]=true;
Enqueue(Q,v);
while(! isEmpty(Q)){
Dequeue(Q,v);
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)
if(!visited(w))
DFS(w);
}
}