图 - 邻接表深度优先遍历(C语言)

#include <stdio.h>#include <stdlib.h># define MAX 100// 边节点typedef struct enode {    int adIndex; // 节点下标    int weight; // 权,本代码中并未用到    struct enode *next; // 下一个节点}ENODE, *PE;// 顶点typedef struct vnode {    char name;    PE firstEdge; // 单链表}VNODE, *PV, VLIST[MAX];// 图(网)typedef struct graph {   VLIST vlist;   int numVnodes, numEdges;}GRAPH, *PG;// 保存已遍历顶点int visited[MAX];void create(PG);void traverse_dfs(GRAPH);void dfs(GRAPH, int);void dfs(GRAPH graph, int i){    PE p;    // 先标识并打印顶点    printf("%c ", graph.vlist[i].name);    visited[i] = 1;    // 递归遍历与该顶点边有关的边节点    p = graph.vlist[i].firstEdge;    while (p) {        if (!visited[p->adIndex]) {            dfs(graph, p->adIndex);        }        // 犯了个错，下面这句加到上面括号中，会导致回退的时候进入死循环        p = p->next;    }}void traverse_dfs(GRAPH graph){    int i;    // 初始化所有顶点为未访问状态    for (i=0; i<graph.numVnodes; i++) {        visited[i] = 0;    }    // 开始遍历    for (i=0; i<graph.numVnodes; i++) {        if (!visited[i]) {            dfs(graph, i);        }    }   }void create(PG g){    int i, j, k;    PE e;    printf("请输入顶点数和边数:\n");    scanf("%d %d", &g->numVnodes, &g->numEdges);    getchar();    // 根据顶点数创建顶点表（VLIST一维数组）    printf("请一次性输入顶点的值: ");    for (i=0; i<g->numVnodes; i++) {        scanf("%c", &g->vlist[i].name);        g->vlist[i].firstEdge = NULL;    }    // 边节点单链表填充（创建边）    for (k=0; k<g->numEdges; k++) {        printf("请输入第%d条边(vi, vj)对应下标:\n", k+1);        scanf("%d %d", &i, &j);        // 创建i的边表节点j（双向）        e = (PE)malloc(sizeof(ENODE));        e->adIndex = j;        e->next = g->vlist[i].firstEdge; // 头插法        g->vlist[i].firstEdge = e;        // 创建j的边表节点i（双向）        e = (PE)malloc(sizeof(ENODE));        e->adIndex = i;        e->next = g->vlist[j].firstEdge;        g->vlist[j].firstEdge = e;    }    printf("create edge done.\n");}int main(void){    GRAPH graph;    create(&graph);    printf("深度优先遍历结果: ");    traverse_dfs(graph);    putchar('\n');    return 0;}

output
说明：
和上一篇中图一样，但是深度遍历的结果不一样（填充边时使用头插法导致遍历切入点不一样导致）

[root@8be225462e66 c]# gcc dfs_adList.c && ./a.out请输入顶点数和边数:8 9请一次性输入顶点的值: ABCDEFGH请输入第1条边(vi, vj)对应下标:0 1请输入第2条边(vi, vj)对应下标:1 2请输入第3条边(vi, vj)对应下标:2 5请输入第4条边(vi, vj)对应下标:1 4请输入第5条边(vi, vj)对应下标:0 4请输入第6条边(vi, vj)对应下标:0 3请输入第7条边(vi, vj)对应下标:3 6请输入第8条边(vi, vj)对应下标:6 4请输入第9条边(vi, vj)对应下标:6 7create edge done.深度优先遍历结果: A D G H E B C F[root@8be225462e66 c]#