[Data Structure]图的建立与遍历（c语言）

图的建立

图的建立过程：

• 初始化一个没有边的图；
• 插入边构件图；

一. 邻接矩阵表示法
邻接矩阵表示法：通过一个矩阵来表示一张图，以下是结构体构建过程：

typedef struct GNode* PtrToGNode;
typedef PtrToGNode MGraph;
const int MaxVertexNum = 100;
struct GNode{
    /* 定义图的边数和条数 */
    int Nv,Ne;
    /* 用于存储矩阵 */
    WeightType G[MaxVertexNum][MaxVertexNum];
};

typedef struct ENode* PtrToENode;
typedef struct PtrToENode Edge;
struct ENode{
    /* 定义边的左右两个顶点 */
    int V1,V2;
    /* 定义边的权重值 */
    WeightType Weight;
};

至于你问我问什么要构建这两个结构体，对于第一个结构体，我认为这是一个常规操作，任何一个图都需要对顶点数和边数进行描述，同时为了能够用矩阵存储，所以我们定义了一个二维数组。

至于第二个结构体，我想说的是**“文章合为时而著，歌诗合为事而作”**，在题目对于顶点和边进行描述时，如果我们要在矩阵中插入一条边，自然需要这条边的两个顶点，如果是有权图就需要对权值进行描述。

接下来开始构建图：
1、初始化一个没有边的图；

/* 传入的参数为顶点数 */
MGraph CreateGraph(int VertexNum)
{
    MGraph M;
    int v,w;
    M->Nv = VertexNum;
    M->Ne = 0;
    for(v = 0;v < VertexNum;v++)
        for(w = 0;w < VertexNum;w++)
            M->G[v][w] = 0;
    return M;
}

2、插入边

/* 插入边 */
void Insert(MGraph M,Edge E)
{
    M->G[E->V1][E->V2] = E->Weight;
    /* 若为无向图则两边都需要 */
    M->G[E->V2][E->V1] = E->Weight;
}

3、完整的建立一个图

void GraphBuild()
{
    MGraph M;
    int VertexNum;/* 顶点数 */
    int EdgeNum;/* 边数 */
    Edge E;
    scanf("%d",&VertexNum);
    /* 初始化一个没有边的图 */
    M = CreateGraph(VertexNum);
    scanf("%d",&EdgeNum);
    if(!EdgeNum) /* 如果边数不为空 */
    {
        for(int i = 0;i < EdgeNum;i++){
            scanf("%d %d %d",&E->V1,&E->V2,&E->Weight);
            Insert(M,E);
        }
    }
    return;
}

二. 邻接表表示法
邻接表表示法，我觉得虽然好理解，但是程序已经把我绕晕了。
邻接表大概长成这么个样子（图是copy来的，侵删）

以下为邻接表表示法的结构体定义（里面的注释有关于这样建立结构体的理解）：

typedef struct LNode* LGraph; 
struct LNode{
    int Nv,Ne;
    AdjList G;
};

/* 
 * 这里的结构体类似于链表表头 
 * 而用结构数组存储的话就类似于存储了一堆表头
 */
typedef struct VNode{
    PtrToAdjVNode FistEdge;
    int data;
}AdjList[MaxVertexNum];/* 最大顶点数 */

/* 此处的AdjVNode很像链表 */
typedef struct AdjVNode* PtrToAdjVNode;
struct AdjVNode{
    int AdjVnode;/* 邻接点下标 */
    PtrToAdjVNode Next;
};

1、创建一个没有邻边的图：

LGraph CreateGraph(int VertexNum)
{
    LGraph L;
    int V,W;
    L = (LGraph)malloc(sizeof(struct LNode));
    L->Nv = VertexNum;
    L->Ne = 0;
    /* 将每一个链表从0开始编号，并且下一个节点为空 */
    for(V = 0;V < VertexNum;V++)
        L->G[V].FistEdge = NULL;
    return L;
}

2、插入边（模仿链表操作即可）

/* 此处可以模仿链表的操作 */
void InsertEdge(LGraph L,Edge E)
{
    PtrToAdjVNode NewNode;
    /* 将V2连接到V1后面 */
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->AdjVnode = E->V2;
    NewNode->Next = L->G[E->V1].FistEdge;
    L->G[E->V1].FistEdge = NewNode;
}

3、完整建立一个图
与上面矩阵建立一个矩阵的图代码基本上一模一样，我把代码放在下面，其实一模一样了。

LGraph BuildGraph()
{
    LGraph L;
    Edge E;
    int VertexNum,EdgeNum;
    L = CreateGraph(VertexNum);
    if(!EdgeNum)
    {
        for(int i = 0;i < EdgeNum;i++){
            scanf("%d%d%d",E->V1,E->V2,E->Weight);
            InsertEdge(L,E);
        }
    }
    return L;
}

图的遍历
图的遍历分为DFS和BFS两种：
DFS就是一条路走到黑，然后不断返回，检查是否有没有访问过的节点。而BFS则是，从一个节点开始访问与他相邻的所有节点，至于代码实现则主要使用了队列（Queue），当一个代码出队后，将所有与他相邻的顶点压入堆栈（除了已经访问过的顶点外）。

以下是具体代码实现。

DFS

void DFS(Vertex V)
{
    Visited[V] = TRUE;
    for(V的邻接点)
    {
        if(!Visited[W])
            DFS(W);
    }
}

BFS

void BFS(Vertex V)
{
    Vertex W;
    EnQueue(V,Q);
    Visited[V] = TRUE;
    while(!isEmpty(Q)){
        for(V的每个邻接点){
            if(!Visited[W]){
                Visited[W] = TRUE;
                EnQueue(W,Q);
            }
        }
    }
}

表面上看起来很简单，但是实际上在题目中有各种各样的破事，而且我好想只用DFS实现过题目。。
至于你问我为什么写了这么又臭又长的一篇文章，而且代码也不是我自己想出来的，是默写的。因为对于邻接表的那些结构体的定义确实不太理解，默写了以后好像终于有点理解了。

这是浙大MOOC的一项小小的课后作业？所以我认为这么多结构体，在不太理解的情况下可能确实需要默写吧。

邻接表建立图确实挺麻烦的，但用邻接表可以实现O(N+E)的时间复杂度，因为每个顶点和边建立的过程中只被用了1次，而矩阵的时间复杂度却达到了O(N2)的复杂度。

真的觉得难度挺大的，都怪自己暑假太浪了。暑假作业还没写完。。。压力有点大。

即使艰难，也还要做；愈难，就愈要做。