扩张注释为个人学习想法

两种存储结构—邻接矩阵和邻接表（理解算法的前提，结构不清楚别看算法）

1. 邻接矩阵

//若只是为了建立二维数组自然没必要使用结构体定义，但往往还需要定义其顶点数和边数等信息
//此时使用结构体将其抽象为一个图的数据结构就很有必要了（抽象大法好）
//先定义结点，因为结点自身可能会携带其他信息
typedef struct {
    int ind;    //结点编号
    int info;    //其他信息
}VType;
//定义邻接矩阵
typedef struct{
    int edges[maxSize][maxSIze];    //注意到这里不是结点的二维数组而是边，若是有权图改为float
    int n,e;    //结点数，边数
    VType vex[maxSize];    //节点信息
}Mgraph;    //Matrix of Graph

2.邻接表

//先定义表所连边，即从当前结点出发到下个结点的边（弧尾为当前结点）
typedef struct ArcNode{
    int ind;    //对应邻接表的下标而不是数据，这也是为什么说这是边的数据结构
    stuct ArcNode *nextArc;
    int w;    //边的权重
}ArcNode;

//表内元素，即图结点
typedef struct VNode{    //其实个人更倾向于写成adjNode，不过VNode在看图时更清晰
    int data;    //数据
    ArcNode *firstArc;    //第一条边
    int i,o;    //有需要的话定义出入度
}VNode;

//邻接表
typedef struct {
    VNode adjlist[maxSize];
    int n,e;    //顶点数和边数
}AGraph;    //Adjacent list of Graph

深度优先遍历（DFS）

tips：利用递归存储的特性使其在“搜索”到最深处的时候可以顺序回退，在其每次抵达结点时都需要对当前结点进行一个标记（很明显即二叉树先序遍历思路，进入递归前visit()当前结点），需要设置一个全局数组visited()记录一下结点的访问信息，防止二次访问

int visited[maxSize]={0};
void DFS(AGrpah *G, int v){	//从v开始遍历
    ArcNode *p = G->adjlist[v].firstArc;
    visited[v] = 1;
    while(p!=NULL){
        if(visited[p->ind]!=1) DFS(G, p);
        p = p->nextArc;
}

把所有经历的边保留，其他删去（可以在 visited[] 检测为1时定义 q 记录当前 p ，令 p 指向下一条边后，释放 q 所指边），即可得到深度优先生成树

广度优先算法（BFS）–类似于二叉树层次遍历

1. 假定给的初始节点 v 是邻接表的数组下标，初始通过图对应的邻接表 G->adjlist[v].first 得到“第一条”边（即 firstArc ），并用 p 记录下该边
2. p->nextArc 循环遍历同层结点，直至 p==NULL ，记录下每次新顶点的下标至队列 queue 中，并将对应 visited 置为1
3. 设置front，rear指针分别指向队头队尾以用于出入队，当front==rear时队列元素清空，遍历完成
   每次出队的结点循环上述操作

void BFS(AGraph* G, int v, int visited[]){
    memset(visited,0,maxSize);    //初始化数组
    ArcNode* p;
    int queue[maxSize], front = 0, rear = 0, j;    //j为此时出队结点
    visit();    //visit()为对该结点操作函数,看情况进行定义
    visited[v] = 1;    //将初始结点标记已访问
    queue(rear++) = v;    //队列存储的是下标,因为边所定义的ind指向的是下标
    while(front!=rear){    //没使用循环队列
        p = G->adjlist[v].firstArc;
        j = queue[front++];    //出队
        while(p!=NULL){    //层次遍历
            if(visited[p.ind]!=1){
                visit();
                queue[rear++] = p.ind;    //将未访问过的结点入队
                visited[p.ind] = 1;    //标记已访问
            }
        p = p->nextArc;    
        }
    }
}

实际上以上 DFS 和 BFS 仅适用于连通分量（即极大连通子图）只有一个的情况下，不过要适用多个非常简单，外层套一个循环在发现 visited 值不为1时再次使用函数即可//以DFS为例，BFS一样

void DFS_Traverse(Agraph *G){
    for(int v=0;v<G.n;v++){
        if(!visited[v]) DFS(G,v);    //!visited[v]即visited[v]==0
    }
}

知乎同链，有误可评论指正