图的定义

图G=(V,E)由顶点（vertex）的集V和边（edge）的集E组成，每一条边就是一个点对（v，w）。如果点对即边是没有方向的，那么就是无向图，如果边是有方向的，那么就是有向图。无向图点对用（v，w）表示，有向图点对用<v,w>表示。有些图的边会有权重，用来表示边的权值。当图的每一个顶点与其他定点都存在一条边时为完全图。图a、b分别为有向图和无向图：
　　　　　 　　　　　　　　　
　　　　　

图a：
V(G)={V1，V2，V3，V4，V5}
E(G)={(V1，V2)，(V1，V4)，(V2，V3)，(V2，V5)，(V3，V4)，(V3，V5)，(V4，V5)}
图b：
V(G)={V1，V2，V3}
E(G)={<V1，V2>，<V2，V3>，<V3，V1>，<V1，V3>}

　　对于无向图，顶点的度表示以该顶点作为一个端点的边的数目。对于有向图，顶点的度分为入度和出度。入度表示以该顶点为终点的入边数目，出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。

数据结构复习之【图】
数据结构和算法系列17 图

图的存储结构

图主要有两种存储结构：邻接矩阵和邻接表。
邻接矩阵：用一个一维数组存储顶点信息，用一个二维数组A存储边的信息，二维数组中A[x][y]的值就表示一条边，如果设为1就是存在x到y的边，否则就不存在。
邻接表：用一个一维数组保存顶点信息，每个顶点后跟一个链表，用来保存与该顶点相连接的顶点。
对于数据不是很多，用邻接矩阵表示方法不错，但是当数据较多且稀疏时邻接矩阵需要的数组空间太大了，用邻接表更为合适。

广度优先搜索

广度优先搜索是一种较为简单的图搜索方法，首先从一个顶点V出发，找出与V相连的所有顶点，再依次对这些顶点进行相同的操作，找出未被访问的与之相邻的顶点，从V开始，由尽到远一层一层进行搜索，直到所有顶点访问完毕。可以发现这个搜索的顺序并不是唯一的，从不同的顶点开始可以有不同的顺序。

　　　　　　　　　
图(f)采用广义优先搜索遍历以V0为出发点的顶点序列为：V0，V1，V3，V4，V2，V6，V8，V5，V7
实现基本思想：首先获取第一个顶点，然后把所有与之相连的顶点放入队列中，当队列不为空时，每次从队列头中取出一个顶点，再把与该顶点相连的顶点放入队列尾部，已经在队列中的顶点不再进行放入。这样每次从队列中取出的顶点就是按照广度优先搜索的顺序输出的。

 //BFS
int main()
{
  int node[5]= {0};//保存节点已访问标志,假设节点个数为5
  int side[5][5] = {0, 1, 0, 1, 1, 
                    1, 0, 1, 1, 0, 
                    0, 1, 0, 1, 0, 
                    1, 1, 0, 0, 0, 
                    1, 0, 1, 0, 0};//邻接矩阵
  queue<int> qn;   //保存节点队列
  vector<int> out;  //输出遍历顺序
  qn.push(0);node[0] = 1;   //初始化第一个节点
  while (!qn.empty())
  {
    int i = qn.front();
    qn.pop();
    out.push_back(i);
    for(int j=0;j<5;j++) 
    {
      if(side[i][j] == 1 && node[j] == 0) 
      {
        qn.push(j);
        node[j] = 1;
      }
    }
  }
    for(int i=0; i<5;i++)  //输出遍历节点顺序
        cout << out[i] << " ";
  return 0;
}

广度优先搜索，图的遍历

深度优先搜索

深度优先搜索是从一个顶点开始Ｖ，搜索与之连接的一个顶点Ｗ，再搜索与Ｗ连接的一个顶点，直到末尾还没有搜索到节点，返回上一节点继续搜索，每次访问过的节点不再进行第二次访问。如上图ｆ中需要找v6，则首先从v0开始，按照路径v1->v2->v5没找到，返回v1，v1-v4-v6，搜索到结果返回。
实现遍历思想：从第一个顶点开始，按照顺序对与之相连的顶点进行深度搜索，每访问一个顶点，将之记录后续不再访问，直到访问完所有顶点，一般采用递归方式。

