数据结构图之定义与遍历

我是自动化专业的应届研究生，最终拿到了tplink、华为、vivo等公司的ssp的offer，分享自己学习过的计算机基础知识（C语言+操作系统+计算机网络+linux）以及数据结构与算法的相关知识，保证看完让你有所成长。
欢迎关注我，学习资料免费分享给你哦！还有其余超多学习资源，都是我自己学习过的，经过过滤之后的资源，免去你还在由于拥有大量资源不知如何入手的纠结，让你体系化学习。

qrcode_for_gh_2244ed2f89ba_258.jpg

图的概念

图就是有少量顶点，顶点之间有少量边，这样就构成了一个图。所以对于图这种数据结构，关键点就是顶点和边，就是形容顶点和边的关系。而后对于边呢，对于某些问题来说，还可能有权重，以城市之间的航班为例，各个城市就是顶点，航线就是边，不同的航线票价不同，这个票价就是权重，所以根据边有无权重，分为有权图和无权图。根据边能否是单方向，就是顶点A和B之间有一条边，假如只能沿着这条边单方向的从A到B或者者从B到A，而不是既可以从A到B也可以从B到A的，这种图就是有向图。

无向图：

在这里插入图片形容

有向图：

在这里插入图片形容

有权图：

在这里插入图片形容

在一个无向图中，假如任意的两个顶点，都可以找到一个路径，让他俩连通，那么这个图就是连通图。否则就不是。

连通图：任意两个节点之间都可以找到通路

在这里插入图片形容

非连通图：ABCD任意一个顶点都不能找到到达E和F的通路。但是ABCD是一个连通图。

在这里插入图片形容

图的邻接矩阵的实现

所谓邻接矩阵就是用二维矩阵（就是二维数组）来表示顶点之间的关系。二维矩阵是一个方阵，大小就是顶点数*顶点数，假如顶点i和顶点j之间有一条边，假如是无向图则，G[i][j]=1,G[j][i]=1。假如是有向图，假设只是从i指向j那么G[i][j]=1。对于有权图，那么这个矩阵的值就是权值，而后两个顶点之间没有边，可以让G[i][j]等于一个权值永远不会相等的数来表示没有边。

代码如下

typedef struct EdgeNode //边的定义，方便为图插入边，假如是有权图，增加一个权重变量就可{    int begin;     int end;}* Edge;#define MAX_NV 11 //定义图的最大顶点数目，当然也可以使用动态数组生成一个二维数组typedef struct Graph //假如是有权图，增加一个权重变量就可{    int Nv;//顶点数    int Ne;//边数    int G[11][11];//边的关系，两个顶点i和j之间有边，则置1}* Graph;Graph creatGraph(int Nv,int Ne)//输入顶点数和边数，创立一个图，返回图的指针。{    Graph graph;    int i,j;    graph=(Graph)malloc(sizeof(struct Graph));    if(graph==NULL)    {        printf("内存不足\n");        return NULL;    }    graph->Ne=Ne;    graph->Nv=Nv;    for(i=0;i<graph->Nv;i++)//一律初始化为没有边    {        for(j=0;j<graph->Nv;j++)        {            graph->G[i][j]=0;        }    }    return graph;}void insert(Graph graph,Edge e)//插入边，这里是无权图，无向图{    if(graph==NULL||e==NULL)    {        return;    }    graph->G[e->begin][e->end]=1;    graph->G[e->end][e->begin]=1;}void destroy(Graph graph)//释放图的内存{    free(graph);}

图的邻接表实现

前面的邻接矩阵对于顶点很多，边特别少的情况（被叫做稀疏矩阵），矩阵中的很多元素都是0，是一种巨大的白费。图的邻接表表示法，其实说究竟就是一个散列而已，定义了一个头部，头部中包含图中一共有多少顶点和边，还有一个元素是指向各个顶点头部，用来指示顶点之间的边的关系。

在这里插入图片形容

与代码对应一下：

