一、图的存储

1. 图的存储邻接矩阵法

#define MaxVertexNum 100  //顶点数目的最大值
typedef struct MGraph
{
    char Vex[MaxVertexNum];     //顶点表
    int Edge[MaxVertexNum][MaxVertexNum];   //邻接矩阵,边表
    int vexnum,arcnum;  //图当前顶点数和边数/弧数
}MGraph;

#define MaxVertexNum 100  //顶点数目的最大值
#define INFINITY 最大的int值    //宏定义常量"无穷"
typedef char VertexType;    //顶点数据类型
typedef int EdgeType;       //带权图中边上权值的数据类型
typedef struct MGraph
{
    VertexType Vex[MaxVertexNum];     //顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];   //邻接矩阵,边表
    int vexnum,arcnum;  //图当前顶点数和边数/弧数
}MGraph;

2. 图的存储邻接表法

无向图–边结点的数量是2|E|,整体空间复杂度为O(|V|+2|E|)

有向图–边结点的数量是|E|,整体空间复杂度为O(|V|+|E|)

#define MaxVertexNum 100  //图中顶点数目的最大值

typedef struct ArcNode      //边表结点
{
    int adjvex;             //该弧指向的顶点的位置
    struct ArcNode *next;   //指向下一条弧的指针
    //InfoType info;        //网的边权值
}

typedef struct VNode    //顶点表结点
{
    VertexType data;    //顶点信息
    ArcNode *first;     //指向第一条依附该结点(发出)的弧的指针
}VNode,AdjList[MaxVertexNum];

//用邻接表存储图
typedef struct
{
    AdjList vertices;   //顶点结点的数组---邻接表
    int vexmi,arcnum;   //图的顶点数和边/弧数
}ALGraph;   //ALGraph是以邻接表存储的图类型

二、图的遍历

1. 广度优先遍历（BFS-无向图）

/*****广度优先遍历(Breadth-First-Search,BFS)
***1.找到与一个顶点相邻的所有顶点
***2.标记哪些顶点被访问过
***3.需要一个辅助队列
*/
/**********复杂度分析**********/
/***空间复杂度：最坏情况，辅助队列大小为O(|V|)
 * 时间复杂度：
 *  (1)邻接矩阵存储的图：
 *      访问|V|个顶点需要O(|V|)的时间;
 *      查找每个顶点的邻接点都需要O(|V|)的时间，而总共有|V|个顶点
 *      时间复杂度=O(|V|^2)
 *  (2)邻接表存储的图：
 *      访问|V|个顶点需要O(|V|)的时间;
 *      查找每个顶点的邻接点共需要(O|E|)的时间,
 *      时间复杂度=O(|V|+|E|)
 * */

FirstNeighbor(G,x);//求图G中顶点x的第一个邻接点,若有则返回顶点号;
                    //若没有邻接点或图中不存在x,则返回-1;

NextNeighbor(G,x,y);//假设图G中顶点y是顶点x的一个邻接点,返回除y之外
                    //顶点x的下一个邻接点的顶点号,若y是x的最后一个邻接点,则返回-1;

bool visited[Max_VERTEX_NUM];   //访问标记数组,初始全为false

void BFSTraverse(Graph G)//对图G进行广度优先遍历
{
    for(int i=0;i<G.vexnum;i++)
        visited[i]=FALSE;   //访问标记数组初始化为false;
    InitQueue(Q);   //初始化辅助队列Q
    for(int i=0;i<G.vexnum;i++) //从0号顶点开始遍历
        if(!visited[i])     //对每个连通分量调用一次BFS;连通分量：极大连通子图
            BFS(G,i)        //vi未访问过,从vi开始再调用一次BFS
}                           //调用BFS的次数==连通分量数

//广度优先遍历(Breadth-First-Search,BFS)
void BFS(Graph h,int v) //从顶点v出发,广度优先遍历图G
{
    visit(v);           //访问初始顶点v
    visited[v]=TRUE;    //对v作已访问标记
    Enqueue(Q,v);       //顶点v入队列Q
    while(!isEmpty(Q))
    {
        DeQueue(Q,v);   //顶点v出队列
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
        {//检测v的所有邻接点
            if(!visited[w]) //w为v的尚未访问的邻接顶点
            {
                visit(w);   //访问顶点w
                visited[w]=TRUE;    //对顶点w作已访问标记
                EnQueue(Q,w);   //顶点w入队列Q
            }//if
        }
    }//while  
}

