似乎是判断一个图有没有环~
资料上有这种算法的~

大神可不可以帮忙敲下代码

那你先说说A-B-C-D-A这样四个算不算是成立的~
或者就只能是三个A-B-C-A?~

不懂啊,能帮我把题目上的样例输出来就行

这个我一时也弄不出来,思路就是在遍历图的01邻接矩阵的时候判断标记数组有没有重复遍历(这个了解遍历思路的时候就知道怎么回事了)~

话说,感觉找一个有向图的遍历代码也是不简单的事情,上去打算搜现成的发现很多拿不过来,自己之前写了一份还是邻接表的也是笑了~

这个建议看看图的邻接矩阵以及遍历原理好了~

找到我以前写过的代码~

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#define MaxVertexNum 20
#define LEN sizeof(EdgeNode) 
#define INF 999   

 //定义无穷大/****************图的邻接矩阵定义 *******************/
 

 typedef char VertexType;      //VertexType----顶点内容
 typedef int EdgeType;         //EdgeType----顶点信息
 typedef struct                //邻接矩阵
 {    VertexType vexs[MaxVertexNum];               //邻接矩阵顶点内容    
     EdgeType visit[MaxVertexNum];           EdgeType edges[MaxVertexNum][MaxVertexNum];  //邻接矩阵列表    
     int n; //n为顶点数     
     int e;//e为边数 
     }MGraph;   //定义邻接矩阵/****************图的邻接表定义 *******************/
 typedef struct node   //邻接表节点
 {    
     VertexType adjvex;      //所在的顶点
     EdgeType info;       //顶点信息    
     struct node *next;   //邻接表指针
} EdgeNode;              //定义邻接表
typedef struct vnode
{    
    VertexType vertex;      //顶点信息
    EdgeType visit;         //遍历标记
    EdgeNode* firstedge;    //第一个顶点指针
}VertexNode;

typedef struct
{    
    int n;                               //顶点数    
    int e;                               //边数
    VertexNode AdjList[MaxVertexNum];    //邻接表的保存信息
}ALGraph;                                //邻接表/****************图的创建与打印 *******************/ 
void CreateMGraph(MGraph* G)
{    
    int i=0;    
    int j=0;    
    int k=0;         printf("请输入顶点数和边数（输入格式为：顶点数，边数）：\n");    assert(scanf("%d%*c%d",&(G->n),&(G->e))==2);      /*输入顶点数和边数*/    
    getchar();    
      printf("请输入顶点信息（输入格式为：顶点号<CR>）:\n");    
      for (i=0;i<G->n;i++)           assert(scanf("%c%*c",&(G->vexs[i]))==1);                               /*输入顶点信息，建立顶点表*/    
      for (i=0;i<G->n;i++)    
      {        
          G->visit[i]=0;
          /*初始化遍历内容*/
          for (j=0;j<G->n;j++)
               G->edges[i][j]=0; 
               /*初始化邻接矩阵*/     
       }          
        printf("请输入每条边对应的两个顶点的序号（输入格式为：i,j）:\n");
     for (k=0;k<G->e;k++)
     {          
           assert(scanf("%d%*c%d",&i,&j)==2);    
           /*输入e条边，建立邻接矩阵*/                    G->edges[i][j]=1;
           /*若加入G->edges[i][j]=1*/
           /*G->edges[j][i]=1; */    
           /*则为无向图的邻接矩阵存储建立 */   }    
      getchar();
}
void printMGraph(MGraph* G)
{    
    int i=0;    
    int j=0;    
    printf("   ");    
    
    for (i=0;i<G->n;++i)
        printf("%c ",G->vexs[i]);    
        
        puts("");    
        for (i=0;i<G->n;++i)    
        {        
            printf("%c->",G->vexs[i]);
            for (j=0;j<G->n;j++)            
                printf("%d ",G->edges[i][j]);    
                
           puts("");    
        } 
}
void Creat_Node(EdgeNode** node,int size)
{    
    *node=(struct node*)malloc(LEN);
    
    assert(*node);
    
    memset(*node,0,size);
}

