bool visited[MAX_VERTEX_NUM];//访问标记数组
//广度优先遍历
void BFS(Graph G,int v){//从顶点v出发，广度优先遍历图G
	visit(v);			//访问初始顶点v
    visited[v]=TRUE;	//对v做已访问标记
    Enqueue(Q,v);		//顶点v入队列Q
    while(!isEmpty(Q)){
        DeQueue(Q,v);	//顶点v出队列
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
            //检测v所有邻接点
            if(!visited[w]){	//w为v的尚未访问的邻接顶点
                visit(w);		//访问顶点w
                visited[w]=TRUE;//对w做已访问标记
                EnQueue(Q,w);	//顶点w入队列
            }
    }
}

//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G,int v){//从顶点v出发，广度优先遍历图G
	//d[i]表示从v到i结点的最短路径
    for(i=0;i<G.vexnum;++i){
        d[i]=∞; //初始化路径长度
        path[i]=-1;//最短路径从哪个顶点过来
    }
    d[u]=0;
    visited[v]=TRUE;	//对v做已访问标记
    Enqueue(Q,v);		//顶点v入队列Q
    while(!isEmpty(Q)){
        DeQueue(Q,v);	//顶点v出队列
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
            //检测v所有邻接点
            if(!visited[w]){	//w为v的尚未访问的邻接顶点
                d[w]=d[v]+1；	//路径长度加1
                path[w]=u;		//最短路径应从v到w
                visited[w]=TRUE;//对w做已访问标记
                EnQueue(Q,w);	//顶点w入队列
            }
    }
}

//....准备工作，根据图的信息初始化矩阵A和path
for(int k=0;k<n;k++){		//考虑以Vk作为中转点
	for(int i=0;i<n;i++){	//遍历整个矩阵，i为行号，j为列号
        for(int j=0;j<n;j++){
            if(A[i][j]>A[i][k]+A[k][j]){//以Vk为中转点的路径更短
                A[i][j]=A[i][k]+A[k][j];//更新最短路径长度
                path[i][j]=k;			//中转点
            }、
        }
    }
}

#define MaxVertexNum 100 //图中顶点数目的最大值
typedef struct ArcNode{  //边表结点
	int adjvex;		//该弧所指向的顶点的位置
    struct ArcNode *nextarc;	//指向下一条弧的指针
}ArcNode;
typedef struct VNode{	//顶点表结点
	VertexType data;	//顶点信息
    ArcNode *firstarc;	//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct{
    AdjList vertices;	//邻接表
    int vexnum,arcnum;	//图的顶点数和弧数
}Graph;		//Graph是以邻接表存储的图类型
bool TopologicalSort(Graph G){
	InitStack(S);	//初始化栈，存储入度为0的顶点
    for(int i=0;i<G.vexnum;i++)
        if(indegree[i]==0)
            Push(S,i);	//将所有入度为0的顶点进栈
    int count=0;		//计数，记录当前已经输出的顶点数
    while(!isEmpty(S)){	//栈不空，则存在入度为0的顶点
        Pop(S,i);	//栈顶元素出栈
        print[count++]=i;	//输出顶点i
        for(p=G.vertices[i].firstarc;p;p=p->nextarc){
        	//将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈s
            v=p->adjvex;
            if(!(--indegree[v]))
                Push(S,v);	//入度为0，则入栈
        }
    }
    if(count<G.vexnum)
        return false;	//排序失败，有向图中有回路
    else 
        return true;	//拓扑排序成功
}

void DFSTraverse(Graph G){	//对图G进行深度优先遍历
	for(v=0;v<G.vexnum;++v)	
        visited[v]=FALSE;	//初始化已访问标记数据
    for(v=0;v<G.vexnum;++v)	//本代码中是从v=0开始遍历
        if(!visited[v])
            DFS(G,v);
}
void DFS(Graph G,int v){//从顶点v出发，深度优先遍历图G
	visited[v]=TRUE;	//设已访问标记
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighor(G,v,w))
        if(!visited[w]){	//w为u的尚未访问的邻接顶点
        DFS(G,w);
        }
    print(v);//输出顶点
}