2. 广度优先遍历（BFS-有向图）

bool visited[MAX_VERTEX_NUM];   //访问标记数组
void BFSTraverse(Graph G)       //对图G进行广度优先遍历
{
    for(int i=0;i<G.vernum;i++)
        visited[i]=FALSE;   //访问标记数组初始化
    InitQueue(Q);           //初始化辅助队列Q
    for(int i=0;i<G.vernum;i++) //从0号顶点开始遍历
        if(!visited[i])     //对每个连通分量调用一次BFS
            BFS(G,i);       //vi未访问过,从vi开始再调用一次BFS
}
//广度优先遍历
void BFS(Graph G,int v)     //从顶点v出发，广度优先遍历图G
{
    visit(v);       //访问初始顶点v
    visited[v]=TRUE;    //对顶点v作已访问标记
    EnQueue(Q,v);       //顶点v入队列Q
    while(!isEmpty(Q))
    {
        DeQueue(Q,v);   //顶点v出队列
        for(int w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
        {   //检测v所有邻接点
            if(!visited[w]) //w为v的尚未访问的邻接顶点
            {
                visit(w);   //访问顶点w
                visited[w]=TRUE;    //对访问顶点w作已访问标记
                EnQueue(Q,w);       //顶点w入队列Q
            }//if
        }
    }//while
}

3. 树的先根遍历

//树的先根遍历
void PreOrder(TreeNode *R)
{
    if(R!=NULL)
    {
        visit(R);   //访问根结点
        while(R还有下一个子树T)
            PreOrder(T);    //先根遍历下一棵子树
    }
}

4. 深度优先遍历

//深度优先遍历
/*** 空间复杂度：来自函数调用栈，最坏情况，递归深度为O(|V|)
 *              最好情况，O(1)
 * 
 *   时间复杂度=访问各顶点所需时间+探索各条边所需时间
 *      (1)邻接矩阵存储的图
 *          访问|V|个顶点需要O(|V|)的时间
 *          查找每个顶点的邻接点都需要O(|V|)的时间，而共有|V|个顶点
 *          时间复杂度=O(|V|^2)
 *      (2)邻接表存储的图
 *          访问|V|个顶点需要O(|V|)的时间
 *          查找每个顶点的邻接点共需要O(|E|)的时间,
 *          时间复杂度=O(|V|+|E|)
 *          
*/

bool visited[MAX_VERTEX_NUM];   //访问标记数组

bool DFSTraverse(graph G)   //对图G进行深度优先遍历
{
    for(int v=0;v<G.vexnum;v++)
        visited[v]=FALSE;   //初始化已访问标记数组
    for(int v=0;v<G.vexnum;v++)
        if(!visited[v])
            DFS(G,v);
}

void DFS(Graph G,int v) //从顶点v出发，深度优先遍历图G
{
    visit(v);   //访问顶点v
    visited[i]=TRUE;    //设已访问标记
    for(int w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
    {   //w为v的尚未访问的邻接顶点
        if(!visited[w])
        {
            DFS(G,w);
        }//if
    }//for
}

5. BFS求最短路径

bool visited[MAX_VERTEX_NUM]; //访问标记数组

FirstNeighbor(G, x); //求图G中顶点x的第一个邻接点,若有则返回顶点号;
                     //若没有邻接点或图中不存在x,则返回-1;

NextNeighbor(G, x, y); //假设图G中顶点y是顶点x的一个邻接点,返回除y之外
                       //顶点x的下一个邻接点的顶点号,若y是x的最后一个邻接点,则返回-1;

//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G, int u)
{
    //d[i]表示从u到i结点的最短路径
    for (int i = 0; i < G.vexnum; i++)
    {
        int d[i] = 25536; //初始化路径长度，近似于∞
        int path[i] = -1; //最短路径从哪个顶点过来
    }
    d[u] = 0;
    visited[u] = TRUE;
    EnQueue(Q, u);
    while (!isEmpty(Q)) //BFS算法主过程
    {
        DeQueue(Q, u); //队头元素u出队列
        for (int w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w))
        {
            if (!visited[w]) //w为u的尚未访问的邻接顶点
            {
                d[w] = d[u] + 1;   //路径长度+1
                path[w] = u;       //最短路径应为从u到w
                visited[w] = TRUE; //设已访问标记
                EnQueue(Q, w);
            } //if
        }     //for
    }         //while
}

/*在BFS基础上改造
void BFS(Graph G,int v)
{
    visit(v);   //访问初始顶点v
    visited[v]=TRUE;    //对v作已访问标记
    EnQueue(Q,v);   //顶点v入队列Q
    while(!isEmpty(Q))
    {
        DeQueue(Q,v);   //顶点v出队列
        for(int w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
        {
            //检测v所有邻接点
            if(!visited[w])     //w为v的尚未访问的邻接顶点
            {
                visit(w);       //访问顶点w
                visited[w]=TRUE;//对w作已访问标记
                EnQueue(Q,w);   //顶点w入队列
            }//if
        }//for
    }//while
}
*/

6. Floyd算法核心代码

//...准备工作,根据图的信息初始化矩阵A 和 path
for(int k=0;k<n;k++)    //考虑以Vk作为中转点
{
    for(int i=0;i<n;i++)    //遍历整个矩阵,i为行号,j为列号
    {
        for(int j=0;j<n;j++)
        {
            if(A[i][j]>A[i][k]+A[k][j]) //以Vk为中转点的路径更短
            {
                A[i][j]=A[i][k]+A[k][j];//更新最短路径长度
                path[i][j]=k;           //更新中转点
            }
        }
    }
}
//时间复杂度:O(|V|^3)
//空间复杂度:O(|V|^2)

7. 拓扑排序

#define MaxVertexNum 100    //图中顶点数目的最大值
typedef struct ArcNode      //边表结点
{
    int adjvex; //该弧所指向的顶点的位置
    struct ArcNode *nextarc;    //指向下一条弧的指针
    //InfoType info;    //网的边权值
}ArcNode;
typedef struct VNode    //顶点表结点
{
    VertexType data;    //顶点信息
    ArcNode *firstarc;  //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];

typedef struct
{
    AdjList vertices;   //邻接表
    int vexnum,arcnum;  //图的顶点数和弧数
}Graph;     //Graph是以邻接表存储的图类型

bool TopologicalSort(Graph G)
{
    InitStack(S);   //保存入度为0的顶点，也可用队列
    for(int i=0;i<G.vexnum;i++)
    {
        if(indegree[i]==0)  //indegree[] 当前顶点入度
            Push(S,i);  //将所有入度为0的顶点入栈
    }
    int count=0;    //计数，记录当前已经输出的顶点数
    while(!IsEmpty(S))  //栈非空，则存在入度为0的顶点
    {
        Pop(S,i);   //栈顶元素出栈
        print[count++]==i;  //输出顶点i     //print[]记录拓扑排序序列
        for(p=G.vertices[i].firstarc;p!=NULL;p=p->nextarc)
        {
            //将所有i指向的顶点的入度-1，并将入度为0的顶点压入栈S
            v=p->adjvex;
            if(!(--indegree[v]))
                Push(S,v);      //入度为0,入栈

        }
    }//while
    if(count<G.vexnum)
        return false;   //拓扑排序失败，有向图中有回路
    else
        return true;    //拓扑排序成功
}

8. 逆拓扑排序（DFS算法）

#include<stdio.h>
#define MaxVertexNum 100    //图中顶点数目的最大值
#define VertexType char
typedef struct ArcNode      //边表结点
{
    int adjvex; //该弧所指向的顶点的位置
    struct ArcNode *nextarc;    //指向下一条弧的指针
    //InfoType info;    //网的边权值
}ArcNode;
typedef struct VNode    //顶点表结点
{
    VertexType data;    //顶点信息
    ArcNode *firstarc;  //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];

typedef struct
{
    AdjList vertices;   //邻接表
    int vexnum,arcnum;  //图的顶点数和弧数
}Graph;     //Graph是以邻接表存储的图类型
void DFSTraverse(Graph G)   //对图G进行深度优先遍历
{
    for(int v=0;v<G.vexnum;v++)
        visited[i]=false;   //初始化已访问标记数据
    for(int v=0;v<G.vexnum;v++) //本代码中是从v=0开始遍历
        if(!visited[i])
            DFS(G,v);
}
void DFS(Graph G,int v) //从顶点v出发，深度优先遍历图G
{
    visited[v]=true;    //设置已访问标记
    for(int w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
    {
        if(!visited[w]) //w为v的尚未访问的邻接顶点
        {
            DFS(G,w);
        }//if
    }//for
    print(v);   //输出顶点-------DFS实现逆拓扑排序在顶点退栈前输出
}