目录

Data structure advanced training course notes and algorithm exercises 数据结构进阶实训课程笔记和算法练习

Source Code

1.图的定义

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V, E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

对于图的定义，需要注意的几个地方：

  • 线性表中把数据元素叫元素，树中将数据元素叫结点，图中将数据元素称之为顶点（Vertex）。
  • 线性表中可以没有数据元素，称之为空表。树中可以没有结点，叫做空树。但在图结构中，不允许没有顶点。在定义中，若V是顶点的集合，则强调顶点集合V有穷非空。
  • 线性表中，相邻的元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

1.1 各种图定义

  • 无向边：若顶点 v i v_i vi​到 v j v_j vj​之间的边没有方向，则称这条边为无向边（Edge），用无序偶对 ( v i , v j ) (v_i, v_j) (vi​,vj​)来表示。
  • 无向图：图中任意两顶点之间的边都是无向边。
  • 有向图：若从顶点 v i v_i vi​到 v j v_j vj​之间的边有方向，则称这条边为有向边（Edge），也称为弧（Arc）。用有序偶 < v 1 , v j > <v_1, v_j> <v1​,vj​>来表示， v i v_i vi​称为弧尾（Tail）， v j v_j vj​称为弧头（Head）。
  • 有向图：图中任意两个顶点之间的边都是有向边。
  • 在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。即不存在自环和重复边。
  • 无向完全图：在无向图中，如果任意两顶点之间都存在边。含有n个顶点的无向完全图有 n ∗ ( n − 1 ) 2 \frac{n*(n-1)}{2} 2n∗(n−1)​条边。
  • 有向完全图：在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧。含有n个顶点的有向完全图有 n ∗ ( n − 1 ) n*(n-1) n∗(n−1)条边。
  • 有很少条边或弧的图称为稀疏图反之称之为稠密图。
  • 有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权（Weight）。这种带权的图通常称为网（Network）。
  • 假设有两个图 G = ( V , { E } ) G=(V, \{E\}) G=(V,{E})和 G ‘ = ( V ‘ , { E ‘ } ) G^`=(V^`, \{E^`\}) G‘=(V‘,{E‘})，如果 V ‘ ⊆ V V^`\subseteq V V‘⊆V且 E ‘ ⊆ E E^`\subseteq E E‘⊆E，则称 G ‘ G^` G‘为 G G G的子图（Subgraph）。

1.2 连通图相关术语

在无向图G中，如果从顶点 v v v到顶点 v ‘ v^` v‘有路径，则称 v v v和 v ‘ v^` v‘是连通的。如果对于图中任意两个顶点 v i 、 v j ∈ E v_i、v_j \in E vi​、vj​∈E， v i v_i vi​和 v j v_j vj​都是连通的，则称G是连通图（Connected Graph）。

  • 无向图中的极大连通子图称为连通分量。

  • 在有向图G中，如果对于每一对 v i 、 v j ∈ V 、 v i ≠ v j v_i、v_j \in V、v_i\ne v_j vi​、vj​∈V、vi​​=vj​，从 v i v_i vi​到 v j v_j vj​和从 v j v_j vj​到 v i v_i vi​都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。

  • 一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。

  • 如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。

  • 一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。

2.图的存储结构

图的存储方式一般有两类，用边的集合方式有邻接矩阵，用链式方式有邻接链表、十字链表、邻接多重表、边集数组等。

2.1 邻接矩阵

图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

代码实现：

typedef char VertexType;           /* 顶点类型应由用户定义 */
typedef int EdgeType;              /* 边上的权值类型应由用户定义 */
#define MAXVEX 100 /* 最大顶点树，应由用户定义 */
#define INFINITY 65535 /* 用65535来代表无穷大 */
typedef struct{
  VertexType vexs[MAXVEX];         /* 顶点表 */
  EdgeType arc[MAXVEX][MAXVEX];    /* 邻接矩阵，可看作表 */
  int numVertexes, numEdges;       /* 图中当前的顶点数和边数 */
}MGraph;

无向网图的创建代码：

/* 建立无向图的邻接矩阵表示 */
void CreateMGraph(MGraph *G){
  int i, j, k, w;
  printf("输入顶点数和边数： \n");
  scanf("%d%d", &G->numVertexes, &G->numEdges);     /* 输入顶点数和边数 */
  for(i = 0; i<G->numVertexes; i++)                 /* 读入顶点信息，建立顶点表 */
    scanf(&G->vexs[i]);
  for(i = 0; i<G->numVertexes; i++)
    for(j = 0; j<G->numVertexes; j++)
      G->arc[i][j] = INFINITY;                      /* 邻接矩阵初始化 */
  for(k = 0; k<G->numEdges; k++){                   /* 读入numEdges条边，建立邻接矩阵 */
    printf("输入边(vi, vj)上的下标i，下标j和权w: \n");
    scanf("%d%d%d", &i, &j, &w);                    /* 输入边（vi, vj）上的权w */
    G->arc[i][j]=w;
    G->arc[j][i]=G->arc[i][j];                      /* 因为是无向图，矩阵对称 */
  }
}

从代码中可以得到，n个顶点和e条边的无向网图的创建，时间复杂度为 O ( n + n 2 + e ) O(n+n^2+e) O(n+n2+e)，其中对邻接矩阵Garc的初始化耗费了 O ( n 2 ) O(n^2) O(n2)的时间。

2.2 邻接表

数组与链表相结合的存储方法称为邻接表（Adjacency List）。图中顶点用一个一维数组存储，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。

代码实现：

typedef char VertexType;          /* 顶点类型由用户定义 */
typedef int EdgeType;             /* 边上的权值类型应由用户定义 */

typedef struct EdgeNode{          /* 边表结点 */
  int adjvex;                     /* 邻接点域，存储该顶点对应的下标 */
  EdgeType weight;                /* 用于存储权值，对于非网图可以不需要 */
  struct EdgeNode *next;          /* 链域，指向下一个邻接点 */
}EdgeNode;

typedef struct VertexNode{        /* 顶点表节点 */
  VertexType data;                /* 顶点域 */
  EdgeNode *firstedge;            /* 边表头指针 */
}VertexNode, AdjList[MAXVEX];

typedef struct{
  AdjList adjList;
  int numVertexes, numEdges;      /* 图中当前顶点数和边数 */
}GraphAdjList;

无向图的邻接表创建代码如下：

/* 建立图的邻接表结构 */
void CreateALGraph(GraphAdjList *G){
  int i, j, k;
  EdgeNode *e;
  printf("输入顶点数和边数： \n");
  scanf("%d%d", &G->numVertexes, &G->numEdges);  /* 输入顶点数和边数 */
  for(i=0; i<G->numVertexes; i++){               /* 读入顶点信息，建立顶点表 */
    scanf(&G->adjList[i].data);                  /* 输入顶点信息 */
    G->adjList[i].firstedge=NULL;                /* 将边表置为空表 */
  }
  for(k=0; k<G->numEdges; k++){                  /* 建立边表 */
    printf("输入边(vi, vj)上的顶点序号：\n");
    scanf("%d%d", &i, &j);                       /* 输入边(vi, vj)上的顶点序号 */
    e=(EdgeNode *)malloc(sizeof(EdgeNode));      /* 向内存申请空间 *//* 生成边表结点 */
    e->adjvex=j;                                 /* 邻接序号为j */
    e->next=G->adjList[i].firstedge;             /* 将e指针指向当前顶点指向的结点 */
    G->adjList[i].firstedge=e;                   /* 将当前顶点的指针指向e */
    
    e=(EdgeNode *)malloc(sizeof(EdgeNode));      /* 向内存申请空间 *//* 生成边表结点 */
    e->adjvex=i;                                 /* 邻接序号为i */
    e->next=G->adjList[j].firstedge;             /* 将e指针指向当前顶点指向的结点 */
    G->adjList[j].firstedge=e;                   /* 将当前顶点的指针指向e */ 
  }
}

这里采用头插法来建立两顶点间关系，对于n个顶点e条边来说，很容易得出算法的时间复杂度是 O ( n + e ) O(n+e) O(n+e)。

2.3 图的基本操作

  • 为实现遍历必须设置访问标志数组，以防止走回路或未访问到。
  • 图的遍历规律有两种：深度优先遍历DFS和广度优先遍历BFS。可用邻接矩阵和邻接表实现。
  • DFS算法是以递归技术为支持，BFS算法是以队列技术为支持。

2.4 图的应用

图的遍历算法是图应用的重要基础。
求解生成树、最小生成树、连通分量、拓扑排序、关键路径、单源最短路径及所有顶点之间的最短路径的重要算法应用。

3.建立图的邻接矩阵存储

3.1 有向图，无向图，有向网，无向网

#define MAX_VERtEX_NUM 20 //顶点的最大个数
#define VRType int //表示顶点之间的关系的变量类型
#define InfoType char //存储弧或者边额外信息的指针变量类型
#define VertexType int //图中顶点的数据类型

typedef enum{DG=1,DN=2,UDG=3,UDN=4}GraphKind;       //枚举图的 4 种类型

typedef struct {
  VRType adj;                         //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
  InfoType *info;                     //弧或边额外含有的信息指针
}ArcCell, AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];

