图的基础数据结构与遍历算法

快要面临实习了，最近打算专攻一些算法，这篇主要回顾一下图的基本算法，以及基本的的数据结构。

简介

本文主要回顾本科所学的关于图的一些数据结构和基本算法，图在实际问题中应用很广泛，是一种非常重要的数据结构。第一部分叙述图的定义以及基本表示形式，第二部分叙述关于图的一些常用算法。

图的描述

图的定义

图是顶点的非空集合和顶点之间边的非空集合组成的，常用**G(V,E)**表示，其中G表示一个图，V代表图G中顶点的集合，E表示图中边的集合。

图主要分为两类：一种是有向图，一种是无向图。其中有向图是顶点到顶点之间的边是有方向的，而无向图说明顶点间的边是不区分方向的。还有一种特殊的图称为网：顶点间的每条边有一个权重值。

图的基本表示

邻接矩阵

邻接矩阵可以非常简单明了的描述一个图。其主要思想是用一个二维数组描述图中顶点间的关系。它也可以很方便的描述网，其中无向图的邻接矩阵是沿对角线对称的。图的邻接矩阵的C语言描述如下所示：

#define MAXVEX 100            // 最大顶点数
#define MAXWEIGHT 65535       // 边的最大权重

typedef char VertextType;     // 顶点表示
typedef int EdgeTypde;        // 边的表示

typedef struct {
  VertextType vex[MAXVEX];
  EdgeTypde edge[MAXVEX][MAXVEX];
  int numVertex, numEdge;
} MGraph;
```  
#### **邻接表**
邻接矩阵的表示形式很容易造成空间的浪费，因为它把不存在边的信息也需要保存下来。而邻接表的表示方法可以解决这个问题，它使用数组和链表结合的存储方式。其中数组中保存图中的顶点数，链表则保存与该顶点关联的每一条边。其C语言的描述如下：
```c
typedef char VertextType;     // 顶点表示
typedef int EdgeTypde;        // 边的表示

/* 存储每个与该顶点相连接的顶点链表 */
typedef struct EdgeNode {
  int adjvex;                  // 存储该顶点在数组中的下标
  EdgeTypde weight;            // 这条边的权重
  struct EdgeNode * next;  
} EdgeNode;

typedef struct VertexNode {
  VertextType data;  
  EdgeNode * firstEdge;        // 与该点相连接的顶点链表中的第一个顶点。
} VertexNode, AdjList[MAXVEX];

typedef struct {
  AdjList adjList;              // 邻接表
  int numVertex, numEdge;       // 保存图的顶点数、边数
} GraphAdjList;

其中邻接表的初始化代码如下：

void create_graph( GraphAdjList * G ) {
  ...
  /* 初始化图的顶点数、变数 */
  G->numVertex = numVertex;
  G->numEdge = numEdge;

  /* 初始化每个顶点的值 */
  for( i = 0; i < G->numVertex; i++ ) {
    scanf(" %d\n", &G->adjList[i].data );
  }

  /*  初始化每个顶点的与之相连的顶点链表 */
  for( k = 0; k < G->numEdge; k++ ) {
    /* 得到每条边的两个顶点在数组中的下标 */
    scanf( "%d, %d\n", &vex1, &vex2 );
    /* 创建一个EdgeNode,加入这俩个顶点的链表中*/
    edge = (EdgeNode *) malloc( sizeof(sizeof(EdgeNode)) );
    edge->adjvex = vex2;         // 相连接点在数组中的下标
    edge->next = G->adjList[vex1].firstEdge;
    G->adjList[vex1].firstEdge = edge;

    edge = (EdgeNode *) malloc( sizeof(sizeof(EdgeNode)) );
    edge->adjvex = vex1;
    edge->next = G->adjList[vex2].firstEdge;
    G->adjList[vex2].firstEdge = edge;
  }
}

逆邻接表

在无向图的邻接表中，顶点V的度恰为顶点V对应的第i个链表中的节点数；

而在有向图中，第i个链表中的结点个数只是顶点V的出度，为求入度，必须遍历整个邻接表。有时，为了便于确定顶点的入度或以顶点V为头的弧，可以再建立一个有向图的逆邻接表，**即对每个顶点V建立一个链接以V为头的弧的链表。**其存储结构与邻接表相同。