//DFS  非递归方式
void dfs2(int (*side)[5], vector<int>& out, int i)
{
    int node[5]= {0};//保存节点已访问标志,个数为5
    stack<int> st;
    node[i] = 1;
    out.push_back(i);
    st.push(i);
    while(!st.empty())
    {
        int i = st.top();
        int j;
        for(j=0; j<5; j++)
        {
            if(side[i][j] == 1 && node[j] == 0)
            {
                st.push(j);
                out.push_back(j);
                node[j] = 1;
                break;
            }
        }
        if(j == 5)    //只当节点没有后续节点后才出栈
            st.pop();
    }
}

//DFS 递归方式
void dfs(int (*side)[5], int* node, vector<int>& out, int i)
{
  out.push_back(i);
  node[i] = 1;
  for(int j=0; j<5; j++)
  {
      if(side[i][j] == 1 && node[j] == 0)
        dfs(side,node,out,j);
  }
}
int main()
{
  int node[5]= {0};//保存节点已访问标志,节点个数为5
  int side[5][5] = {0, 1, 0, 1, 1, 
                    1, 0, 1, 1, 0, 
                    0, 1, 0, 1, 0, 
                    1, 1, 0, 0, 0, 
                    1, 0, 1, 0, 0};//邻接矩阵
  vector<int> out; 
  dfs(side,node,out,0);
  //dfs2(side,out,0);
  for(int i=0; i<out.size();i++)  //输出遍历节点顺序
      cout << out[i] << " ";
  return 0;
}

深度优先算法，图的遍历

最短路径算法

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。注意该算法要求图中不存在负权边。
主要思想：
将顶点集合V分成两个部分，S和T，S中保存已经求出最短路径的顶点，T中为剩余的顶点。将T中的顶点依次放入S中，但是要保证从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度，每一个顶点对应一个路径值。其中S中顶点对于路径值为从V0到此顶点的长度；T中顶点对应路径值为从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度。
下面为有5个顶点的图实现的最短路径算法

const int N = 10000;  //不要用INT_MAX,容易溢出
void dijkstra(int (*side)[5], int *node, int *len, int *path)
{
  node[0] = 1;   //第一个点加入S集
  for(int i=0; i<5; i++)//把到第一个顶点可知的路径长度填入len，不知为N
  {
    if(side[0][i] != N )
    {
      len[i] = side[0][i];
      path[i] = 0;
    }
    else
    {
      len[i] = N;
      path[i] = -1;
    }
  }

  for(int j=1; j<5; j++)  //有n个顶点，循环n-1次，每次将一个顶点加入集合S
  {
    int nid;   //节点号
    int lentmp = N;
    for(int k=0; k<5; k++)    //找出集合T中到顶点v0距离最小的顶点
    {
      if(node[k] == 0 && len[k] < lentmp)
      {
        lentmp = len[k];
        nid = k;
      }
    }
    node[nid] = 1;  //将找到的点选出到S集
    for(int n=0; n<5; n++) //S集中增加了顶点后，对T中每一个顶点到v0的距离进行更新
    {
      if(node[n] == 0 && (lentmp + side[nid][n]) < len[n])
      {
        len[n] = lentmp + side[nid][n];
        path[n] = nid;    //更新，保存顶点前面的一个顶点
      }
    }
  }
}

//由于path中保存的是当前顶点的前一个顶点，因此循环用栈将其顺序填入再输出
void Path(int *path,int v)   //打印顶点v的最短路径 
{
    stack<int> s;   
    while(v!=0)
    {
        s.push(v);
        v=path[v];
    }
    s.push(v);
    while(!s.empty())
    {
        cout<<s.top()<<" ";
        s.pop();
    }
    cout << endl;
} 

int main()
{
  int node[5] = {0};//当值为1时表示对应的顶点在S集，0则在T集
  int side[5][5] = {N, 1, N, 3, 8, 
                    N, N, 3, N, N, 
                    N, N, N, N, 1, 
                    N, N, 2, N, 6, 
                    N, N, N, N, N};//邻接矩阵
  int len[5];   //保存起点到各顶点的路径距离，不知道时为N表示一个极大值，不能为0
  int path[5];  //path记录最短路径上从v0到i的前一个顶点，默认时为-1

  dijkstra(side,node,len,path);  //默认初始顶点为0
  for(int i=1; i<5; i++)
    Path(path,i);
  return 0;
}

Dijkstra算法（单源最短路径）

最小生成树

一个有 n 个结点的连通图的最小生成树是由图的所有顶点和边构成的树，且其总权值最小。 最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。一般是应用于无向图。一般思想为寻找最小的边连接到顶点，依次循环直到所有的顶点都被连接，不能有环路产生。