typedef struct {
  VertexType vexs[MAX_VERtEX_NUM];        //存储图中顶点数据
  AdjMatrix arcs;                         //二维数组，记录顶点之间的关系
  int vexnum, arcnum;                      //记录图的顶点数和弧（边）数
  GraphKind kind;                         //记录图的种类
}MGraph;

//根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph * G,VertexType v){
int i=0;
//遍历一维数组，找到变量v
for (; i<G->vexnum; i++) {
  if (G->vexs[i]==v) {
      break;
  }
}
//如果找不到，输出提示语句，返回-1
if (i>G->vexnum) {
  printf("no such vertex.\n");
  return -1;
}
return i;
}
//构造有向图
void CreateDG(MGraph *G){
//输入图含有的顶点数和弧的个数
printf("Enter the number of vertices and edges: ");
scanf("%d%d",&(G->vexnum),&(G->arcnum));
//依次输入顶点本身的数据
printf("Please enter all vertices: ");
for (int i=0; i<G->vexnum; i++) {
  scanf("%d",&(G->vexs[i]));
}
//初始化二维矩阵，全部归0，指针指向NULL
for (int i=0; i<G->vexnum; i++) {
  for (int j=0; j<G->vexnum; j++) {
      G->arcs[i][j].adj=0;
      G->arcs[i][j].info=NULL;
  }
}
//在二维数组中添加弧的数据
for (int i=0; i<G->arcnum; i++) {
  int v1,v2;
  //输入弧头和弧尾
  printf("Enter arc head and arc tail: ");
  scanf("%d%d", &v1, &v2);
  //确定顶点位置
  int n=LocateVex(G, v1);
  int m=LocateVex(G, v2);
  //排除错误数据
  if (m==-1 ||n==-1) {
    printf("no this vertex\n");
    return;
  }
  //将正确的弧的数据加入二维数组
  G->arcs[n][m].adj=1;
}
}