void MGraphtoALGraph(MGraph* mG,ALGraph* alG)   //邻接矩阵转化为邻接表
{    
    int i=0;    
    int j=0;    
    
    EdgeNode* p=NULL;    
    
    alG->e=mG->e;    
    alG->n=mG->n;    
    
    for (i=0;i<mG->n;++i)
    {        
        Creat_Node(&p,LEN);
       
        alG->AdjList[i].firstedge=p;    
        alG->AdjList[i].vertex=mG->vexs[i];            alG->AdjList[i].firstedge->info=i;                   alG->AdjList[i].visit=0; 
                             
        for (j=0;j<mG->n;++j)            
            if (mG->edges[i][j])
            {                
                 EdgeNode* new_p=NULL;    
                                     
                 Creat_Node(&new_p,LEN);
                   
                 new_p->adjvex=mG->vexs[j];      
                 new_p->info=j;
                 p=p->next=new_p;
             }    
     }
}
void printALGraph(ALGraph* alG)          //打印邻接表
{    
    EdgeNode* p=NULL;    
    int i=0;    
    
    for (i=0;i<alG->n;++i)
    {
        p=alG->AdjList[i].firstedge;
        printf("%c->",alG->AdjList[i].vertex);
        
        while (p)
        {            
            printf("%c ",p->adjvex);
            
            p=p->next;
        }        
        
        puts("");
    }
}/****************图的深度优先遍历 *******************/
void MG_DFSTraverse(MGraph* mG,EdgeType Col) 

 //矩阵的列
 {    
     int i=0;
     mG->visit[Col]=1;
     
     printf("vertex->%c\n",mG->vexs[Col]);
     
     for (i=0;i<mG->n;++i)
         if (mG->visit[i]==0&&mG->edges[Col][i]==1)
             MG_DFSTraverse(mG,i);

 }

 

 void ALG_DFSTraverse(ALGraph* alG,int i)
{
    EdgeNode* p=alG->AdjList[i].firstedge;    
        
    if (p==NULL)
        return ;    
        
    alG->AdjList[i].visit=1;
     printf("vertex->%c\n",alG->AdjList[i].vertex);    
    
    while (p=p->next)        
        if (alG->AdjList[p->info].visit==0) ALG_DFSTraverse(alG,p->info);
}

/****************图的广度优先遍历 *******************/
void MG_BFSTraverse(MGraph* mG,EdgeType n)
{    
    EdgeType queue[MaxVertexNum]={0};  //用队列来保存顶点信息    
    EdgeType count[MaxVertexNum]={0};  //步长信息    
    EdgeType step=1;   //步长    
    EdgeType front=0;   //队头指针
    EdgeType rear=0;   //队尾指针    
    
    int Row=n;         printf("步长->%-3dvertex->%c\n",step,mG->vexs[Row]);    
    
    queue[rear++]=Row;                 //第一个顶点入队    
    count[rear-1]=step;    
    mG->visit[Row]=1;                  //标记此顶点已经遍历    
    while (front!=rear)               //当队列不为空时    
    {        
        if (count[front]==step)
            ++step;
            
        for (Row=0;Row<mG->n;++Row)                    if (mG->visit[Row]==0&&mG->edges[queue[front]][Row]==1)
        {                  printf("步长->%-3dvertex->%c\n",step,mG->vexs[Row]);
            queue[rear++]=Row;
            rear%=MaxVertexNum;
            assert(front!=rear+1); //判断队满            
            count[rear-1]=step; //记录步长
            mG->visit[Row]=1;            
       
         }        
       
        ++front;
        front%=MaxVertexNum;
    }
}

