一、定义
一个图状结构G由顶点集V和边集E组成，常记为G=(V,E)
V(G)表示图G中所有顶点的集合，一定是非空的集合。
E(G)表示图G中所有边的集合，可以为空集。
二、属性
在表示一个边的时候，我们常用顶点对的方式来表示连接这两个顶点的一个边。例如顶点W和顶点V的顶点对，表示连接顶点W和V的边。
（一）有向与无向
根据边集E中存储的边是否有方向，可以将边分为有向边与无向边，进而区分出有向图与无向图。
1、无向图
若E中存储的边是无向边，则图G为无向图，常记为(V,W)或(W,V)，由于无向边没有方向的要求，因此(V,W)=(W,V)。
2、有向图
若E中存储的边是有向边，则图G为有向图，常记为<V,W>，表示由V指向W的一条边或弧，V称为弧尾，W称为弧头。同理有<W,V>，表示由W指向V的一条边或弧。显然，<V,W>不等于<W,V>。
（二）简单与多重
根据顶点之间是否存在重复边以及是否存在顶点到自身的边，可以区分出简单图与多重图。
1、简单图
满足①顶点之间不存在重复的边；②不存在顶点到自身的边；这两个条件的图称为简单图。
2、多重图
允许顶点之间存在重复边和顶点到自身的边这种条件的图称为多重图。
（三）度
度：连接一个顶点的边的总数称为这一个顶点的度。
入度：在有向图中，指向顶点V或者说以顶点V为终点的边的总数称为入度。
出度：在有向图中，由顶点V指出或者说以顶点V为起点的边的总数称为出度。
（四）顶点关系
1、路径
由一个顶点V沿着边到另一个顶点W所经过的所有顶点的序列称为由V到W的一条路径，在有向图中，路径只能沿着边的指向运动。
2、回路
一条路径的起点和终点是同一个顶点，这样的路径称为回路。
3、简单路径
在路径的序列中，不出现重复顶点的路径称为简单路径。
4、简单回路
在回路的序列中，除了起点和终点外，不出现重复顶点的回路称为简单回路。
5、路径长度
在一个路径中边的数目称为路径长度。
6、点到点的距离
从顶点V到顶点W的所有路径中，长度最短的路径称为V到W的距离，若不存在任何一条路径，我们一般称V到W的距离是无穷。
7、连通性
若图G中任意两个顶点都存在路径，则称图G为连通图，否则称为非连通图。若图G为有向图，我们称图G为强连通图。
（五）局部图
1、子图
设有两个图G=(V,E)和G'=(V',E')，若有V'是V的子集，且E'是E的子集，则称G'是G的子图。
若V=V'，即G与G'有相同的顶点集，则称G'是G的生成子图。
【注意】每个边一定要连接两个顶点，因此并非任意的顶点和边就能够构成子图！
２、极大连通子图
在无向图中，在子图是连通图的前提下，尽可能多地包括顶点和边，这样的子图称为极大连通子图，也称为连通分量。
在有向图中，在子图是强连通图的前提下，尽可能多地包括顶点和边，这样的子图称为极大强连通子图，也称为强连通分量。
3、生成树
在连通图中，在包含所有顶点的前提下，尽可能少地包含边，这样构成的一个极小连通子图，称为生成树。
在非连通图中。各个连通分量形成的生成树的集合，称为生成森林。
（六）边权
在一个图中，可以在边上标注具有某种含义的数值，这样的数值称为边的权。
若一个图的边上标注了权值，这样的图就称为带权图，或称为网。
在带权图中，一条路径上所有边的权值之和，称为这条路径的带权路径长度。
三、特殊图
（一）完全图
在无向图中，任意两个顶点之间都存在边的图，称为无向完全图。
在有向图中，任意两个顶点之间都存在双向边的图，称为有向完全图。
（二）稀疏图与稠密图
将边数很少的图称为稀疏图，边数很多的图称为稠密图。
【注意】没有绝对的界限，但我们一般将E=VlogV作为界限。
（三）树
在无向图中，将不存在回路，且连通的图称为树。
在有向图中，将仅有一个顶点入度为0，其余顶点入度均为1的图称为有向树。
四、存储结构
（一）邻接矩阵
邻接矩阵法是用二维数组的方式来存储图，以顶点作为行标与列标，例如[行A][列B]，表示从顶点A到顶点B的一条边，若边存在，将数值设为1（或边权）；若边不存在，将数值设为0（或无穷）。

typedef struct{
    VertexType Vex[MaxSize];
    //VertexType表示顶点的数据类型，Vex用于存储顶点
    EdgeType Edge[MaxSize][MaxSize];
    //EdgeType表示边的数据类型，Edge用于存储边
    int Vexnum,Arcnum;
    //Vexnum与Arcnum分别表示顶点与边的个数
}MGraph;

（二）邻接表法
邻接表法使用顺序存储和链式存储相结合的方式，以顺序数组来存储顶点和指向第一个边的指针，并将其他的边以链式存储的方式连接到第一个边的链表上。