//构造无向图
void CreateDN(MGraph *G){
printf("Enter the number of vertices and edges: ");
scanf("%d%d", &(G->vexnum),&(G->arcnum));
printf("Please enter all vertices: ");
for (int i=0; i<G->vexnum; i++) {
  scanf("%d", &(G->vexs[i]));
}
for (int i=0; i<G->vexnum; i++) {
  for (int j=0; j<G->vexnum; j++) {
      G->arcs[i][j].adj=0;
      G->arcs[i][j].info=NULL;
  }
}
for (int i=0; i<G->arcnum; i++) {
  int v1,v2;
  printf("Enter the subscript i and j on the side (vi, vj):");
  scanf("%d%d", &v1,&v2);
  int n=LocateVex(G, v1);
  int m=LocateVex(G, v2);
  if (m==-1 ||n==-1) {
      printf("no this vertex\n");
      return;
  }
  G->arcs[n][m].adj=1;
  G->arcs[m][n].adj=1;      //无向图的二阶矩阵沿主对角线对称
}
}

//构造有向网，和有向图不同的是二阶矩阵中存储的是权值。
void CreateUDG(MGraph *G){
printf("Enter the number of vertices and edges: ");
scanf("%d%d",&(G->vexnum),&(G->arcnum));
printf("Please enter all vertices: ");
for (int i=0; i<G->vexnum; i++) {
  scanf("%d",&(G->vexs[i]));
}
for (int i=0; i<G->vexnum; i++) {
  for (int j=0; j<G->vexnum; j++) {
    G->arcs[i][j].adj=0;
    G->arcs[i][j].info=NULL;
  }
}
for (int i=0; i<G->arcnum; i++) {
  int v1,v2,w;
  printf("Enter the arc head, arc tail and the weight of this edge: ");
  scanf("%d%d%d",&v1,&v2,&w);
  int n=LocateVex(G, v1);
  int m=LocateVex(G, v2);
  if (m==-1 ||n==-1) {
    printf("no this vertex\n");
    return;
  }
  G->arcs[n][m].adj=w;
}
}

