邻接表存储结构创建图，掌握图的深度优先遍历和广度优先遍历C语言代码

邻接表存储结构创建图的C语言代码：

#include <stdio.h>
#include <stdlib.h>

#define MAXVEX 100       // 最大顶点数
#define INFINITY 65535   // 定义无穷大

typedef int ElemType;     // 顶点的数据类型

// 邻接表中表对应的链表的顶点
typedef struct EdgeNode{
    int adjvex;           // 邻接点域，存储该顶点对应的下标
    ElemType weight;      // 存储权值，对于非网图可以不需要
    struct EdgeNode *next; // 链域，指向下一个邻接点
}EdgeNode;

// 邻接表中表的顶点
typedef struct VertexNode{
    ElemType data;        // 顶点域，存储顶点信息
    EdgeNode *firstedge;  // 边表头指针
}VertexNode, AdjList[MAXVEX];

// 邻接表存储图
typedef struct{
    AdjList adjList;      // 邻接表
    int numVertexes;      // 图中当前顶点数
    int numEdges;         // 图中当前边数
}GraphAdjList;

// 创建邻接表对应的图(自己手动输入)
void CreateALGraph(GraphAdjList *G){
    int i, j, k, w;
    EdgeNode *e;
    printf("请输入顶点数和边数：\n");
    scanf("%d%d", &G->numVertexes, &G->numEdges);
    printf("请输入顶点信息：\n");
    for(i=0; i<G->numVertexes; i++){
        scanf("%d", &G->adjList[i].data);
        G->adjList[i].firstedge = NULL;
    }
    printf("请输入边的信息：\n");
    for(k=0; k<G->numEdges; k++){
        printf("输入边(vi, vj)上的顶点序号：\n");
        scanf("%d%d", &i, &j);
        printf("输入边(vi, vj)上的权值：\n");
        scanf("%d", &w);

        // 添加边表结点
        e = (EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjvex = j;
        e->weight = w;

        // 将e指针指向当前顶点指向的结点
        e->next = G->adjList[i].firstedge;
        G->adjList[i].firstedge = e;

        // 向另一个方向添加边表结点
        e = (EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjvex = i;
        e->weight = w;
        e->next = G->adjList[j].firstedge;
        G->adjList[j].firstedge = e;
    }
}

// 图的深度优先遍历
void DFS(GraphAdjList G, int i, int *visited){
    EdgeNode *p;
    visited[i] = 1;
    printf("%d ", G.adjList[i].data);
    p = G.adjList[i].firstedge;
    while(p){
        if(!visited[p->adjvex]){
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

// 邻接表的深度遍历操作
void DFSTraverse(GraphAdjList G){
    int i;
    int visited[MAXVEX] = {0};   // 初始化所有结点为未访问状态
    for(i=0; i<G.numVertexes; i++){
        if(!visited[i]){         // 对未访问过的结点进行深度优先遍历
            DFS(G, i, visited);
        }
    }
}

// 图的广度优先遍历
void BFS(GraphAdjList G, int i, int *visited){
    int j;
    EdgeNode *p;
    int queue[MAXVEX], front=0, rear=0;
    printf("%d ", G.adjList[i].data);
    visited[i] = 1;
    queue[rear++] = i;
    while(front < rear){
        j = queue[front++];
        p = G.adjList[j].firstedge;
        while(p){
            if(!visited[p->adjvex]){
                printf("%d ", G.adjList[p->adjvex].data);
                visited[p->adjvex] = 1;
                queue[rear++] = p->adjvex;
            }
            p = p->next;
        }
    }
}

// 邻接表的广度遍历操作
void BFSTraverse(GraphAdjList G){
    int i;
    int visited[MAXVEX] = {0};   // 初始化所有结点为未访问状态
    for(i=0; i<G.numVertexes; i++){
        if(!visited[i]){         // 对未访问过的结点进行广度优先遍历
            BFS(G, i, visited);
        }
    }
}

int main(){
    GraphAdjList G;
    CreateALGraph(&G);
    printf("\n深度优先遍历：");
    DFSTraverse(G);
    printf("\n广度优先遍历：");
    BFSTraverse(G);
    return 0;
}

其中，`CreateALGraph()`函数用于创建邻接表对应的图，`DFS()`函数用于实现图的深度优先遍历，`DFSTraverse()`函数用于对整个图进行深度遍历操作，`BFS()`函数用于实现图的广度优先遍历，`BFSTraverse()`函数用于对整个图进行广度遍历操作。