1 图存储结构的定义

1.1 图的邻接矩阵定义法

用一个一维数组存储图中顶点（vertex）的信息，用一个二维数组存储图中边（弧arc）的信息（即各顶点之间的邻接关系）。存储顶点之间的邻接关系的二维数组称为邻接矩阵。

 对于有向图，如果vi到vj有边，arc[vi][vj] = 1；如果vi到vj无边，arc[vi][vj] = 0。

 对于无向图，如果vi到vj有边，arc[vi][vj] = arc[vj][vi] = 1；如果vi到vj无边，arc[vi][vj] = arc[vj][vi] = 0。

 对于带权图（网），若顶点vi和vj之间有边相连，则邻接矩阵中对应项存放着对应的权值；若不相连，则用∞来表示两个顶点之间不存在的边。

#define MaxVertexNum 100#define VertexType int//## 1.1 图的邻接矩阵定义法typedef struct{                             VertexType vexs[MaxVertexNum];          //顶点信息    int arc[MaxVertexNum][MaxVertexNum];    //边（弧）信息    int vexnum,arcnum;                      //顶点数和边数}MGraph;    //以邻接矩阵存储的图类型

图的邻接矩阵存储表示法的特点：

1. 无向图的邻接矩阵一定是个对称矩阵，并且唯一。因此，在实际存储邻接矩阵只需存储上（下）三角矩阵的元素即可。

2. 对于无向图，邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。对于有向图，邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的出度（或入度）。

3. 容易确定图中任意两个顶点是否有边，但要确定图中有多少条边则按行（列）对每个元素检测，时间开销很大。

4. 空间复杂度为O(n^2)，适合存储稠密图。

5. 非带权图的邻接矩阵n次方值，就是对应顶点间路径长度为n的路径条数。

1.2 图的邻接表定义法

邻接表法是对图G中的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，这个单链表就称为顶点vi的边表（对于有向图则称为出边表），边表的头指针(firstarc)和顶点信息采用顺序存储，称为顶点表。所以，在邻接表中存在两种结点：顶点表（头）结点和边表结点。

#define MaxVertexNum 100#define VertexType int#define WeightType double//## 1.2 图的邻接表定义法typedef struct ArcNode{ //弧（边表）结点    int adjvex;         //弧所指顶点的位置（下标）    WeightType cost;    //带权图的边权值(info)    struct ArcNode *nextarc;//下一条弧指针    //ArcNode *nextarc; //is also ok}ArcNode;typedef struct{         //顶点表（顶点/头）结点    VertexType data;        //顶点数据    ArcNode *firstarc;      //指向第一条依附该顶点的弧指针}VNode,AdjList[MaxVertexNum];typedef struct{     AdjList vertices;       //邻接表    int vexnum,arcnum;      //顶点数和边数}ALGraph;           //以邻接表存储的图类型

图的邻接表存储表示法的特点：

1. 对于图G=(V,E)，如果G为无向图，则所需存储空间为O(|V|+2|E|)；如果G为有向图，则所需存储空间为O(|V|+|E|)。

2. 对于稀疏图，采用邻接表表示将大大节省存储空间。

3. 求某个顶点的所有邻边，只需读取它的邻接表。其效率O(ViE)一般比邻接矩阵O(n)所实现的优。

4. 确定两个顶点是否有边，需在邻接表相应的边表中查找另一个结点。其效率O(ViE)不如邻接矩阵O(1)所实现的。

5. 在有向图的邻接表中，求某个顶点的出度只需计算其边表结点个数；但求其入度，则需要遍历全部边表，因此可以设计逆邻接表实现快速求其入度，也可以设计下面的有向图的十字链表来实现。

6. 图的邻接表表示并不唯一，但可表示一个确定的图。因为每个顶点的边结点链接次序可以是任意的，取决于建立邻接表的算法和边的输入次序。

1.3 有向图的十字链表定义法

这里写图片描述

#define MaxVertexNum 100#define VertexType int#define InfoType double//## 1.3 有向图的十字链表定义法typedef struct XArcNode{    int tailvex,headvex;    struct XArcNode *hlink,*tlink;    //XArcNode *hlink,*tlink;//Successful    //InfoType info;}XArcNode;typedef struct{    VertexType data;    XArcNode *firstin,*firstout;}XVNode;typedef struct{    XVNode xlist[MaxVertexNum];    int vernum,arcnum;}XLGraph;

1.4 无向图的邻接多重表定义法

2 图的遍历

2.1 深度优先搜索

