数据结构进阶实训十二 图的存储结构
算法C36 分钟 读完 (大约 5343 个字)  0次访问

数据结构进阶实训十二 图的存储结构

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 各种图定义

  • 无向边：若顶点到之间的边没有方向，则称这条边为无向边（Edge），用无序偶对来表示。
  • 无向图：图中任意两顶点之间的边都是无向边。
  • 有向图：若从顶点到之间的边有方向，则称这条边为有向边（Edge），也称为弧（Arc）。用有序偶来表示，称为弧尾（Tail），称为弧头（Head）。
  • 有向图：图中任意两个顶点之间的边都是有向边。
  • 在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。即不存在自环和重复边。
  • 无向完全图：在无向图中，如果任意两顶点之间都存在边。含有n个顶点的无向完全图有条边。
  • 有向完全图：在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧。含有n个顶点的有向完全图有条边。
  • 有很少条边或弧的图称为稀疏图反之称之为稠密图。
  • 有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权（Weight）。这种带权的图通常称为网（Network）。
  • 假设有两个图和，如果且，则称为的子图（Subgraph）。

1.2 连通图相关术语

在无向图G中，如果从顶点到顶点有路径，则称和是连通的。如果对于图中任意两个顶点，和都是连通的，则称G是连通图（Connected Graph）。

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

  • 在有向图G中，如果对于每一对，从到和从到都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。

  • 一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。
  • 如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。
  • 一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。

2.图的存储结构

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

2.1 邻接矩阵

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

代码实现：

1
2
3
4
5
6
7
8
9
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;

无向网图的创建代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 建立无向图的邻接矩阵表示 */
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条边的无向网图的创建，时间复杂度为，其中对邻接矩阵Garc的初始化耗费了的时间。

2.2 邻接表

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

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* 建立图的邻接表结构 */
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条边来说，很容易得出算法的时间复杂度是。

2.3 图的基本操作

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

2.4 图的应用

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#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.邻接矩阵的深度和广度优先搜索

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

4.1 算法设计思想

深度优先搜索

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

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

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

广度优先搜索

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

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

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

4.2 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
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 运行情况截图

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

DS

5.建立图的邻接表存储

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#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.邻接表的广度和深度优先搜索

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

6.1 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//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 运行截图

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

DS

#

喜欢这篇文章？打赏一下作者吧

评论

关注我

链接

分类

标签

English1
主题1
前端1
原理4
基类1
复试1
搜索引擎1
数据库1
校招2
框架12
积累2
算法18
考研1
计算机基础7
课程5
配置7
面试题集2

订阅更新

×