提示：有详细注释，若有错误还请多多指教。

一、图的存储结构

图是一种比树还要复杂的数据结构，表示多对多的关系。任意两个顶点之间都可能存在联系，因此不能以数据元素在存储区中的位置来表示元素之间的关系。
在实际应用中很多对应案例，因此大量使用，例如地图、好友关系等。
常用的存储结构如：
邻接矩阵

1. 邻接矩阵：适合稠密图；
2. 邻接表：适合稀疏图；
3. 十字链表：只能存储有向图
4. 邻接多重表：只能存储无向图

代码实现了邻接矩阵存储结构：用两个数组分别表示顶点表和边表。

#include <iostream>

using namespace std;

/***************************** 图的邻接矩阵存储************************************/
/*
*/
// vertex 顶点

#define MVNum 100           // 最大顶点数
typedef int VerTexType;    // 顶点类型
typedef int ArcType;        // 边的权值类型
typedef enum {DG,DN,UDG,UDN} GraphKind;     //{有向图，有向网，无向图，无向网}

typedef struct {
    VerTexType vexs[MVNum];     // 顶点表
    ArcType arcs[MVNum][MVNum]; // 邻接矩阵 
    int vexnum,arcnum;          // 当前的顶点数和边数
    GraphKind kind;             // 图的种类
}MGraph;       

// 通过顶点找到对应顶点表的下标
int LocateVex(MGraph G, VerTexType v) {
    for(int i = 1; i <= G.vexnum; ++i) {
        if(G.vexs[i] == v)
            return i;
    }
    return -1;
}

// 构造有向图
bool CraeteDG(MGraph &G) {
    // 输入顶点数和边数
    int vex,arc;
    cin>>vex>>arc;

    // 初始化
    for(int i = 1; i <= G.vexnum; ++i)
        cin>>G.vexs[i];
    for(int i = 1; i <= G.vexnum; ++i) {
        for(int j = 1; j <= G.vexnum; ++j) {
            G.arcs[i][j] = 0;               // 有向图中，以0表示没有边的两个顶点
        }
    }
    for(int k = 1; k <= G.arcnum; ++k) {
        VerTexType v1,v2;
        cin>>v1>>v2;     // 输入两个有边的顶点

        int i = LocateVex(G,v1);
        int j = LocateVex(G,v2);
        if(i ==-1 || j == -1)
            return false;
        G.arcs[i][j] = 1;
    }
    return true;
}
// 构造无向图
bool CreateUDG(MGraph &G) {
    // 输入顶点数和边数
    // int vex,arc;
    // cin>>vex>>arc;

    // 初始化
    for(int i = 1; i <= G.vexnum; ++i)
        cin>>G.vexs[i];
    for(int i = 1; i <= G.vexnum; ++i) {
        for(int j = 1; j <= G.vexnum; ++j) {
            G.arcs[i][j] = 0;       // 无向图中，以0表示没有边的两个顶点
        }
    }
    for(int k = 1; k <= G.arcnum; ++k) {
        VerTexType v1,v2;
        cin>>v1>>v2;     // 输入两个有边的顶点

        int i = LocateVex(G,v1);
        int j = LocateVex(G,v2);
        if(i ==-1 || j == -1)
            return false;
        G.arcs[i][j] = G.arcs[j][i] = 1;
    }
    return true;
}
// 构造无向网
bool CreateUDN(MGraph &G) {
    // 输入顶点数和边数
    int vex,arc;
    cin>>vex>>arc;

    // 初始化
    for(int i = 1; i <= G.vexnum;; ++i)
        cin>>G.vexs[i];
    for(int i = 1; i <= G.vexnum;; ++i) {
        for(int j = 1; j <= G.arcnum; ++j) {
            G.arcs[i][j] = INT32_MAX;       // 无向图中，以无穷大表示没有边的两个顶点
        }
    }
    for(int k = 0; k < arc; ++k) {
        VerTexType v1,v2;
        ArcType w;
        cin>>v1>>v2>>w;     // 输入两个有边的顶点和对应的权值

        int i = LocateVex(G,v1);
        int j = LocateVex(G,v2);
        if(i ==-1 || j == -1)
            return false;
        G.arcs[i][j] = G.arcs[j][i] = w;
    }
    return true;
}
// 构造有向网
bool CreateDN(MGraph &G) {
    // 输入顶点数和边数
    // int vex,arc;
    // cin>>vex>>arc;

    // 初始化
    for(int i = 1; i <= G.vexnum; ++i)
        cin>>G.vexs[i];
    for(int i = 1; i <= G.vexnum; ++i) {
        for(int j = 1; j <= G.vexnum; ++j) {
            G.arcs[i][j] = INT16_MAX;       // 无向图中，以无穷大表示没有边的两个顶点
        }
    }
    for(int k = 1; k <= G.arcnum; ++k) {
        VerTexType v1,v2;
        ArcType w;
        cin>>v1>>v2>>w;     // 输入两个有边的顶点和对应的权值

        int i = LocateVex(G,v1);
        int j = LocateVex(G,v2);
        if(i ==-1 || j == -1)
            return false;
        G.arcs[i][j] = w;
    }
    return true;
}