#include
    
     #define MaxVertexNum 100#define VertexType int#define WeightType double#define InfoType doubleint visited[MaxVertexNum];//## 1.1 图的邻接矩阵定义法typedef struct{    VertexType vexs[MaxVertexNum];    int arc[MaxVertexNum][MaxVertexNum];    int vexnum,arcnum;}MGraph;//## 1.2 图的邻接表定义法typedef struct ArcNode{    int nodeindex;    WeightType cost;    struct ArcNode *nextarc;    //ArcNode *nextarc;//Successful    //AdjNode *nextarc;//[Error] 'AdjNode' does not name a type}AdjNode;typedef struct{    VertexType data;    AdjNode *firstarc;}VNode,AdjList[MaxVertexNum];typedef struct{    AdjList vertices;    int vexnum,arcnum;}ALGraph,Graph;void DFS_M(MGraph G,int i){    visited[i]=1;    printf("%d ",i);//    for(int j=0;j
     
      nextarc){        int ind=p->nodeindex;        if(visited[ind]==0){            DFS_AL(G,ind);        }    }}void DFSTraverse(Graph G){    for(int i=0;i

2.2广度优先搜索

#include
    
     #define MaxVertexNum 100#define VertexType int#define WeightType double#define InfoType doubleint visited[MaxVertexNum];//## 1.1 图的邻接矩阵定义法typedef struct{    VertexType vexs[MaxVertexNum];    int arc[MaxVertexNum][MaxVertexNum];    int vexnum,arcnum;}MGraph;//## 1.2 图的邻接表定义法typedef struct ArcNode{    int nodeindex;    WeightType cost;    struct ArcNode *nextarc;    //ArcNode *nextarc;//Successful    //AdjNode *nextarc;//[Error] 'AdjNode' does not name a type}AdjNode;typedef struct{    VertexType data;    AdjNode *firstarc;}VNode,AdjList[MaxVertexNum];typedef struct{    AdjList vertices;    int vexnum,arcnum;}ALGraph,Graph;void BFS_AL(ALGraph G,int i){    visited[i]=1;    printf("%d ",i);    InitQueue(Q);    EnQueue(Q,i);    while(!IsEmpty(Q)){        int v;        DeQueue(Q,v);        for(ArcNode* p=G.vertices[v].firstarc;p;p=p->nextarc){            int ind=p->nodeindex;            if(visited[ind]==0){                printf("%d ",ind);                visited[ind]=1;                EnQueue(Q,ind);            }        }    }}void BFS_M(MGraph G,int i){    visited[i]=1;    printf("%d ",i);    InitQueue(Q);    EnQueue(Q,i);    while(!IsEmpty(Q)){        int v;        DeQueue(Q,v);        for(int ind=0;ind

3 图的基本应用

3.1 最小生成树

3.1.1 Prim算法

3.1.2 Kruskal算法

#include
    
     #include
     
      #define MaxVertexNum 100//## 1.1 图的邻接矩阵定义法using namespace std;typedef struct{    int a,b,w;}Road;typedef struct{    int vexnum,arcnum;    Road road[MaxVertexNum];}MGraph;    int sum=0;    MGraph G;    int v[MaxVertexNum];int getRoot(int n){    while(n!=v[n])        n=v[n];    return n;}bool cmp(Road r1,Road r2){    return r1.w

3.2 最短路径

3.2.1 Dijkstra算法

/** * Copyright ? 2016 Authors. All rights reserved. * * FileName: .cpp * Author: Wu_Being <1040003585@qq.com> * Date/Time: 10-12-16 10:34 * Description: */#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include
        
         #include
         
          #include 
          
           #define MAX_V 20000using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair
           
             Pii;const int inf = 0x7e7e7e7e;const LL infLL = 0x7e7e7e7e7e7e7e7eLL;const unsigned uinf = 0xfcfcfcfc;const ULL uinfLL = 0xfcfcfcfcfcfcfcfcLL;using namespace std;struct edge{ int to,cost;};typedef pair
            
             P;int V;vector
             
              G[MAX_V];int d[MAX_V];void dijkstra(int s){ priority_queue
              
               ,greater
                >que; fill(d,d+V,inf); d[s]=0;//!!!!!!!!!!! que.push(P(0,s)); while(!que.empty()){ P p=que.top();que.pop(); int v=p.second; if(d[v]
                
                 d[v]+e.cost){ d[e.to]=d[v]+e.cost; que.push(P(d[e.to],e.to)); } } }}void input(){ struct edge e; int E,f,t,c; cin>>V>>E; for(int i=0;i
                 
                  >f>>t>>c; e.cost=c; e.to=t-1; G[f-1].push_back(e); //e.to=f; G[t].push_back(e); }}int main(int argc,char* argv[]){ input(); dijkstra(0); for(int i=1;i

3.2.2 Floyd-Warshall算法

void Floyd(int n){    int i, j, k;    for (k=0; k
    
      dist[i][k] + dist[k][j])        {            dist[i][j] = dist[i][k] + dist[k][j];            path[i][j] = k;       //i到j要经过K节点        }}

3.3 拓扑排序

3.4 关键路径

4 图的实例

Wu_Being 博客声明：本人博客欢迎转载，请标明博客原文和原链接！谢谢！

《【数据结构6】图》

Wu_Being 吴兵博客接受赞助费二维码

如果你看完这篇博文，觉得对你有帮助，并且愿意付赞助费，那么我会更有动力写下去。