收集的C语言算法程序

图的深度优先搜索
第一个是邻接表的。

#include<stdio.h>
#define max 12
typedef struct enode{
        int b;
        struct enode *next;
}Edgenode;       //边表 
typedef struct vnode{
        char c;
        Edgenode *first;
}Vertexnode;    //顶点表 
typedef struct graph{
        Vertexnode v[max];
        int n,e;
}Graph;   //图结构 
int visited[max]; //访问标记数组 
void creat(Graph *g) //初始化图 
{
     int i,m,n;
     Edgenode *p; 
     printf("Please input VertexNode:\n");
     for(i=0;i<g->n;i++)
           {
           scanf("\n%c",&g->v[i].c);
           g->v[i].first=NULL;
           }
     for(i=0;i<g->e;i++)
           {
           printf("Please input Edge(like 0,1):\n");
           scanf("\n%d,%d",&m,&n);
           p=(Edgenode *)malloc(sizeof(Edgenode));
           p->b=n;
           p->next=g->v[m].first;
           g->v[m].first=p;
           
           p=(Edgenode *)malloc(sizeof(Edgenode));
           p->b=m;
           p->next=g->v[n].first;
           g->v[n].first=p;           
           }
}

void dsearch(Graph *g,int i) //从边表开始递归搜索 
{
     Edgenode *p;
     printf("%c ",g->v[i].c); //访问 
     visited[i]=1;
     p=g->v[i].first;
     while(p)              //当有边表节点时 
     {       if(visited[p->b]!=1)   //如果边表内的下标处的顶点未被访问 
                  dsearch(g,p->b); //递归搜索 
             p=p->next;            //否则查找边表的下一个节点 
     }
}
     
void dfs(Graph *g)
{
     int i;
     for(i=0;i<g->n;i++)
          visited[i]=0;
     for(i=0;i<g->n;i++)          //从标记数组一个一个查起 
           if(visited[i]==0)
                  dsearch(g,i);
        
}           
int main()
{
    Graph *g;
    g=(Graph *)malloc(sizeof(Graph));
    g->n=4;g->e=5; //表的顶点个数和边的个数 
    creat(g);
    dfs(g);
    system("pause");
}


第二个是邻接矩阵的。

#include<stdio.h>
#define max 20
typedef struct graph{
        char v[max];
        int edge[max][max];
        int n,e;
}Graph;
int visited[max];
void creatg(Graph *g)
{
int i,j,m,n,w=1;
g->n=8;g->e=9;
printf("Please input Vertex:\n");
for(i=0;i<g->n;i++)
        scanf("\n%c",&g->v[i]);
printf("Please input Edge:\n");
for(i=0;i<g->n;i++)
     for(j=0;j<g->n;j++)
          g->edge[i][j]=0;
for(i=0;i<g->e;i++)
          {
          scanf("\n%d,%d",&m,&n);
          g->edge[m][n]=w;
          g->edge[n][m]=w;
          }
}

void search(Graph *g,int i)
{    
     int j;
     printf("%c ",g->v[i]);
     visited[i]=1;
     for(j=0;j<g->n;j++)
          if(g->edge[i][j]==1 && visited[j]!=1) //若邻接点存在且未被访问过 
          //为什么不是visited[g->edge[i][j]],这是和邻接表不一样的。
          //邻接矩阵只用了下标，矩阵里面存的是权 
                   search(g,j);
}

void dfs(Graph *g)
{
     int i,j;
     for(i=0;i<g->n;i++)
         visited[i]=0;
     for(i=0;i<g->n;i++)
         if(visited[i]!=1)
               search(g,i); 
}

int main()
{
Graph *g;
g=(Graph *)malloc(sizeof(Graph));
creatg(g);
dfs(g);
system("pause");
}