1.基础数据结构
1.1 邻接矩阵
#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 65535
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
typedef struct {
VertexType vexs[MAXVEX]; /* 顶点表 */
EdgeType arc[MAXVEX][MAXVEX]; /* 邻接矩阵，可看作边表 */
int numVertices, numEdges; /* 图中当前的顶点数和边数 */
} MGraph;
1.2 邻接表
#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 65535
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
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 numVertices, numEdges; /* 图中当前顶点数和边数 */
} graphAdjList, *GraphAdjList;
2. 深度优先遍历
深度优先，是因为先从一个顶点出发，找到每个顶点在表中最近未被访问的顶点，继续递归，一条路走到黑，达到最深。
核心：
- 需要一个额外数组记录顶点是否被访问过。
- 不管是邻接矩阵还是邻接表，其实每个每个点位都被访问过。
- 每次递归返回(出栈)，会从上次的位置继续往后遍历，查找是否有未访问的顶点，继续深度优先遍历。
2.1 邻接矩阵实现
Boolean visited[MAXVEX]; // 是否访问过的标志数组
void DFS(MGraph G, int i) {
visited[i] = TRUE; // 先标记被访问过
printf("%c ", G.vexs[i]); // 打印被访问的顶点
for (int j = 0; j < G.numVertices; j++) // 遍历顶点i的邻接矩阵
if(G.arc[i][j] == 1 // 确认i和j顶点相连
&& !visited[j]) // 确认没有被访问
DFS(G, j);
}
void DFSTraverse(MGraph G) {
// 1.初始化
for (int i = 0; i < G.numVertices; i++)
visited[i] = FALSE;
// 2.遍历所有顶点，非连通图DFS完还有没有标记完，需要遍历确认
for (int i = 0; i < G.numVertices; i++)
if(!visited[i])
DFS(G, i);
}
2.2 邻接表实现
顶点数组的遍历和邻接矩阵一样，只是把邻接矩阵每行的数组遍历，改为了链表的遍历。
Boolean visited[MAXVEX]; // 是否访问过的标志数组
void DFS(GraphAdjList GL, int i) {
visited[i] = TRUE; // 先标记被访问过
printf("%c ", GL->adjList[i].data); // 打印被访问的顶点
EdgeNode *p = GL->adjList[i].firstEdge; // 链表的开头
while (p->next) {
if (!visited[p->adjvex]) { // 连接的顶点还没被访问过，邻接表里面都是相连的的顶点
DFS(GL, p->adjvex);
}
p = p->next;
}
}
void DFSTraverse(GraphAdjList GL) {
// 1.初始化
for (int i = 0; i < GL->numVertices; i++)
visited[i] = FALSE;
// 2.遍历所有顶点，非连通图DFS完还有没有标记完，需要遍历确认
for (int i = 0; i < GL->numVertices; i++) {
if(!visited[i])
DFS(GL, i);
}
}
3. 广度优先遍历
广度优先，是因为先从一个顶点出发，找到每个顶点相连接的未访问顶点入队。有点每到一个顶点呼朋唤友的感觉。
核心：
- 需要一个额外数组记录顶点是否被访问过。
- 类似于树的层序遍历。
- 利用了队列数据结构作为辅助。
- 不管是邻接矩阵还是邻接表，其实每个每个点位都被访问过。
3.1 邻接矩阵实现
Boolean visited[MAXVEX]; /* 访问标志的数组 */
void BFSTraverse(MGraph G) {
// 1.初始化
for (int i = 0; i < G.numVertices; i++)
visited[i] = FALSE;
Queue queue;
InitQueue(&queue);
// 2.遍历所有顶点
int idx;
for (int i = 0; i < G.numVertices; i++) {
if (!visited[i]) { // 确认没有被访问
visited[i] = TRUE; // 先标记被访问过
printf("%c ", G.vexs[i]); // 打印被访问的顶点
EnQueue(&queue, i); // 3.入队
while (!QueueEmpty(queue)) { // 队列中还有顶点
DeQueue(&queue, &idx); // 4.出队
for (int j = 0; j < G.numVertices; j++) { // 把出队元素相连的未访问顶点全部入队
if (G.arc[idx][j] == 1 // 确认i和j顶点相连
&& !visited[j]) { // 确认没有被访问
visited[j] = TRUE; // 先标记被访问过
printf("%c ", G.vexs[j]); // 打印被访问的顶点
EnQueue(&queue, j); // 入队
}
}
}
}
}
}
3.2 邻接表实现
同样，只是把邻接矩阵每行的遍历，替换为链表的遍历。
Boolean visited[MAXSIZE]; /* 访问标志的数组 */
void BFSTraverse(GraphAdjList GL) {
// 1.初始化
for (int i = 0; i < GL->numVertexes; i++)
visited[i] = FALSE;
Queue queue;
InitQueue(&queue);
// 2.遍历所有顶点
int idx;
EdgeNode *p;
for (int i = 0; i < GL->numVertexes; i++) {
if (!visited[i]) { // 确认没有被访问
visited[i] = TRUE; // 先标记被访问过
printf("%c ", GL->adjList[i].data); // 打印被访问的顶点
EnQueue(&queue, i); // 入队
while (!QueueEmpty(queue)) {
DeQueue(&queue, &idx); // 4.出队
p = GL->adjList[idx].firstEdge;
while (p) { // 把出队元素相连的未访问顶点全部入队
idx = p->adjvex; // 得到顶点的下标
if (!visited[idx]) { // 相连顶点未访问过
visited[idx] = TRUE; // 先标记被访问过
printf("%c ", GL->adjList[idx].data); // 打印被访问的顶点
EnQueue(&queue, idx); // 入队
}
p = p->next;
}
}
}
}
}
网友评论