DFS算法源程序

/* dfs算法 */
#include<alloc.h>
#include<stdio.h>
#include<malloc.h>
#include<conio.h>

/* 函数结果状态代码 */
#define   True     1
#define   False     0
#define   Ok       1
#define   Error     0
#define   Infeasible -1
#define   Overflow   -2
#define   Null     0
#define STACK_INIT_SIZE 100
#define Stackincrement 10

#define INFINITY 10000 /* 最大值10000 */
#define MAX_VERTEX_NUM 20 /* 最大顶点个数 */
#define Status int
typedef char TElemType; /* 抽象元素类型为char类型 */

typedef struct ArcNode{
  int adjvex; /* 该弧所指向的顶点的位置 */
  int weight; /* 边的权值 */
  struct ArcNode *nextarc; /* 指向下一条弧的指针 */
}ArcNode;

typedef struct VNode{
  char data; /* 顶点向量 */
  ArcNode *firstarc; /* 指向第一条依附该顶点的弧的指针 */
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct {
  AdjList vertices;
  int vexnum,arcnum; /* 图的当前顶点数和弧数 */
}ALGraph;

struct STU{
char data;
};
typedef struct STU SElemType;

struct STACK
{
SElemType *base;
SElemType *top;
int stacksize;
};

typedef struct STACK SqStack;
int visited[MAX_VERTEX_NUM]; /* visited[MAX_VERTEX_NUM]为全局变量，记录相应顶点是否被访问过，访问过则为1，否则为0 */

Status InitStack(SqStack *S)
  /* 构造一个空栈 */
{
S->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemTy pe));
if(!S->base)
  exit(Overflow); /* 存储分配失败 */
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return Ok;
} /* InitStack() */


Status StackEmpty(SqStack *S)
/* 判断栈S是否为空 */
{
if(S->top==S->base) return True;
else
  return False;
} /* StackEmpty() */



Status GetTop(SqStack *S,SElemType **e)
/* 若栈不空，则用e返回S的栈顶元素，并返回Ok，否则返回Error */
{
if(S->top==S->base)
  return Error;
else
  {
    *e=S->top-1;
    return Ok;
  } /* else */
} /* GetTop() */



Status Push(SqStack *S,char e)
/* 插入元素e为新的栈顶元素 */
{
if(S->top-S->base>=S->stacksize) /* 栈满，追加存储空间 */
  {
    S->base=(SElemType*)realloc(S->base,(S->stacksize+S tackincrement)*sizeof(SElemType));
    if(!S->base)exit(Overflow);
    S->top=S->base+S->stacksize;
    S->stacksize+=Stackincrement;
  } /* if */
S->top->data=e;
++S->top;
} /* Push() */




Status Pop(SqStack *S,SElemType **e)
/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回Ok；否则返回Error */
{
if(S->top==S->base)
  return Error;
else
  {
    (*e)->data=(S->top-1)->data;
    –S->top;
  } /* else */
return Ok;
} /* Pop() */



void CreateGraph(ALGraph *G)
/* 生成G的存储结构-邻接表 */
{
int w,i,j,k;
char sv,tv;
ArcNode *pi,*pj;

printf(“Please input the number of the vertex and arc:\n”);
printf(“vertex:”); /* 输入顶点数 */
scanf(“%d”,&G->vexnum);
printf(“arc:”); /* 输入弧数 */
scanf(“%d”,&G->arcnum);
printf(“Please input the vertex:”);
getchar();

for(i=0;i<G->vexnum;i++) /* 构造顶点数组 */
  {
    scanf(“%c”,&G->vertices.data); /* 输入顶点 */
    G->vertices.firstarc=Null; /* 初始化链表头指针为空 */
  }

getchar();
for(k=0;k<G->arcnum;k++) /* 输入各边并构造邻接表 */
  {
    pi=(ArcNode*)malloc(sizeof(ArcNode));
    if(!pi)
    exit(Overflow); /* 分配存储失败 */
    printf(“Please input two points of one arc and it’s weight:”);
    scanf(“%c%c%d”,&sv,&tv,&w); /* 输入一条弧的始点和终点及其权值 */

    getchar();
    pi->weight=w;
    i=LocateVex(G,sv); /* 确定sv和tv在G中位置，即顶点在G->vertices中的序号 */
    j=LocateVex(G,tv);
    pi->adjvex=j; /* 对弧结点赋邻接点位置 */
    pi->nextarc=G->vertices.firstarc;
    G->vertices.firstarc=pi; /* 插入链表G->vertices */

    pj=(ArcNode*)malloc(sizeof(ArcNode));
    if(!pj)
    exit(Overflow); /* 分配存储失败 */
    pj->adjvex=i; /* 对弧结点赋邻接点位置 */
    pj->weight=w;
    pj->nextarc=G->vertices[j].firstarc;
    G->vertices[j].firstarc=pj; /* 插入链表G->vertices[j] */
  } /* for */
} /* CreateGraph() */