// 创建邻接矩阵的接口
bool CraeteGraph(MGraph &G,GraphKind kind) {
    switch (kind)
    {
        case DG:    return CraeteDG(G);     // 创建有向图
        case UDN:   return CreateUDN(G);    // 创建无向网
        case UDG:   return CreateUDG(G);    // 创建无向图
        case DN:    return CreateDN(G);     // 创建有向图
        default:    return false;
    }
}

二、遍历算法

在遍历事先建立图，代码如下：

#include "graph1.h"
#include <queue>

/************实例：邻接矩阵表示的无向图深度优先遍历实现****************/
/*输入实例
1 2 3 4 5 6
1 2
1 3
1 4
2 5
3 5
4 6
*/

int visit[100];     // 访问数组1--dfs
int visit2[100];     // 访问数组2---bfs
int main() 
{
    MGraph G;
    G.vexnum = 6;
    G.arcnum = 6;

    CraeteGraph(G,UDG); // 创建无向图
    PrintGraph(G);

    // DFS(G,2); 
    BFS(G,2); 

    return 0;
}

void PrintGraph(MGraph G) {
    // 打印图
    for(int i = 1; i <= G.vexnum; ++i) {
        for(int j = 1; j <= G.vexnum; ++j) {
            cout<<G.arcs[i][j]<<" ";
        }
        cout<<endl;
    }
    /*打印出来的邻接矩阵
        0 1 1 1 0 0 
        1 0 0 0 1 0 
        1 0 0 0 1 0 
        1 0 0 0 0 1 
        0 1 1 0 0 0 
        0 0 0 1 0 0
    */
}

1.DFS深度优先搜索

代码如下（示例）：

// 实例使用邻接矩阵表示图，其dfs时间复杂度： O(n*n)
// 若使用邻接表表示，dfs时间复杂度则为：O(n+e)，其实不需要dfs哈哈哈
void DFS(MGraph G,char start) {
    int st = start;
    visit[st] = 1;
    cout<<"已搜索到顶点："<<st<<endl;

    for(int i = 1; i<= G.vexnum; i++) {
        if(visit[i] == 0 && G.arcs[st][i] == 1) {
            DFS(G,i);
        }
    }
}

2.BFS广度优先搜索

代码如下（示例）：

// 广度优先遍历时间复杂度和深度优先相同，都是O(n*n)
// 空间复杂度也都是O(n)
void BFS(MGraph G,char start) {
    int st = start;
    queue<int> q;
    q.push(st);

    while(!q.empty()) {
        st = q.front(); q.pop();
        visit2[st] = 1;
        cout<<"已搜索到顶点："<<st<<endl;
        for(int i = 1; i <= G.arcnum; ++i) {
            if(visit2[i] == 0 && G.arcs[st][i] == 1) {
                q.push(i);
            }
        }
    }
}

三、最短路径问题（Dijkstra算法）

此类问题一般都为有向网（有向带权图）建立有向网如下图：