//构造无向网。和无向图唯一的区别就是二阶矩阵中存储的是权值
void CreateUDN(MGraph* G){
printf("Enter the number of vertices and edges: ");
scanf("%d,%d",&(G->vexnum),&(G->arcnum));
printf("Please enter all vertices: ");
for (int i=0; i<G->vexnum; i++) {
  scanf("%d",&(G->vexs[i]));
}
for (int i=0; i<G->vexnum; i++) {
  for (int j=0; j<G->vexnum; j++) {
    G->arcs[i][j].adj=0;
    G->arcs[i][j].info=NULL;
  }
}
for (int i=0; i<G->arcnum; i++) {
  int v1,v2,w;
  printf("Enter the two vertices of the edge and the weight of this edge: ");
  scanf("%d%d%d",&v1,&v2,&w);
  int m=LocateVex(G, v1);
  int n=LocateVex(G, v2);
  if (m==-1 ||n==-1) {
      printf("no this vertex\n");
      return;
  }
  G->arcs[n][m].adj=w;
  G->arcs[m][n].adj=w;      //矩阵对称
}
}

4.邻接矩阵的深度和广度优先搜索

写出上述建立图的深度和广度优先搜索序列。
         示例
          v1
        /    \
       v2     v3
      /  \   /
    v4 -- v5
程序运行将以这个图作为输入。

4.1 算法设计思想

深度优先搜索

深度优先搜索的过程类似于树的先序遍历

所谓深度优先搜索，是从图中的一个顶点出发，每次遍历当前访问顶点的临界点，一直到访问的顶点没有未被访问过的临界点为止。然后采用依次回退的方式，查看来的路上每一个顶点是否有其它未被访问的临界点。访问完成后，判断图中的顶点是否已经全部遍历完成，如果没有，以未访问的顶点为起始点，重复上述过程。

深度优先搜索是一个不断回溯的过程。

广度优先搜索

广度优先搜索类似于树的层次遍历

从图中的某一顶点出发，遍历每一个顶点时，依次遍历其所有的邻接点，然后再从这些邻接点出发，同样依次访问它们的邻接点。按照此过程，直到图中所有被访问过的顶点的邻接点都被访问到。

最后还需要做的操作就是查看图中是否存在尚未被访问的顶点，若有，则以该顶点为起始点，重复上述遍历的过程。

4.2 源代码

typedef enum{false,true}bool;               //定义bool型常量
bool visited[MAX_VERtEX_NUM];               //设置全局数组，记录标记顶点是否被访问过

typedef struct Queue{                       //广度优先搜索的实现需要借助队列
  VertexType data;
  struct Queue * next;
}Queue;

