图的基本概念

从各种数据结构上来看，线性表内包含的是1对1的关系，树包含的是1对多的关系，而图包含的是多对多的关系，一个图可以表示一个社交网络，在图结构中，每个元素都可以有零个或多个前驱，也可以有零个或多个后继，也就是说，元素之间的关系是任意的。这是一个随意的图。
在这里插入图片描述

1、有向图和无向图

有向图与无向图的区别是，对于无向图而言，在一条边(u，v)中，u和v不存在谁指向谁的方向关系，即（u，v）和（v，u）是同一条边。无向图的边常用一对圆括号表示。
如下便是一张无向图。
在这里插入图片描述
对于有向图而言，在一条边中，u和v存在谁指向谁的方向关系，即和不是同一条边，代表u指向v，代表v指向u。有向图的边常用一对尖括号表示。
如下是一个有向图：

2、权值与网

图的结构常常会让我们想起地图，在地图上两个点之间是存在距离的，在图中我们可以把这种“距离”类似的概念称为，即图的每条边上可能存在具有某种含义的数值，称该数值为该边上的权。
就像这样：
在这里插入图片描述
这种存在权值的图被称作网。

3、顶点的度

顶点的度：顶点关联的边的数目。
无向图中顶点的度就是顶点周围边的数量。
有向图中存在入度和出度，入读指的是方向指向顶点的边；出度指的是方向背向顶点的边。在有向图中顶点的度就是两者之和。

4、邻接矩阵表示法

在邻接矩阵中，用两个数组保存数据。一个一维数组存储图中的顶点信息，一个二维数组存储图中的边或弧的信息。
对于这样一幅无向图而言：
在这里插入图片描述
其邻接矩阵表示法的顶点数组和边数组分别为：

对于这样一副有向图而言：

其邻接矩阵表示法的顶点数组和边数组分别为：

BFS的实现方法

广度优先搜索与树的层次遍历过程类似。
常常需要借助一个队列来实现图的广度优先搜索。
以下图为例，要想遍历abcdef六个顶点，可以将整幅图设为三层，a为第一层，b、c、d为第二层，e、f为第三层，再逐个遍历每一层的每个顶点。
在这里插入图片描述
具体遍历的过程如下：
1、创建一个visited数组，用来记录已被访问过的点；创建一个队列，用来存放按照遍历顺序存放的点；初始化图Graph。
2、从图中的a开始访问，将的visited[0]数组的值设置为1，同时将v0入队。
3、while队列不空： a、队头head出队，显示内容； b、检查head所有的邻接点n，若visited[n]的值为0，则代表该点尚未被访问过；c、访问n，并将visited[n]置为1，同时将n压入队列。
假设顶点数组的存储顺序为：a、b、c、d、e、f。
那么遍历结果为：
a b c d e f。
接下来我将具体展示如何进行BFS：
白底代表尚未访问，黄底代表已经访问！
1、初始状态。
在这里插入图片描述
2、访问a点，根据顶点数组的存储顺序，visited[0]设为1；将a压入队列。

3、将a点取出队列，访问其周围所有邻接点，若对应visited[n]的值为0，则代表该点尚未被访问过，访问之，并将其压入队列，访问顺序根据顶点数组的存储顺序决定，存储顺序为a b c d e f。
在这里插入图片描述

4、所有邻接点访问完后，重新取出队头元素，此时队头元素为b，访问其周围所有邻接点，若对应visited[n]的值为0，则代表该点尚未被访问过，访问之，并将其压入队列，访问顺序根据顶点数组的存储顺序决定，存储顺序为a b c d e f。在本步骤中，由于d已经被访问，因此无需再次访问，紧接着访问e f。
在这里插入图片描述

此时便完成了所有点的访问。在接下来的时间里，c d e f会依次出队，由于visted数组全为1，访问结束。

利用c语言实现BFS

#include<stdlib.h>
#include<stdio.h>
#define VexNum 100
typedef char Ele;
struct Node{
    Ele data;
    struct Node* Next;        //data用于存储信息，Next用于存储下一个队列下一个元素的地址。
};
typedef struct Node* LinkedList;
struct Queue{
    LinkedList head;
    LinkedList tail;        //head为队头，tail为队尾。
};
typedef struct Queue QueueList;
void init(QueueList* q){
    q->head = q->tail = (LinkedList)malloc(sizeof(struct Node));
    if (q->head == NULL){
        printf("内存空间分配失败");
        exit(1);
    }
    q->head->Next = NULL;
}
void push(QueueList* q, Ele e){
    LinkedList p;
    p = (LinkedList)malloc(sizeof(struct Node));
    if (p == NULL){
        printf("内存空间分配失败");
        exit(1);
    }
    p->Next = NULL;
    p->data = e;
    q->tail->Next = p;    //将元素压入队列、将队尾指针指向新节点
    q->tail = p;
}
void pop(QueueList* q,Ele *e){
    LinkedList p;
    if (q->head == q->tail){
        printf("队列已空");
        exit(1);
    }
    p = q->head->Next;
    q->head->Next = p->Next;    //利用p取出队头
    *e = p->data;
    if (q->tail == p){
        q->tail = q->head;        //判断是否取出所有元素，如果取出所有元素，队头指向队尾
    }
    free(p);                    //释放中间节点
}
bool empty(QueueList* q){
    return q->head == q->tail;
}
typedef struct Graph            //利用邻接矩阵表示
{
    char vexs[VexNum];            //顶点
    int arcs[VexNum][VexNum];    //边    
    int vexnum, arcnum;            //顶点和边的数量
}Graph;
int LocateVex(Graph *G, char c)    //输入顶点符号，寻找其对应的位置
{
    for (int i = 0; i < G->vexnum; i++)
    {
        if (G->vexs[i] == c)
            return i;
    }
}
void initGraph(Graph *G)                    //图的初始化
{
    int i, j;
    char c1, c2;
    scanf("%d %d", &G->vexnum, &G->arcnum);
    getchar();
    for (i = 0; i < G->vexnum; i++)
        for (j = 0; j < G->vexnum; j++)
            G->arcs[i][j] = 0;                //初始化每条边为0
    for (i = 0; i < G->vexnum; i++)
        scanf("%c", &G->vexs[i]);            //输入点的信息
    for (int k = 0; k < G->arcnum; k++)            //创建边的信息
    {
        getchar();
        scanf("%c%c", &c1, &c2);            //输入一条边依附的顶点
        i = LocateVex(G, c1);                //找到顶点i的下标
        j = LocateVex(G, c2);                //找到顶点j的下标
        G->arcs[i][j] = G->arcs[j][i] = 1;
    }
}
bool visited[VexNum];
void BFS(Graph *G, char c0)                    //从c0开始遍历整个图
{
    QueueList q;
    char e;
    int index0,i;
    init(&q);
    for (i = 0; i < G->vexnum; i++){
        visited[i] = 0;
    }
    index0 = LocateVex(G, c0);
    visited[index0] = 1;
    push(&q,c0);
    printf("%c ", c0);
    while (!empty(&q))
    {
        pop(&q,&e);
        index0 = LocateVex(G, e);
        for (i = 0; i < G->vexnum; i++)
        {
            if (G->arcs[index0][i] && !visited[i])
            {
                e = G->vexs[i];
                printf("%c ", e);    //打印顶点w
                push(&q,e);        //将顶点w入队
                visited[i] = 1;        //顶点w已被访问
            }
        }
    }
}
void main(){
    Graph G;
    initGraph(&G);
    BFS(&G,'a');
}