//定义存储边的结点
typedef struct ArcNode{
    int Adjvex;//记录边指向哪一个顶点
    struct ArcNode *next;//指向下一个边结点
}ArcNode;
//定义顶点数组
typedef struct VNode{
    VertexType data;//存储顶点数据
    ArcNode *first;//指向第一个边结点
}VNode,AdjList[MaxSize];

（三）十字链表法
十字链表法使用链式存储的方式，多用于存储有向图，分别定义顶点结点和弧结点。

//弧结点
typedef struct ArcNode{
    int info;
    //记录边的权值
    int TailVex,HeadVex;
    //记录连接的顶点，TailVex表示弧尾顶点，HeadVex表示弧头顶点
    struct ArcNode *Hlink,*Tlink;
    //Hlink指向弧头顶点相同的下一个结点，Tlink表示弧尾顶点相同的下一个结点
}ArcNode;
//顶点结点
typedef struct VNode{
    VertexType data;
    struct ArcNode *FirstIn,*FirstOut;
}VNode;

（四）邻接多重表
邻接多重表使用链式存储的方式，多用于存储无向图，与十字链表类似，只是边结点解释方式和顶点结点的定义略有不同。

//边结点
typedef struct ArcNode{
    int info;
    int TailVex,HeadVex;
    //在邻接多重表中，解释为连接的两个顶点
    struct ArcNode *Hlink,*Tlink;
}ArcNode;
//顶点结点
typedef struct VNode{
    VertexType data;
    struct ArcNode *FirstEdge;
}VNode;

五、遍历算法
（一）广度优先遍历(BFS)
广度优先遍历会优先访问与该结点相邻的所有结点，与树不同，由于存在回路，因此我们需要设置辅助数组记录一个结点是否已经被访问。

FirstNeighbor(G,x);
//FirstNeighbor函数：求图G的结点X的第一个邻接点，若存在返回顶点号，不存在返回-1；具体实现根据存储结构的不同有所差异。
NextNeighbor(G,x,y);
//NextNeighbor函数：求图G的结点X已访问邻接点y之后的下一个邻接点的顶点号，若存在返回顶点号，不存在返回-1；

//定义辅助数组
bool Visited[Maxsize];//初始设为false;
//定义访问队列
int Q[MaxSize];
//广度优先遍历
void BFSTraverse(Graph G){
    for(int i=0;i<G;++i)
    {
        visited[i]=false;
    }
    InitQueue(Q);
    for(int i=0;i<G.vexnum;++i)
    {
        if(!visit[i])
        {
            BFS(G,i);
        }
    }
}
//广度优先遍历
void BFS(Graph G,int V){
    visit(V);
    visited[V]=true;
    EnQueue(Q,V);
    while(!IsEmpty(Q))
    {
        DeQueue(Q,V);
        for(W=FirstNeighbor(G,V);W>=0;W=NextNeighbor(G,V,W))
        {
            if(!visited[W])
            {
                visit(W);
                visited[W]=true;
                EnQueue(Q,W);
            }
        }
    }
}

（二）深度优先遍历(DFS)

bool visit[MaxSize];
//深度优先遍历
void DFSTraverse(Graph G){
    for(V=0;V<G.Vexnum;++V)
    {
        visited[V]=false;
    }
    for(V=0;V<G.Vexnum;++V)
    {
        if(!visited[V])
        {
            DFS(G,V);
        }
    }
}
//深度优先遍历
void DFS(Graph G,int V){
    visit(V);
    visit[V]=true;
    for(W=FirstNeighbor(G,V);W>=0;W=NextNeighbor(G,V,W))
    {
        if(!visit[W])
        {
            DFS(G,W);
        }
    }
}

六、最小生成树算法
（一）Prim算法
①从一个顶点开始构造生成树
②将生成树中所有顶点相邻的边权最小的顶点纳入生成树
③重复上述步骤
（二）kruskal算法
①从权值最小的边开始连通结点
②每次选择权值最小的还没有被连通的结点的边
③重复上述步骤
七、最短路径算法
（一）BFS算法

void BFS_MinDistance(Graph G,int v){
    for(i=0;i<G.Vexnum;++i)
    {
        d[i]=无穷;
        path[i]=-1;
    }
    d[v]=0;
    visited[v]=true;
    EnQueue[Q,v];
    while(!IsEmpty(Q))
    {
        DeQueue(Q,v);
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
        {
            if(!visited(w))
            {
                d[w]=d[v]+1;
                path[w]=v;
                visited[w]=true;
                EnQueue(Q,w);
            }
        }
    }
}

（二）Dijkstra算法
①从一个结点开始，计算由它到其他结点的最短距离，非邻接点记为无穷；
②选择距离最短的结点加入，并重新计算加入该点之后的最短距离。
③重复上述步骤。
（三）Floyd算法
从不允许有任何中转点开始，逐渐添加中转点，依次计算距离。