图的邻接矩阵存储和遍历

邻接矩阵存储

用一维数组存储数据元素（顶点）的信息，用二维数组存储数据元素之间的信息（弧边）。

对于无权图，二维数组元素的值是确定的，为 1 时表示顶点之间有弧边，为 0 时表示顶点之间没有边；
对于有权图，二维数组元素的值是该弧边的权值，为正常数值时表示边的权值，为 ∞（程序中用能表示的最大数） 时表示顶点之间没有弧边。

代码实现

顶点和弧边的定义

// 有向图，有向网，无向图，无向网
typedef enum { DG, DN, UDG, UDN } GraphKind;

// 顶点的数据类型
typedef char VertexType;
// 边的数据类型
typedef int ArcType;

typedef struct {
    VertexType vexs[MAX_VERTEX_NUM]; // 一维数组表顶点
    ArcType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 二维数组表示边
    int vexnum, arcnum; // 当前顶点数和边数
    GraphKind kind; // 图的种类标识
}MGraph;

深度优先遍历

在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。

递归深度搜索 DFS：

// DFS
void DFS(MGraph *G, int i, int *visited)
{
    int j;
    visited[i] = 1;
    printf("%c\t", G->vexs[i]);
    for (j = 0; j < G->vexnum; ++j)
        if(G->arcs[i][j] != INF && 0 == visited[j])
            DFS(G, visited, j);
}

广度优先遍历

从图中某个顶点V0出发，并访问此顶点；然后访问V0的各个未曾访问的邻接点W1，W2，…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点；重复步骤第二个步骤，直到全部顶点都被访问为止。

// 广度优先搜索BFS
void BFS(MGraph *G, int i, int *visited)
{
    SqQueue Q; InitQueue(&Q);
    int j;
    // 必须在进栈之前访问，否则会重复访问
    visited[i] = 1;
    printf("%c\t", G->vexs[i]);
    EnQueue(&Q, i);
    while(!QueueEmpty(&Q))
    {
        DeQueue(&Q, &i);
        for (j = 0; j < G->vexnum; ++j)
        {
            if(G->arcs[i][j] != INF && 0 == visited[j])
            {
                visited[j] = 1;
                printf("%c\t", G->vexs[j]);
                EnQueue(&Q, j);
            }
        }
    }
}

完整代码可参见：GitHub

DONE！