数据结构之图(c语言版)

图是比树更复杂的结构，树是一对多的关系，图是多对多的关系。

一、基本概念

1、定义：图(graph)是由一些点(vertex)和这些点之间的连线(edge)所组成的；其中，点通常被成为"顶点(vertex)"，而点与点之间的连线则被成为"边或弧"(edege)。通常记为，G=(V,E)。

2、根据边是否有方向，将图可以划分为：无向图和有向图。

3、度，在无向图中，某个顶点的度是邻接到该顶点的边(或弧)的数目。

在有向图中，度还有"入度"和"出度"之分。
某个顶点的入度，是指以该顶点为终点的边的数目。而顶点的出度，则是指以该顶点为起点的边的数目。
顶点的度=入度+出度。

4、弧头和弧尾

有向图中：用<A,B>,<B,C>,<B,F>，A->B,A是弧尾，B是 弧头。

无向图中：用(A,B),(A,C),(B,C)，弧头和弧尾没有区别。

5、权

弧如果有值的话，称为权。

二、图的存储结构

图的存储结构有许多种，有邻接矩阵，邻接表，十字链表等。

邻接矩阵

用矩阵表示，用线性表存储数据，直观简单，但是浪费空间。

邻接表

用数组和链表表示结构，节省空间，可伸缩。
数组中存储了链表，链表的头节点代表定点，存储着数据及下一个顶点的引用，后面的节点存储着下标和下一个顶点的引用。

图来自《大话数据结构》

三、图的建立（邻接表）

由上可知，邻接表由数组和链表构成。首先一个结构体数组存储着数据和指向下一个顶点的指针，数组下标代表着顶点的序号。

所有数据都放在顶部方便修改，用结构体数组存储着边和顶点。

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


#define MAXVEX 10 //最大顶点数

static int VexNum=5;//当前顶点数
static int edgeNum=6;//当前边数

typedef struct edgeNode{//边表节点
    int index;//下标
   // EdgeType weight;//权值
    struct edgeNode *next;//指向下一个边表
}EdgeNode;

typedef struct vexNode{//顶点表节点
    int data;       //顶点数据A
    EdgeNode *firstEdge;//指向第一个边表
}VexNode,VexList[MAXVEX];

typedef struct  graphList{//邻接表
   VexList vexlist;
}GraphList;



//建立邻接表
GraphList* createGraph(){
    GraphList *list=(GraphList *)malloc(sizeof(GraphList));

    printf("建立顶点表：\n");
    printf("输入顶点数据：\n");
    for(int i=0;i<VexNum;i++){//顶点数据
        
        //输入数据//数据放入节点
        scanf("%d",&(list->vexlist[i].data));
        list->vexlist[i].firstEdge=NULL;//边表先不指向
    }

    printf("建立边表：\n");
    printf("输入弧头i和弧尾j：\n");
    for(int k=0;k<edgeNum;k++){
        EdgeNode *e=(EdgeNode *)malloc(sizeof(EdgeNode));
        int i,j;
        
        scanf("%d%d",&i,&j);
        e->index=j;
        e->next=list->vexlist[i].firstEdge;
        list->vexlist[i].firstEdge=e;

        //无向图需要指回去
        e=(EdgeNode *)malloc(sizeof(EdgeNode));
        e->index=i;
        e->next=list->vexlist[j].firstEdge;
        list->vexlist[j].firstEdge=e;
    }

    printf("打印图：\n");
    for(int i=0;i<VexNum;i++){
        EdgeNode *p=list->vexlist[i].firstEdge;
        while(p){
            printf("(%d %d)",list->vexlist[i].data,list->vexlist[p->index].data);
            p=p->next;
        }
        printf("\n");
    }

    printf("结束\n");
    return list;
}

可以在主函数中测试一下：

int main(){
    GraphList *g=createGraph();
  
}

实现这个简单的表：

建立顶点表：
输入顶点数据：
4 3 2 1 0
建立边表：
输入弧头i和弧尾j：
0 4
1 2
2 0
2 3
3 4
1 0
打印图：
(4 3)(4 2)(4 0)
(3 4)(3 2)
(2 1)(2 4)(2 3)
(1 0)(1 2)
(0 1)(0 4)
结束

四、图的遍历

图的遍历有深度优先和广度优先。

深度优先遍历是从图中某个顶点出发,访问此顶点,然后从它未被访问到的邻接点出发深度优先遍历图,直到图中所有和它有路径相通的顶点都被访问到.，类似树的先序遍历。

广度优先遍历从某个顶点出发，访问其所有相邻元素，再从某个相邻元素开始广度优先遍历，类似树的层级遍历。

深度优先遍历

从一个元素开始，一直访问其相邻元素，访问后的元素被标记，下次不再访问。

int visit[MAXVEX];//标记是否被遍历，0未遍历，1已经遍历

//深度优先
void DFS(GraphList *list,int i){
    EdgeNode *p;
    visit[i]=1;//标记遍历
    printf("%d ",list->vexlist[i].data);
    p=list->vexlist[i].firstEdge;//指向边表
    while(p){
        if(visit[p->index]==0){
            DFS(list,p->index);
        }
        p=p->next;//指向下一边
    }
}

//深度优先遍历
void DFSVisit(GraphList *list){
    int i;
    for(i=0;i<VexNum;i++){
        visit[i]=0;//全部标记未遍历
    }
    for(i=0;i<VexNum;i++){
        if (visit[i]==0)
        {
            DFS(list,i);
        }    
    }

}

主方法测试：

int main(){
    GraphList *g=createGraph();
    printf("开始深度优先遍历：\n");
    DFSVisit(g);
}

按照上图所示，结果如下：

开始深度优先遍历：
4 3 2 1 0

广度优先遍历

广度优先遍历从一个元素开始访问其全部相邻元素，再按顺序对每个元素进行广度优先遍历，我们需要一个队列来存储等待遍历的元素。

广度优先遍历下，输入顶点 01234以及各条弧。

得到遍历结果： 01243