图的深度优先遍历:释义详见百度百科

  基本思想: 深度优先遍历图的方法是,从图中某顶点v出发:
    (1)访问顶点v;
    (2)依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;
    (3)若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止.

深度优先遍历

1.邻接表

数据结构如下:

#include <stdio.h>
#include <stdlib.h>
#define maxsize 1010   //一般顶点超过1000的建议用邻接表
typedef struct ArcNode {    //边结点
    int adjvex;        //序号
    struct ArcNode *next;
}ArcNode;
typedef struct VNode{    //顶点
    ArcNode *firstarc;
    int no;
}VNode;
typedef struct Graph {      //图
    VNode VNodeList[maxsize];
    int node;    //顶点数
    int edge;    //边数
}Graph;

建立邻接表

void createGraph(Graph *G){
    int start;
    int end;
    ArcNode *e;

    scanf("%d%d",&(G->node),&(G->edge));        //输入边数和结点数

    for(int i = 0; i < G->node; i++){//输入顶点
        scanf("%d",&(G->VNodeList[i].no));
        G->VNodeList[i].firstarc = NULL;
    }

    for(int i = 0; i < G->edge; i++){
        scanf("%d%d",&start,&end);

        //插入该点指向的边表
        e =(ArcNode*)malloc(sizeof(ArcNode));//分配空间
        e->adjvex = end;
        e->next = G->VNodeList[start].firstarc;
        G->VNodeList[start].firstarc = e;//类似于链表的前插

        //无向图才有下方
        e =(ArcNode*)malloc(sizeof(ArcNode));//分配空间
        e->adjvex = start;
        e->next = G->VNodeList[end].firstarc;
        G->VNodeList[end].firstarc = e;//类似于链表的前插
    }

}

`

递归

//邻接表递归
 int visited[maxsize] = {0};    //直接赋值
 void DFS(Graph *g, int v){
    ArcNode *arc = g->VNodeList[v].firstarc;
    visited[v]=1;
    printf("访问结点:%d\n",g->VNodeList[v].no);
    while(arc != null){        //找到未访问的点
        if(visited[arc->adjvex] == 0)
            DFS(g,arc->adjvex);
        arc = arc->next;
    }
 }

 void DFSTraverse(Graph *g){
    if(g == NULL) return;   //判空
    //memset(visited, 0, sizeof(visited));
    //或者在此之前将visited赋值完毕
    for(int i=0;i < g->node; i++){
        if(visited[i] == 0)
            DFS(g,i);
    }
 }
`

非递归

// 邻接表非递归
int visited[maxsize] = {0};
void DFSNonRecursion(Graph *g, int v){
   int stack[maxsize];        //工作栈
   int top = -1;    //栈顶指针
   int j;        //获取栈顶
   ArcNode *p;        //边结点

   //memset(visited,0,sizeof(visited));  //或在此赋值
   printf("访问结点:%d\n", g->VNodeList[v].no);   //访问结点
   visited[v] = 1;    //置已访问
   stack[++top] = v;   //入栈
   while (top != -1) {
       j = stack[top];        //栈顶访问
       p = g->VNodeList[j].firstarc;    //连接的第一个边结点
       while (p != NULL) {
           while (p != NULL && visited[p->adjvex] == 1)  //非空且已经访问
               p = p->next;
           if(p == NULL)    //如果当前已为空,则表示与当前结点邻接的所有结点访问完毕
               break;
           stack[++top] = p->adjvex;  //序号入栈
           visited[p->adjvex] = 1;
           printf("访问结点:%d\n", g->VNodeList[p->adjvex].no);      //访问且置为已访问
           p = g->VNodeList[p->adjvex].firstarc;    //找到与该结点第一个邻接的下一个顶点
       }
       --top;
   }

   return;
}

2.邻接矩阵

数据结构如下:

 #include <stdio.h>
 #define max 100
 typedef struct{
    int vertex;    //顶点数
    int edge;    //边数
    int VertexList[max];    //顶点数组
    int EdgeList[max][max];    //边数组
 }Graph

建立邻接矩阵

 //建立图的邻接矩阵
void CreateGraph(Graph *G){
    scanf("%d%d", &G->vertex,&G->edge);   //输入顶点数、边数

    for (int i=0; i < G->vertex; i++){
        scanf("%d",&(G->VertexList[i]));
    }

    for (int i=0; i < G->vertex; i++){
        for (int j=0; j<G->vertex; j++)
            G->EdgeList[i][j] = -1;        //初始化置为-1不可达
    }

    int start, end, weight;
    for (int k=0; k < G->edge; k++){    //赋值边数组
        scanf("%d%d%d", &start,&end,&weight);
        G->EdgeList[start][end] = weight;
        //如果是无向图,才有下面这一句
        G->EdgeList[end][start] = G->EdgeList[start][end];
    }

}

`

递归

int visited[max] = {0}
void DFS(Graph* G, int v){
   visited[v] = 1;            //置已访问且输出
   printf("访问结点:%d\n", G->VertexList[v]);
   for (int j=0; j < G->vertex; j++){        //如果有边,且还未访问,访问之
       if (G->EdgeList[v][j] != -1  &&  visited[j] == 0)
           DFS(G, j);
   }
}

void DFSTraverse(Graph* G){
//memset(visited,0,sizeof(visited));  //或者在这里初始化visited数组
   for (int i=0; i < G->vertex; i++){        //遍历
       if (visited[i] == 0)
           DFS(G, i);
   }
}
`

非递归

int visited[max] = {0}
void DFS(Graph* G,int v){
  //memset(visited,0,sizeof(visited));  //或者在这里初始化访问数组
  int stack[max];
  int top = -1;
  printf("访问结点:%d\n", G->VertexList[v]);    //输出结点
  visited[v] = 1     //置已访问该结点

  stack[++top] = v;     //入栈

  while(top != -1){    //栈不空
      int data = s[top];    //取栈顶
      int i;
      for(i = 0; i < G->vertex; i++){
          if(G->EdgeList[data][i] != 0 && visited[i] == 0){    //如果有边且还未访问
               printf("访问结点:%d\n", G->VertexList[i]);
               visited[i] = 1;       //输出且置为已访问
               s[++top] = i;      //入栈
               break;    //跳出
          }
      }
      if(i == G->vertex)    //data相邻的结点都访问结束了,弹出
          --top;
  }
}

参考原文

  • alipay
  • wechat