typedef struct Gnode{    int end;    struct Gnode* next;}* Gnode;typedef struct Graph{    int Nv;//顶点数    int Ne;//边数    struct Gnode G[20];}* Graph;

struct Graph就是散列的管理结构，struct Gnode G[20];就是散列表的头部，struct Gnode就是节点。

而后图中的顶点与边的对应关系是这样的：G[i]就是表示第i顶点，而后向后遍历这个链表，每个节点struct Gnode结构中都有end元素，它表示的就是第end顶点，就是i到end顶点之间存在一个边。

在这里插入图片形容

假设有上图所示的一个无向图，那么表示一个图的邻接表就是：

在这里插入图片形容

图中的方框表示的就是struct Gnode节点。比方0与1和3之间有边，那么对于图的管理结构G[0]这个链表就是表示的顶点0的边，上图可以看到这个链表是1，3.也就是表示0与1，0与3之间有边。就这样即可以表示出来了一个图的顶点与边的关系。

代码实现：

Graph creatGraph(int Nv,int Ne){    Graph graph;    int i;    graph=(Graph)malloc(sizeof(struct Graph));    if(graph==NULL)    {        printf("内存不足");        return NULL;    }    graph->Ne=Ne;    graph->Nv=Nv;    for(i=0;i<Nv;i++)    {        graph->G[i].next=NULL;    }    return graph;}void insert(Graph graph,int begin,int end)//无向图i与j有边//那么在G[i]的链表里插入边，也得在G[j]的链表里插入边，假如是有向边即可以只插入一个边了。{    Gnode g;    g=(Gnode)malloc(sizeof(struct Gnode));    if(g==NULL)    {        return;    }    g->next=graph->G[begin].next;    graph->G[begin].next=g;    g->end=end;    g=(Gnode)malloc(sizeof(struct Gnode));    if(g==NULL)    {        return;    }    g->next=graph->G[end].next;    graph->G[end].next=g;    g->end=begin;}void destroyGraph(Graph graph) //释放图的空间{    int i;    Gnode g;    if(graph==NULL)    {        return;    }    else    {        for(i=0;i<graph->Nv;i++)        {            while(graph->G[i].next!=NULL)            {                g=graph->G[i].next;                graph->G[i].next=g->next;                free(g);            }        }    }    free(graph);}

图的深度优先遍历

图的深度优先遍历，就是从一个顶点A开始出发，而后找到一个与A有边的顶点B，将A标记为已经访问，而后去访问B，将B标记为访问完成，而后找到一个与B有边的顶点C，在去访问C，而后标记已经访问完成。之后发现C已经没有可以访问的顶点了，那么就回退到B，继续找与B相连，且没有访问的顶点，最后回退到A，在寻觅，最后直到找不到合适的顶点，结束遍历。

在这里插入图片形容

举个例子来说，如上图所示的一个图，首先从0开始遍历。将0标记为已经访问，而后找到与它相连的顶点1.

在这里插入图片形容

而后将1标记为已经访问，找到与它相连的2，

在这里插入图片形容

在2处，把2标记为已经访问，而后继续搜寻，发现与它相连的1已经被访问了，所以继续寻觅，找到了3

在这里插入图片形容

在3点，标记为已访问，而后发现与之相连的顶点0，1，2都访问了，只剩下4了，所以去顶点4.

在这里插入图片形容

到达4点的时候，标记为已经访问，而后发现与之相连的3点访问过了。没有其余的边了，那么就回退到刚才访问4顶点之前的3顶点，看看还有没有与之相连的顶点没有访问，发现3也没有了，那就在回退到访问3之前的节点2，发现2有节点5没有访问，而后访问，与4一样，没有其余顶点可以访问，那么就回退到2，此时2的顶点也都被访问过了，在回退到访问2之前的1，最后回退到0，发现都没有空余节点访问了，所以完成了深度优先遍历。这个过程是不是与之前学过的一种数据结构很像，先进后出，没错就是栈，函数实现栈，就是递归，所以图的深度优先遍历，就是不断递归的过程。

代码如下：

void DFS(Graph graph,int *visit,int k)//从k顶点开始遍历，visit为访问标记，访问//过了就置1{    int i;    visit[k]=1;    printf(" %d",k);    for(i=0;i<graph->Nv;i++)    {        if(visit[i]==0&&graph->G[k][i]==1)        {            DFS(graph,visit,i);        }    }}

图的广度优先遍历

图的广度优先遍历就比较简单了，其实就是二叉树的层次遍历的思想，需要使用队列这个数据结构，基本思路是这样的：首先将第一个顶点入队，标记为已经访问（切记肯定是入队就标记已经访问，不可以出队在标记访问，否则会造成顶点的重复入队）而后开始遍历，循环结束的条件是队列为空，将队列首个元素弹出，而后判断与它相连的顶点能否被访问过，没有，则入队，并且标记已经访问。重复这个过程，就完成了遍历。

代码如下：

void BFS(Graph graph,int *visit,int k){    int i,j;    queue q;    q=createQueue();    if(q==NULL)    {        return;    }    printf("{");    add_que(q,k);    visit[k]=1;    while(!isEmpty(q))    {        i=pop_que(q);        printf(" %d",i);        for(j=0;j<graph->Nv;j++)        {            if(visit[j]==0&&graph->G[i][j]==1)            {                add_que(q,j);                visit[j]=1;            }        }    }    printf(" }\n");    destroyQueue(q);}

图的练习题

对于图的基础定义和图的遍历，大家可以通过下面这道题练习一下：
列出连通集

补充

补充：广度优先遍历中使用队列的实现代码如下：

typedef int Element;typedef struct Qnode{  Element data[50];  int rear;  int front;};#define True 1#define False 0typedef struct Qnode* queue;queue createQueue();int isFull(queue que);int isEmpty(queue que);void add_que(queue que,Element BT);Element pop_que(queue que);void destroyQueue(queue que);

queue createQueue(){  queue que;  que=(queue)malloc(sizeof(struct Qnode));  if(que==NULL)  {    printf("空间不足");    return NULL;  }  que->rear=0;  que->front=0;  return que;}int isFull(queue que){  return ((que->rear+1)%50)==(que->front);}int isEmpty(queue que){  return ((que->rear==que->front));}void add_que(queue que,Element BT){  if(isFull(que)==True)  {    printf("队列满\n");    return;  }  que->rear=(que->rear+1)%50;  que->data[que->rear]=BT;}Element pop_que(queue que){  if(isEmpty(que)==True)  {    printf("队列空\n");    return -1;  }//注意这个出队，是先front指向的位置加1  que->front=(que->front+1)%50;  return que->data[que->front];}void destroyQueue(queue que){  free(que);}