图的相关算法

• 深度优先搜索非递归形式 DFS

Boolean visited[MAX]; //标志数组 
Status (*VisitFunction)(int v); //访问函数
 
void DFSTraverse(Graph G, Status (*Visit)(int v))
{
    VisitFunction = Visit;
    for(v = 0; v < G.vexnum; ++v) //初始化标志数组
        visited[v] = false;
    for(v = 0; v < G.vexnum; ++v) //对未访问过的顶点调用DFS
        if(!visited[v])
            DFS(G, v);
}
 
void DFS(Graph G, int v) //从顶点v出发进行DFS
{
    visited[v] = true;
    VisitFunction(v);
    for(w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
        if(!visited[w])
            DFS(G, w); //递归调用未访问的邻接顶点w
}

• 深度优先搜索非递归形式

N_DFS(gragh g, int i){
    int j;
    seqstack s;
    INITSTACK(s);
    while(!EMPTY(s)){
        if(visited[i] == 0){
            visited[i] = 1;
            printf(g.vexs[i]);
        }
        for(j = 0; j != n;++j)
            if((g.arcs[i][j] == 1) && (!visited[j])){
                PUSH(s,j);
                i = j;
                break;
            }
            else{
                POP(s);
                i = GETTOP(s);
            }
    }
}

• 广度优先搜索 BFS

void BFSTraverse(Graph G, Status (*Visit)(int v))
{
    for(v = 0; v < G.vexnum; ++v)
        visited[v] = false;   
    InitQueue(Q);
    for(v = 0; v < G.vexnum; ++v)
        if(!visited[v])
        {
            visited[v] = true;
            Visit(v);
            EnQueue(Q, v);
            while(!QueueEmpty(Q))
            {
                DeQueue(Q, u);
                for(w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w))
                    if(!visited[w])
                    {
                        visited[w] = true;
                        visit(w);
                        EnQueue(Q, w);
                    }
            }
        }
}

• 判断无向图是否是树

 int IsTree(AdjGraph *G)
{
    int vNum=0,eNum=0,i;
    for(i=0;i<G->vexnum;i++)
        visited[i]=0;
    DFS(G,0,&vNum,&eNum);
    if(vNum==G->vexnum && eNum==2*(G->vexnum-1))
        return 1;
    else
        return 0;
}
void DFS(AdjGraph *G,int v,int *vNum,int *eNum)
{
    ArcNode *p;
    visited[v]=1;
    (*vNum)++;
    p=G->vertex[v].firstarc;
    while(p!=NULL)
    {
        (*eNum)++;
        if(visited[p->adjvex]==0)
            DFS(G,p->adjvex,vNum,eNum);
        p=p->nextarc;
    }
}

• 判断有向图中两个顶点是否存在长度为K的路径

int visited[MAXSIZE]
//出发点为i，终点为j，长度为k 
int exist_path_len(ALGraph G,int i,int j,int k) 
{
    if(i==j&&k==0)
        return 1;
    else if(k>0)
    {
        visited[i]=1;
        for(p=G.vertices[i].firstarc;p;p=p->nextarc)
        {
            int temp=p->adjvex;
            if(!visited[temp]&&exist_path_len(temp,j,k-1))
                return 1; 
        } 
        visited[i]=0;
   //这里需要把已经访问的点重新置为0，因为如果当前不存在长度为k
   //到达j点，那么这个点还是可以使用的，因为有可能从其他点出口
   //可以到达j点并且长度为k 
    } 
    return 0;
}