int FirstAdjVex(MGraph G,int v){
//查找与数组下标为v的顶点之间有边的顶点，返回它在数组中的下标
for(int i = 0; i<G.vexnum; i++){
  if( G.arcs[v][i].adj ){
    return i;
  }
}
return -1;
}
int NextAdjVex(MGraph G,int v,int w){
//从前一个访问位置w的下一个位置开始，查找之间有边的顶点
for(int i = w+1; i<G.vexnum; i++){
  if(G.arcs[v][i].adj){
    return i;
  }
}
return -1;
}

void visitVex(MGraph G, int v){
printf("%d ",G.vexs[v]);
}

void DFS(MGraph G,int v){
visited[v] = true;//标记为true
visitVex( G,  v); //访问第v 个顶点
//从该顶点的第一个边开始，一直到最后一个边，对处于边另一端的顶点调用DFS函数
for(int w = FirstAdjVex(G,v); w>=0; w = NextAdjVex(G,v,w)){
  //如果该顶点的标记位false，证明未被访问，调用深度优先搜索函数
  if(!visited[w]){
    DFS(G,w);
  }
}
}

//深度优先搜索
void DFSTraverse(MGraph G){
int v;
//将用做标记的visit数组初始化为false
for( v = 0; v < G.vexnum; ++v){
  visited[v] = false;
}
//对于每个标记为false的顶点调用深度优先搜索函数
for( v = 0; v < G.vexnum; v++){
  //如果该顶点的标记位为false，则调用深度优先搜索函数
  if(!visited[v]){
    DFS( G, v);
  }
}
}

/* 队列操作 */
//初始化队列
void InitQueue(Queue ** Q){
(*Q)=(Queue*)malloc(sizeof(Queue));
(*Q)->next=NULL;
}
//顶点元素v进队列
void EnQueue(Queue **Q,VertexType v){
Queue * element=(Queue*)malloc(sizeof(Queue));
element->data=v;
element->next = NULL;
Queue * temp=(*Q);
while (temp->next!=NULL) {
  temp=temp->next;
}
temp->next=element;
}
//队头元素出队列
void DeQueue(Queue **Q,int *u){
(*u)=(*Q)->next->data;
(*Q)->next=(*Q)->next->next;
}
//判断队列是否为空
bool QueueEmpty(Queue *Q){
if (Q->next==NULL) {
  return true;
}
return false;
}

//广度优先搜索
void BFSTraverse(MGraph G){
int v;
//将用做标记的visit数组初始化为false
for( v = 0; v < G.vexnum; ++v){
  visited[v] = false;
}
//对于每个标记为false的顶点调用深度优先搜索函数
Queue * Q;
InitQueue(&Q);
for( v = 0; v < G.vexnum; v++){
  if(!visited[v]){
    visited[v]=true;
    visitVex(G, v);
    EnQueue(&Q, G.vexs[v]);
    while (!QueueEmpty(Q)) {
      int u;
      DeQueue(&Q, &u);
      u=LocateVex(&G, u);
      for (int w=FirstAdjVex(G, u); w>=0; w=NextAdjVex(G, u, w)) {
        if (!visited[w]) {
          visited[w]=true;
          visitVex(G, w);
          EnQueue(&Q, G.vexs[w]);
        }
      }
    }
  }
}
}

4.3 运行情况截图

以下演示的是图采用邻接矩阵存储结构的有向图和无向图的建立。

5.建立图的邻接表存储

5.1 有向图，无向图，有向网，无向网

#define MAX_VERTEX_NUM 20//最大顶点个数
#define VertexType int//顶点数据的类型
#define InfoType int//图中弧或者边包含的信息的类型

typedef enum{DG=1,DN=2,UDG=3,UDN=4}GraphKind;       //枚举图的 4 种类型
typedef enum{false,true}bool;               //定义bool型常量

typedef struct ArcNode{
  int adjvex;//邻接点在数组中的位置下标
  struct ArcNode * nextarc;//指向下一个邻接点的指针
  int weight;  //权值
  InfoType * info;//信息域
}ArcNode;

typedef struct VNode{
  VertexType data;//顶点的数据域
  ArcNode * firstarc;//指向邻接点的指针
}VNode, AdjList[MAX_VERTEX_NUM];//存储各链表头结点的数组

