本文主要讨论无向图AB两点是否连通的算法。
分别有邻接表和邻接矩阵存储两个版本。
主要函数列表如下：
int IsConnected(AGraph *G,int A,int B)
int IsConnected(MGraph M,int A,int B)

//If this code works ,it is written by Dannyboy
//compiler:Microsoft VC++

#include <stdio.h>
#define N 7
#define STACKLEN 100

int A[7][7]={
{0,1,0,0,0,0,0},//0
{1,0,1,1,0,0,0},//1
{0,1,0,0,0,0,0},//2
{0,1,0,0,1,1,0},//3
{0,0,0,1,0,1,1},//4
{0,0,0,1,1,0,0},//5
{0,0,0,0,1,0,0} //6
};


typedef struct ArcCell
{
    int adj;
    char * info;
}ArcCell;

typedef struct
{
    int vexnum;
    int arcnum;
    ArcCell arcs[N][N];
}MGraph;



typedef struct ArcNode
{
    int adjVex;
    int weight;
    ArcNode *nextarc;
    char *info;
}ArcNode;
typedef struct VNode
{
int data;
ArcNode *firstarc;
}VNode,adjList[N];

typedef struct
{
    adjList vertices;
    int vexnum;
    int arcnum;
}AGraph;



void CreateMGraph(MGraph& M)
{

    int i,j;
    int count=0;
    for(i=0;i<N;i++)
    for(j=0;j<N;j++)
    {
        M.arcs[i][j].adj=A[i][j];
        if(M.arcs[i][j].adj!=0)count++;

    }
    M.vexnum=N;
    M.arcnum=count/2;
}

void CreateAdjFromMat(AGraph *G,MGraph A)
{

    int i,j;
    G->vexnum=A.vexnum;
    G->arcnum=A.arcnum;
    for(i=0;i<A.vexnum;i++)
    {
        G->vertices[i].firstarc=NULL;
        for(j=0;j<A.vexnum;j++)
        {
            if(A.arcs[i][j].adj!=0)
            {
                ArcNode *p;
                p=new ArcNode;
                p->adjVex=j;
                p->info=0;
                p->nextarc=G->vertices[i].firstarc;
                G->vertices[i].firstarc=p;
            }

        }


    }


}
int IsConnected(AGraph *G,int A,int B)
{


typedef struct node
{
    int begin,end;
    int level;
}node;

int i,j;
int connected[N];int visited[N];
for(i=0;i<N;i++)
{connected[i]=0;visited[i]=0;}

int Stack[STACKLEN];
int top=-1;

ArcNode *p;
p=G->vertices[A].firstarc;

while(p!=NULL)
{
    connected[p->adjVex]=1;
    top++;
    Stack[top]=p->adjVex;
    p=p->nextarc;
}

while(top>=0)
{
int out=Stack[top];
top--;
visited[out]=1;

ArcNode *p;
p=G->vertices[out].firstarc;

while(p!=NULL)
{
    if(visited[p->adjVex]==0)
    {
        if(connected[out]==1){connected[p->adjVex]=1;}
        Stack[++top]=p->adjVex;
    }
    p=p->nextarc;

}
}


return connected[B];

}
int IsConnected(MGraph M,int A,int B) //判断任意两点之间是否连通
{


    
        int i,j,k;
        int ans[N][N];
        for(i=0;i<N;i++)
        for(j=0;j<N;j++)
        {
            ans[i][j]=M.arcs[i][j].adj;
        }


        for(j=0;j<N;j++)
        for(i=0;i<N;i++)
        for(k=0;k<N;k++)
        if(ans[i][k]&&ans[k][j])ans[i][j]=1;

//for(i=0;i<N;i++)
//{printf("%d",ans[A][i]);}
       

        return ans[A][B];

}



int main()
{

    MGraph M;
    AGraph *G;
    G=new AGraph;

    CreateMGraph(M);//创建邻接矩阵M
    CreateAdjFromMat(G,M);//创建邻接表G

    //判段 0点 与 6点 是否连通
    printf("%d",IsConnected(G,0,6));
//    printf("%d",IsConnected(M,0,6));

    //让系统输入一个整数后退出
    int stop;
    scanf("%d",&stop);
    return 0;
}