Status STraverse_Nonrecursive(ALGraph *G,int(*Visit)(TElemType))
/* 非递归遍历图G,图G采用邻接表存储方式 */
{
int record=1,i,j,k; /* record记录已经打印的顶点数目 */
SElemType *e;
SqStack *s;

s=(SqStack*)malloc(sizeof(SqStack));
if(!s)
  exit(Overflow); /* 存储分配失败 */
InitStack(s);
Push(s,G->vertices[0].data); /* 将第一个顶点入栈 */
Visit(G->vertices[0].data); /* 访问第一个顶点 */
for(i=1;i<G->vexnum;i++)
  visited=0; /* 对visited初始化为0 */
visited[0]=1; /* 第一个顶点已访问过 */  

while(record<G->vexnum) /* 循环执行直到record=G->vexnum */
  {
    if(!StackEmpty(s))
    {
      while(GetTop(s,&e)&&e)
        {
        j=FirstAdjVex(G,*e);
        while(j==-1&&!StackEmpty(s)&&GetTop(s,&e )&&e)
          {
            j=FirstAdjVex(G,*e);
            Pop(s,&e);
          }
        if(j!=-1&&!visited[j])
          {
            Visit(G->vertices[j].data);
            visited[j]=1;
            record++;
            Push(s,G->vertices[j].data); /* 向左走到尽头 */
            if(record==G->vexnum) /* 如果所有顶点都已被访问过， 则退出 */
            return 1;
          } /* if */
        } /* while */
      if(!StackEmpty(s))
        {
        Pop(s,&e);
        GetTop(s,&e);
        k=FirstAdjVex(G,*e); /* 向右走一步 */
        if(k!=-1&&!visited[k])
          {
            Visit(G->vertices[k].data);
            visited[k]=1;
            Push(s,G->vertices[k].data);
            record++;
            if(record==G->vexnum) /* 如果所有顶点都已被访问过， 则退出 */
            return 1;
          } /* if */
        }
    } /* if */
  } /* while */
} /* STraverse_Nonrecursive() */


Status FirstAdjVex(ALGraph *G,char v)
/* 图G存在，v是G中的某个顶点,返回v的第一个未被访问的邻接顶点的序号，若顶点再G中没有邻接顶点，则返回-1 */
{
ArcNode *p;
int i;
for(i=0;i<G->vexnum;i++) /* 寻找v所在的邻接表中的序号 */
  {
    if(v==G->vertices.data)
    break;
  } /* for */
p=G->vertices.firstarc;   /* p指向v的第一个邻接点 */
while(p)
  {
    if(visited[p->adjvex]) /* 如果此邻接点已被访问则p指向v的下一个邻接点 */
    p=p->nextarc;
    else
    return p->adjvex;
  } /* while */
return -1;
} /* FirstAdjVex() */



Status LocateVex(ALGraph *G,char vex)
/* 确定vex在G中的位置 */
{
int i;
for(i=0;i<G->vexnum;i++) /* 确定v1在G中位置 */
  if(vex==G->vertices.data)
    return i;
} /* LocateVex() */


int PrintGraph(TElemType e)
/* 输出图中的每一个结点 */
{
printf(“%c “,e);
return Ok;
}


main()
{
ALGraph *G;
int i;

G=(ALGraph*)malloc(sizeof(ALGraph));
CreateGraph(G);
STraverse_Nonrecursive(G,PrintGraph);
}