typedef struct {
  AdjList vertices;//图中顶点的数组
  int vexnum,arcnum;//记录图中顶点数和边或弧数
  GraphKind kind;//记录图的种类
}ALGraph;

/* 建立有向图图的邻接表结构 */
void CreateDGALGraph(ALGraph *G){
  int i, j, k;
  ArcNode *e;
  printf("Enter the number of vertices and edges: ");
  scanf("%d%d", &G->vexnum, &G->arcnum);  /* 输入顶点数和边数 */
  printf("Please enter all vertices: ");
  for(i=0; i<G->vexnum; i++){               /* 读入顶点信息，建立顶点表 */
    scanf("%d", &G->vertices[i].data);                  /* 输入顶点信息 */
    G->vertices[i].firstarc=NULL;                /* 将边表置为空表 */
  }
  for(k=0; k<G->arcnum; k++){                  /* 建立边表 */
    printf("Enter the vertex number on the edge (vi, vj): ");
    scanf("%d%d", &i, &j);                       /* 输入边(vi, vj)上的顶点序号 */
    e=(ArcNode *)malloc(sizeof(ArcNode));      /* 向内存申请空间 *//* 生成边表结点 */
    e->adjvex=j;                                 /* 邻接序号为j */
    /* 头插法 */
    e->nextarc=G->vertices[i].firstarc;             /* 将e指针指向当前顶点指向的结点 */
    G->vertices[i].firstarc=e;                   /* 将当前顶点的指针指向e */
  }
}

/* 建立无向图图的邻接表结构 */
void CreateDNALGraph(ALGraph *G){
  int i, j, k;
  ArcNode *e;
  printf("Enter the number of vertices and edges: ");
  scanf("%d%d", &G->vexnum, &G->arcnum);  /* 输入顶点数和边数 */
  printf("Please enter all vertices: ");
  for(i=0; i<G->vexnum; i++){               /* 读入顶点信息，建立顶点表 */
    scanf("%d", &G->vertices[i].data);                  /* 输入顶点信息 */
    G->vertices[i].firstarc=NULL;                /* 将边表置为空表 */
  }
  for(k=0; k<G->arcnum; k++){                  /* 建立边表 */
    printf("Enter the vertex number on the edge (vi, vj): ");
    scanf("%d%d", &i, &j);                       /* 输入边(vi, vj)上的顶点序号 */
    e=(ArcNode *)malloc(sizeof(ArcNode));      /* 向内存申请空间 *//* 生成边表结点 */
    e->adjvex=j;                                 /* 邻接序号为j */
    /* 头插法 */
    e->nextarc=G->vertices[i].firstarc;             /* 将e指针指向当前顶点指向的结点 */
    G->vertices[i].firstarc=e;                   /* 将当前顶点的指针指向e */
    
    e=(ArcNode *)malloc(sizeof(ArcNode));      /* 向内存申请空间 *//* 生成边表结点 */
    e->adjvex=i;                                 /* 邻接序号为i */
    e->nextarc=G->vertices[j].firstarc;             /* 将e指针指向当前顶点指向的结点 */
    G->vertices[j].firstarc=e;                   /* 将当前顶点的指针指向e */
  }
}

/* 建立有向网的邻接表结构 */
void CreateUDGALGraph(ALGraph *G){
  int i, j, k, w;
  ArcNode *e;
  printf("Enter the number of vertices and edges: ");
  scanf("%d%d", &G->vexnum, &G->arcnum);  /* 输入顶点数和边数 */
  printf("Please enter all vertices: ");
  for(i=0; i<G->vexnum; i++){               /* 读入顶点信息，建立顶点表 */
    scanf("%d", &G->vertices[i].data);                  /* 输入顶点信息 */
    G->vertices[i].firstarc=NULL;                /* 将边表置为空表 */
  }
  for(k=0; k<G->arcnum; k++){                  /* 建立边表 */
    printf("Enter the arc head, arc tail and the weight of this edge: ");
    scanf("%d%d%d", &i, &j, &w);                       /* 输入边(vi, vj)上的顶点序号 */
    e=(ArcNode *)malloc(sizeof(ArcNode));      /* 向内存申请空间 *//* 生成边表结点 */
    e->adjvex=j;                                 /* 邻接序号为j */
    e->weight=w;
    /* 头插法 */
    e->nextarc=G->vertices[i].firstarc;             /* 将e指针指向当前顶点指向的结点 */
    G->vertices[i].firstarc=e;                   /* 将当前顶点的指针指向e */
  }
}

