图之深搜与广搜

邻接矩阵的定义：

#define MAXVEX 100
typedef char VertexType;
typedef int EdgeType;
struct GraphStruct;
typedef struct GraphStruct *Graph;
struct GraphStruct{VertexType vexs[MAXVEX]; /*顶点，下标从0开始*/EdgeType edge[MAXVEX][MAXVEX]; /*邻接矩阵*/int vertexNum,edgeNum;
};

邻接表的定义：

#define MAXVEX 100 /*最大顶点数*/
typedef char VertexType;
struct GraphStruct;
typedef struct GraphStruct *Graph;typedef struct ENode{int adjVertex;  /*该边所指的顶点的位置*/int weight;     /*边的权*/struct ENode *nextEdge;  /*指向下一条边的指针*/
}ENode;typedef struct VNode{VertexType data;   /*顶点信息*/ENode *firstEdge; /*指向第一条依附该顶点的边的弧指针*/
}VNode;struct GraphStruct{VNode vexs[MAXVEX];int vertexNum,edgeNum; /*图的当前顶点数和弧数*/
};

无向带权图(邻接表)

完成void BFS(Graph g,int k)函数，该函数从第k个点开始广度优先遍历图g，遍历过程中把访问过的顶点的设置为1(初始为0)。请注意，在测试代码中已经完成int (Graph g, v);函数(在图g中查找顶点v的序号，不存在返回-1)，你可以直接调用。

我们这里怎么实现图的深搜：

void DFS(Graph g,int v0)
{ENode* p; int w;g->vexs[v0].visited=1;p=g->vexs[v0].firstEdge;while(p!=NULL){//每一个while循环，都是同一个节点的边。 w=p->adjVertex;if(g->vexs[w].visited==0){DFS(g,w);//每一次DFS都是更进一层的循环 }p=p->nextEdge;}
}

实现图的广搜：

void BFS(Graph g,int k)
{queue q;ENode *p;g->vexs[k].visited=1;q.push(k);int v,w;while(q.size()){//循环一次，访问一个节点的所有边v=q.front();q.pop();p=g->vexs[v].firstEdge;while(p!=NULL){w=p->adjVertex;if(g->vexs[w].visited==0){g->vexs[w].visited=1;q.push(w);//将边对应的节点放到队列里面}p=p->nextEdge;}}
} 

无向带权图(邻接矩阵)

在这里我们怎么实现图的深搜：

void DFS(Graph g, int i)  
{  g->visited[i] = 1;  for(int j = 0; j < g->vertexNum; j ++){if(g->edge[i][j] == 1 && g->visited[j] == 0) {DFS(g,j); }      }           
}  

在这里我们怎么实现图的广搜：

void BFS(Graph g,int i)
{queue q;q.push(i);int v;while(q.size()){i=q.front();q.pop();for(int j=0;jvertexNum;j++){if(g->edge[i][j]==1 && g->visited[j]==0){g->visited[j]=1;q.push(j);}	}                                                                                                    }
} 

深搜：

广搜：