代码如下：

/*输入实例  --图为有向网
1 2 3 4 5 6
1 3 10
1 5 30
1 6 100
2 3 5
3 4 50
4 6 10
5 4 20
5 6 60

*/

实例代码：

void ShortestPath_DIJ(MGraph G,int start) {
    int re[G.vexnum + 1]; // 表示start点到其它点的最小距离，初始化为无穷大
    int visit[G.vexnum + 1] = {0};  // 0表示未访问过，1表示访问过
    int st = start;

    for(int i = 1; i <= G.vexnum; ++i)
        re[i] = G.arcs[st][i];
    re[st] = 0;     //到自己的距离为0

    for(int i = 1; i < G.vexnum; ++i) {
        int next;
        int _min = INT16_MAX;
        // 1、找出当前可到达的最近点，记录其下标
        for(int j = 1; j <= G.vexnum; ++j) {
            if(!visit[i] && re[i] < _min) {
                next = i; _min = re[i];
            }
        }
        visit[next] = 1;    // start到此点确定是最近的

        // 更新距离--通过next点，找到start到其它点的距离
        for(int k = 1; k <= G.vexnum; ++k) {
            if(_min + G.arcs[next][k] < re[k]) {
                re[k] = _min + G.arcs[next][k];
            }
        }
    }
    //打印start到各个顶点的最短路径
    for(int i = 1; i <= G.vexnum; ++i) {
        cout<<re[i]<<" ";
    }
    cout<<endl;
}

四、拓扑排序

DAG图：有向无环图；
用顶点表示活动，用弧表示优先关系的有向图称为用顶点表示活动的网，简称AOV网。
与之对应的是用边表示活动的网：AOE网，是一种带权的有向无环图，弧表示活动，权表示活动持续的时间。
在AOV网中，不应该出现环，因为存在环意味着某项活动以自己为先决条件，在四维空间中简直很荒谬。
判断是否有环？
经典求解思路是进行拓扑排序，当然进行dfs搜索也可以。注意：得到的拓扑有序序列不是唯一的，这很好理解，就是同一时刻可能会有多种选择。
时间复杂度分析：
拓扑排序需要知道每个结点的入度，所以如果使用邻接表存储则可以在头结点中增加一个存放入度的数组，则求顶点入度时间复杂度为O(e)，总的时间复杂度为O(n+e)。但是使用邻接矩阵的话,需要O(n*n)的时间复杂度求顶点的入度。
对于下图为例，建立邻接矩阵并求一个拓扑排序序列：

进行拓扑排序代码如下：

建立有向图实例：

/*输入实例  --图为有向图
1 2 3 4 5 6 7 8 9 10 11 12
1 2
1 4
1 3
1 12
2 3
3 5
3 7
3 8
4 5
5 7
6 8
9 10
9 11
9 12
10 12
11 6
*/

void TopologicalSort(MGraph G) {
    // 1、求出每个顶点的入度，记录在数组中，并将度为0的顶点入栈
    int indegree[G.vexnum] = {0};
    stack<int> s;
    for(int i = 1; i <= G.arcnum; ++i) {
        for(int j = 1; j <= G.arcnum; ++j) {
            if(G.arcs[i][j] == 1)
                indegree[j] ++;
        }
    }
    for(int i = 1; i <= G.vexnum; ++i)
        if(indegree[i] == 0) s.push(i);
    
    int count = 0;  // 计数，用于判断是否有环
    while(!s.empty()) {
        int t = s.top(); s.pop();
        cout<<"输出顶点："<<t<<endl;
        count++;
        for(int i =1; i <= G.arcnum; ++i) {
            if(G.arcs[t][i] == 1) {
                if(!(--indegree[i]))
                    s.push(i);
            }
        }
    }
    if(count < G.vexnum) {
        cout<<"该有向图有回路"<<endl;
    }
}
/*
    MGraph G;
    G.vexnum = 12;
    G.arcnum = 16;

    CraeteGraph(G,DG);  // 创建有向图
*/

总结

提示：这里对文章进行总结：