十字链表

十字链表是有向图的一种存储方法，它实际上是邻接表与逆邻接表的结合。即把每一条边的边结点分别组织到以弧尾顶点为头结点的链表和以弧头顶点为头顶点的链表中。这里有向边称之为弧，弧头为：有向边的起始点；弧尾为：有向边的末尾节点。其C语言描述如下：

typedef struct EdgeNode {
  int vexTail, vexHead;            // 该有向边的弧头、弧尾在顶点表中位置
  struct EdgeNode * head, * tail;  // 分别连上弧头相同的边和弧尾相同的边
  InfoType info;                   // 该弧的附加信息
} EdgeNode;
typedef struct VertexNode {
  VertextType data;
  EdgeNode * firstIn, * firstOut;   // 分别指向该顶点的第一条弧头和弧尾
} VertexNode;
typedef struct {
  VertexNode XList[MAXVEX];
  int numVertex, numEdge;       // 保存图的顶点数、边数
} OLGraph;

十字链表的初始化比较麻烦，但实现不难。其过程如下：

void create_graph( OLGraph * G ) {
  ...
  /* 先初始化顶点数、边数 */
  G->numVertex = numVertex;
  G->numEdge = numEdge;

  /* 在把顶点表的数组初始化 */
  for( int i = 0; i < G->numVertex; i++ ) {
    scanf( "%d\n", &G->XList[i].data );

    G->XList[i].firstIn = NULL;
    G->XList[i].firstOut = NULL;
  }

  /* 然后输入有向边的信息，构造链表 */
  for( k = 0; k < G->numEdge; k++ ) {
    /* 得到每条边的两个顶点在数组中的下标 */
    scanf( "%d, %d\n", &vex1, &vex2 );
    /* 创建一个EdgeNode,加入这俩个顶点的链表中*/
    edge = (EdgeNode *) malloc( sizeof(sizeof(EdgeNode)) );
    edge->vexTail = vex1;                     // 该弧的头节点在数组中的下标
    edge->vexHead = vex2;                     // 弧尾节点在数组中的下标
    edge->head = G->XList[vex2].firstIn;      // 指向弧头相同的节点
    edge->tail = G->XList[vex1].firstOut;     // 指向弧尾相同的节点

    G->XList[vex1].firstOut = G->XList[vex2].firstin = p;   // 构成链表了
  }
}
```  
图的表示形式多种多样，要根据具体问题，选择合适的数据结构，下一部分叙述关于图的基本算法。
## **图的算法**
### **图的遍历**
图的遍历算法应用非常广泛，主要分为两种。一种是深度优先遍历(**DFS**)，一种是广度优先遍历(**BFS**)。主要区别在于遍历的时候，是先从该点的邻接点再次出发遍历(**DFS**)，还是从该点的邻接点集中取的下一个顶点出发遍历(**BFS**)。它们主要特点对每一个已访问的顶点进行标记。  
#### **深度优先遍历DFS**
根据邻接表或者邻接矩阵的下一个顶点出发遍历，根据一个访问标记数组，来判断是否对该点进行访问。其C语言描述如下：
````c
/*
 * 使用邻接矩阵进行DFS遍历操作
 */
void DFS( MGraph * G, int vex, int visit[] ) {
  visit[vex] = true;
  printf("%d : %d \n", vex, G->vex[vex] );

  for( int i = 0; i < G->numVertex; i++ ) {
    /* 这两条边没有相连或者已访问过 */
    if( G->edge[vex][i] == 0 || visit[i] == true ) continue;
    DFS( G, i, visit );
  }
}
/*
 * 使用邻接表进行DFS操作
 */
void DFS( GraphAdjList * G, int vex, int visit[] ) {
  visit[vex] = true;
  printf("%d : %d \n", vex, G->AdjList[vex].data );

  EdgeNode * edge = G->AdjList[vex]->firstEdge;
  while( edge ) {
    int index = edge->adjvex;
    if( visit[index] != true ) {
      DFS( G, index, visit );
    }
    edge = edge->next;
  }
}
/*
 * 使用十字链表进行DFS操作
 */
void DFS( OLGraph * G, int vex, int visit[] ) {
  visit[vex] = true;
  printf("%d : %d \n", vex, G->XList[vex].data );

  Edge * edge = G->XList[vex].firstOut;
  while( edge ) {
    if( visit[edge->vexHead] != true ) {
      DFS( G, edge->vexHead, visit );
    }
    edge = edge->tail;
  }
}
//void DFS_Traverse( MGraph * G )
//void DFS_Traverse( GraphAdjList * G )
void DFS_Traverse( OLGraph * G ) {
  int visit[G->numVertex];
  for( int i = 0; i < MAXVEX; i++ ) {
    visit[i] = false;
  }

  for( int i = 0; i < G->numVertex; i++ ) {
    if( visit[i] != true ) {
      DFS( G, i, visit );
    }
  }
}

广度优先遍历BFS

可以采用队列数据结构，就像二叉树的层次遍历，其C语言描述如下：

/*
 * 邻接矩阵的BFS遍历
 */
void BFS_Traverse( MGraph * G ) {
  int visit[G->numVertex];
  Queue Q;

  for( int i = 0; i < G->numVertex; i++ ) {
    visit[i] = false;
  }

  init_queue( &Q );

  for( int i = 0; i < G->numVertex; i++ ) {
    if( visit[i] == true ) continue;
    visit[i] = true;
    printf("%d : %c \n", G->vex[i] );

    in_queue( &Q, i );
    while( ! empty( &Q ) ) {
      int vex;
      out_queue( &Q, &vex );

      for( int j = 0; j < G->numVertex; j++ ) {
        if( G->vex[vex][j] == 0 || visit[j] == true ) continue;

        visit[j] = true;
        printf("%d : %c \n", G->vex[i] );
        in_queue( &Q, G->vex[j] );
      }
     }
   }
 }
 /*
  * 邻接表的BFS遍历
  */
void BFS_Traverse( GraphAdjList * G ) {
  int visit[G->numVertex];
  Queue Q;

  for( int i = 0; i < G->numVertex; i++ ) {
    visit[i] = false;
  }

  init_queue( &Q );
  for( int i = 0; i < G->numVertex; i++ ) {
    if( visit[i] == true ) continue;

    visit[i] = true;
    printf("%d : %d \n", G->adjList[i].data );

    in_queue( &Q, i );
    while( ! empty( &Q ) ) {
      int vex;
      out_queue( &Q, &vex );

      Edge * edge = G->adjList[i].firstEdge;
      while( edge ) {
        if( visit[edge->adjvex] != true ) {
          visit[edge->adjvex] = true;
          printf("%d : %d \n", G->adjList[i].data );
          in_queue( &Q, edge->adjvex );
        }
        edge = edge->next;
       }
     }
   }
 }
/*
 * 十字链表的BFS算法
 */
void BFS_Traverse( OLGraph * G ) {
 int visit[G->numVertex];
 Queue Q;

 for( int i = 0; i < G->numVertex; i++ ) {
   visit[i] = false;
 }

 init_queue( &Q );

 for( int i = 0; i < G->numVertex; i++ ) {
   if( visit[i] == true ) continue;

   visit[i] = true;
   printf( "%d : %d\n", G->XList[i].data );

   in_queue( &Q, i );
   while( ! empty( &Q ) ) {
     int vex;
     out_queue( &Q, &vex );

     EdgeNode * edge = G->XList[vex].firstOut;
     while( edge ) {
       if( visit[edge->vexHead] != true ) {
         visit[edge->vexHead] = true;
         printf( "%d : %d\n", G->XList[i].data );

         in_queue( &Q, edge->vexHead );
       }
       edge = edge->tail;
      }
    }
   }
 }

最后

上面是图的基本数据结构以及基本算法，在这个时候，整体梳理一下。下一篇在准备写图的一些常用算法，比如求最小生成树，最短路径等等…

上面参考了网上不少博主的文章，在此表示感谢^_

参考：

[1] 大话数据结构-图
[2] C语言中文网
[3] 有向图的十字链表操作
[4] 图的遍历之深度优先搜索和广度优先