/* 建立无向网的邻接表结构 */
void CreateUDNALGraph(ALGraph *G){
  int i, j, k, w;
  ArcNode *e;
  printf("Enter the number of vertices and edges: ");
  scanf("%d%d", &G->vexnum, &G->arcnum);  /* 输入顶点数和边数 */
  printf("Please enter all vertices: ");
  for(i=0; i<G->vexnum; i++){               /* 读入顶点信息，建立顶点表 */
    scanf("%d", &G->vertices[i].data);                  /* 输入顶点信息 */
    G->vertices[i].firstarc=NULL;                /* 将边表置为空表 */
  }
  for(k=0; k<G->arcnum; k++){                  /* 建立边表 */
    printf("Enter the arc head, arc tail and the weight of this edge: ");
    scanf("%d%d%d", &i, &j, &w);                       /* 输入边(vi, vj)上的顶点序号 */
    e=(ArcNode *)malloc(sizeof(ArcNode));      /* 向内存申请空间 *//* 生成边表结点 */
    e->adjvex=j;                                 /* 邻接序号为j */
    e->weight=w;
    /* 头插法 */
    e->nextarc=G->vertices[i].firstarc;             /* 将e指针指向当前顶点指向的结点 */
    G->vertices[i].firstarc=e;                   /* 将当前顶点的指针指向e */
    
    e=(ArcNode *)malloc(sizeof(ArcNode));      /* 向内存申请空间 *//* 生成边表结点 */
    e->adjvex=i;                                 /* 邻接序号为i */
    e->weight=w;
    e->nextarc=G->vertices[j].firstarc;             /* 将e指针指向当前顶点指向的结点 */
    G->vertices[j].firstarc=e;                   /* 将当前顶点的指针指向e */
  }
}

6.邻接表的广度和深度优先搜索

写出上述建立图的深度和广度优先搜索序列。
         示例
          v0
        /    \
       v1 --  v2
程序运行将以这个图作为输入。

6.1 源代码

//DFS遍历
void DFS(ALGraph *g,int i,int *visited){
  ArcNode *p;
  visited[i]=1;
  printf("%d ",g->vertices[i].data);
  p=g->vertices[i].firstarc;
  while( p ){
    if(!visited[p->adjvex]){
      DFS(g,p->adjvex,visited);
    }
    p=p->nextarc;
  }
}

void TraDFS(ALGraph *g){
  int i;
  int visited[MAX_VERTEX_NUM];
  for(i=0;i<g->vexnum;i++){
    visited[i]=0;
  }
  for(i=0;i<g->vexnum;i++){
    if(!visited[i]){
      DFS(g,i,visited);
    }
  }
}

//BFS遍历
void TraBFS(ALGraph *g){
  int i,j;
  Queue *q;
  int visited[MAX_VERTEX_NUM];
  for(i=0; i<g->vexnum; i++){
    visited[i]=0;
  }
  InitQueue(&q);
  for(i=0; i<g->vexnum;i++){
    if(!visited[i]){
      printf("%d ",g->vertices[i].data);
      visited[i]=1;
      EnQueue(&q, i);
      while(!QueueEmpty(q)){
        DeQueue(&q,&i);
        ArcNode *p = g->vertices[i].firstarc;
        while( p ){
          if(!visited[p->adjvex]){
            printf("%d ",g->vertices[p->adjvex].data);
            visited[p->adjvex]=1;
            EnQueue(&q,p->adjvex);
          }
          p=p->nextarc;
        }
      }
    }
  }
}

6.2 运行截图

以下演示的是图采用邻接表存储结构的无向图和有向网的建立。