void ALG_BFSTraverse(ALGraph* alG,int n)
{    
    EdgeType queue[MaxVertexNum]={0};  //用队列来保存顶点信息
    EdgeType count[MaxVertexNum]={0};  //步长信息    
    EdgeType step=1;    //步长
    EdgeType front=0;   //队头指针
    EdgeType rear=0;    //队尾指针
    EdgeNode* p=alG->AdjList[n].firstedge;
                    
     printf("步长->%-3dvertex->%c\n",step,alG->AdjList[p->adjvex]);
    queue[rear++]=p->info;
    //第一个顶点入队
    
    count[rear-1]=step;
    alG->AdjList[p->info].visit=1;        //标记此顶点已经遍历    
    while (front!=rear)
    {        
        if (count[front]==step)
            ++step;
        p=alG->AdjList[queue[front]].firstedge;
        
        while (p=p->next)
            if (alG->AdjList[p->info].visit==0)                {
                printf("步长->%-3dvertex->%c\n",step,alG->AdjList[p->info].vertex);
                queue[rear++]=p->info;  //入队
                rear%=MaxVertexNum;                assert(front!=rear+1);        //判断队满    
                
                count[rear-1]=step;//记录步长
                alG->AdjList[p->info].visit=1;                }    
        ++front;
        front%=MaxVertexNum;
    }
}

/****************************************辅助函数*************************************/

EdgeType Search(MGraph* mG,VertexType c)
{    
    int i=0;
    
    for (i=0;i<mG->n;++i)
        if (mG->vexs[i]==c)
            return i;    
            
    return -1;
}

void Empty_MG_Visit(MGraph* mG)
{    
    int i=0;
    
    for (i=0;i<mG->n;++i)
        mG->visit[i]=0;
    
}

void Empty_ALG_Visit(ALGraph* alG)
{    
    int i=0;    
    
    for (i=0;i<alG->n;++i)
        alG->AdjList[i].visit=0;
    }/****************************************main函数*************************************/ 
int main()
{
    MGraph G={0};    
    ALGraph alG={0};    
    
    int point=0;    
    
    VertexType sc=0;
    CreateMGraph(&G);    
    
    printMGraph(&G);
    MGraphtoALGraph(&G,&alG);
    
    puts("邻接表示例如下:");
    printALGraph(&alG);
    //邻接矩阵深度优先搜索
    
    puts("\n图的深度优先搜索:");
    printf("请输入查找起点搜索名称:");
    
    scanf("%c%*c",&sc);
    point=Search(&G,sc);    
    
    if (point!=-1)    
    {        
        puts("\n邻接矩阵的深度优先搜索结果:");        MG_DFSTraverse(&G,point);        puts("\n邻接表的深度优先搜索结果:");
        ALG_DFSTraverse(&alG,point);
    }    
    else        
        puts("找不到该顶点信息!"); 
        
    Empty_MG_Visit(&G);//重置搜索状态
    Empty_ALG_Visit(&alG);    
    puts("\n图的广度优先搜索:");
    printf("请输入查找起点搜索名称:");
    
    scanf("%c%*c",&sc);
    
    point=Search(&G,sc);
    
    if (point!=-1)    
    {         puts("\n邻接矩阵的广度优先搜索结果:");        MG_BFSTraverse(&G,point);        puts("\n邻接表的广度优先搜索结果:");
        ALG_BFSTraverse(&alG,point);
    }     
    else        
        puts("找不到该顶点信息!");
    
    return 0;
}

这个是邻接矩阵附带邻接表的遍历方法,在深度遍历那里标记数组简单改改还有对所有进行遍历就可以了~

具体看这个代码的实现方法就可以了~

void MG_DFSTraverse(MGraph* mG,EdgeType Col) 

 //矩阵的列
{    
     int i=0;
     mG->visit[Col]=1;
     
     printf("vertex->%c\n",mG->vexs[Col]);
     
     for (i=0;i<mG->n;++i)
         if (mG->visit[i]==0&&mG->edges[Col][i]==1)
             MG_DFSTraverse(mG,i);

 }

 

然后改了一下~

void MG_DFSTraverse(MGraph* mG,EdgeType Col) 

 //矩阵的列
{    
     int i=0;
     mG->visit[Col]=1;
     
     printf("vertex->%c\n",mG->vexs[Col]);
     
     for (i=0;i<mG->n;++i)
         if (mG->visit[i]==0&&mG->edges[Col][i]==1)
             MG_DFSTraverse(mG,i);
        else if (mG->visit[i]==1&&mG->edges[Col][i]==1)
             puts("这个图存在环!");

 }

 

补充一下拓补排序也可以判断,那个可以去看看资料,其实单纯判断有没有环还是这种写法简单~

[此贴子已经被作者于2018-3-19 01:00编辑过]