图---DFS

目录：

• • 实现方法：
  • 定义结构体：
  • 初始化图：
  • 创建图：
  • DFS遍历：
  • 测试：
  • 输出结果：
  • 结果分析：

实现方法：

Graph *initgraph(int vexNum);//初始化图void creat_graph(Graph *graph,char *vexs,int *arcs);//创建图//void creat_graph(Graph *graph,char *vexs,int (*arcs)[5]);//创建图void DFS(Graph *graph,int *flag,int index);//DFS遍历

定义结构体：

#include #include typedef struct Graph{    char *vexs;     //  顶点元素    int **arcs;     //  邻接表    int vexNum;     //  顶点数量    int arcsNum;    //  边数量}Graph;

初始化图：

Graph *initgraph(int vexNum){    Graph *graph = (Graph *)malloc(sizeof(Graph));    graph->vexs = (char *)malloc(sizeof(char) * vexNum);    //为顶点元素申请内存空间    graph->arcs = (int **)malloc(sizeof(int *) * vexNum);   //指针数组(存储一维数组首地址)    for(int i = 0;i < vexNum;i++)    { graph->arcs[i] = (int *)malloc(sizeof(int) * vexNum);   //为一维数组申请内存空间    } graph->vexNum = vexNum;     //初始化顶点数量    graph->arcsNum = 0;  //初始化边数量    return graph;}

创建图：

void creat_graph(Graph *graph,char *vexs,int *arcs){    for(int i = 0;i < graph->vexNum;i++)    { graph->vexs[i] = vexs[i];//为顶点赋值 for(int j = 0; j < graph->vexNum;j++) {     graph->arcs[i][j] = *(arcs + i * graph->vexNum + j) ;      //创建邻接表     if(graph->arcs[i][j] != 0)    //二维数组不等于0是存在边，边数加 1  graph->arcsNum ++; }    }    for(int i = 0;i < graph->vexNum;i++)    {  for(int j = 0; j < graph->vexNum;j++) {     printf("%d\t",graph->arcs[i][j]); } printf("\n");    } printf("\n");    graph->arcsNum /= 2;    //无向图两顶点之间是没有方向的，}

DFS遍历：

void DFS(Graph *graph,int *flag,int index){    //打印结点内容    printf("%c\t",graph->vexs[index]);    //标记已访问    flag[index] = 1;    //遍历二维数组    for(int i = 0;i < graph->vexNum;i++)    {   //如果未访问过且存在边的关系则访问结点 if(graph->arcs[index][i] == 1 && !flag[i]) {     DFS(graph,flag,i); }    }}

测试：

#include "graph.h"void main(){    Graph *graph = initgraph(5);    int *flag = (int *)malloc(sizeof(int) * graph->vexNum);    for(int i = 0;i < graph->vexNum;i++)    { flag[i] = 0;    }    int arcs[5][5] = { 0,1,1,1,0, 1,0,1,1,1, 1,1,0,0,0, 1,1,0,0,1, 0,1,0,1,0    };    creat_graph(graph,"ABCDE",(int *)arcs);    printf("DFS遍历结果：\n");    DFS(graph,flag,0);    printf("\n"); system("pause");    return ;}

输出结果：

结果分析：

声明：此文章为学习笔记，如有侵权请联系删除。