228 lines
6.6 KiB
C++
228 lines
6.6 KiB
C++
#include <stdio.h>
|
||
#include <stdlib.h>
|
||
#include <string.h>
|
||
|
||
#define MaxSize 8
|
||
|
||
typedef struct ArcNode
|
||
{ // 【边结点】
|
||
int adjvex; // 该边所指向的顶点的位置
|
||
struct ArcNode *nextarc; // 指向下一条边的指针
|
||
} ArcNode;
|
||
|
||
typedef struct VNode
|
||
{ // 【表头结点】
|
||
char data[3]; // 顶点信息——每个顶点的数据是一个由3个字符组成的字符串（或字符数组）V0,V1
|
||
ArcNode *firstarc; // 指向第一条依附该顶点的边的指针
|
||
} VNode;
|
||
|
||
typedef struct
|
||
{
|
||
VNode vertices[MaxSize]; // 邻接表(vertices为数组名)
|
||
int vexnum, arcnum; // 图的当前顶点数和边数
|
||
} ALGragh;
|
||
|
||
// 1、构建图：参考P151算法6.2
|
||
void InitList(ALGragh &G, char a[][3])
|
||
{
|
||
int i, j;
|
||
for (i = 0; i < G.vexnum; i++)
|
||
{
|
||
for (j = 0; j < 3; j++)
|
||
// todo list //输入顶点值
|
||
G.vertices[i].data[j] = a[i][j];
|
||
// todo list //初始化表头结点的指针域为NULL
|
||
G.vertices[i].firstarc = NULL;
|
||
}
|
||
|
||
printf("请输入各边所依附的两个顶点的位置\n");
|
||
for (int k = 0; k < G.arcnum; k++)
|
||
{
|
||
scanf("%d %d", &i, &j);
|
||
// 生成一个新的边结点*p1:
|
||
ArcNode *p1 = (ArcNode *)malloc(sizeof(struct ArcNode));
|
||
// todo list 设此邻接点序号为j，并将新结点*p1插入顶点vi的边表头部(头插法)
|
||
p1->adjvex = j;
|
||
p1->nextarc = G.vertices[i].firstarc;
|
||
G.vertices[i].firstarc = p1;
|
||
|
||
// 生成另一个对称的新的边结点*p2：
|
||
ArcNode *p2 = (ArcNode *)malloc(sizeof(struct ArcNode));
|
||
// todo list 设此邻接点序号为i，并将新结点*p2插入顶点vj的边表头部(头插法)
|
||
p2->adjvex = i;
|
||
p2->nextarc = G.vertices[j].firstarc;
|
||
G.vertices[j].firstarc = p2;
|
||
}
|
||
}
|
||
|
||
// 2、输出邻接表
|
||
void PrintInf(ALGragh G)
|
||
{
|
||
int i;
|
||
ArcNode *p; // struct ArcNode* p;
|
||
printf("输出图的邻接表：\n");
|
||
for (i = 0; i < G.vexnum; i++)
|
||
{ // G.vexnum表示图中的顶点数量。
|
||
printf("%s ", G.vertices[i].data); // 打印当前顶点 i 的数据 (%s 被用于表示待插入的数据是字符串类型)
|
||
// for (// todo list) //for循环遍历当前顶点 i 的所有邻接顶点，并打印这些邻接顶点。
|
||
for (p = G.vertices[i].firstarc; p != NULL; p = p->nextarc)
|
||
printf("%d ", p->adjvex);
|
||
printf("\n");
|
||
}
|
||
}
|
||
|
||
// 3、对采用【邻接表】表示的图，做深度优先遍历：参考P157算法6.6
|
||
void DFS_AL(ALGragh G, int visited[], int v)
|
||
{
|
||
printf("%s ", G.vertices[v].data); // 访问第 v 个顶点
|
||
ArcNode *p;
|
||
int w;
|
||
visited[v] = 1;
|
||
|
||
// todo list //将 p 初始化为指向顶点 v 的第一个邻接点的指针
|
||
p = G.vertices[v].firstarc;
|
||
// todo list //while循环：对v未被访问的邻接顶点w递归调用DFSTraverse 函数；并寻找v相对于w的下一个邻接点
|
||
while (p != NULL)
|
||
{
|
||
w = p->adjvex;
|
||
if (!visited[w])
|
||
DFS_AL(G, visited, w);
|
||
p = p->nextarc;
|
||
}
|
||
}
|
||
|
||
// 4、深度优先遍历非连通图（也兼容连通图） ： 参考P156算法6.4 （可用于计算连通分量的个数，但需要增加count变量，如下算法5）
|
||
void DFSTraverse_AL(ALGragh G, int visited[])
|
||
{
|
||
int v;
|
||
for (v = 0; v < G.vexnum; v++) // 初始化标记数组,置为0
|
||
visited[v] = 0;
|
||
for (v = 0; v < G.vexnum; v++)
|
||
// todo list 如果有顶点没有被访问，那就以它为起点遍历所在的连通分量
|
||
if (!visited[v])
|
||
DFS_AL(G, visited, v);
|
||
printf("\n");
|
||
}
|
||
|
||
// 5、计算连通分量的个数
|
||
void Count(ALGragh G, int visited[])
|
||
{
|
||
int count = 0, v;
|
||
for (v = 0; v < G.vexnum; v++) // 初始化标记数组,置为0
|
||
visited[v] = 0;
|
||
for (v = 0; v < G.vexnum; v++)
|
||
// todo list 如果有顶点没有被访问，那就以它为起点遍历所在的连通分量，连通分量个数加一
|
||
if (!visited[v])
|
||
{
|
||
DFS_AL(G, visited, v);
|
||
count++;
|
||
}
|
||
printf("\n");
|
||
printf("连通分量个数:%d\n", count);
|
||
}
|
||
|
||
// 思考1
|
||
// 对采用【邻接矩阵】表示的图，做深度先遍历：
|
||
void DFS_AM(ALGragh G, int visited[], int v)
|
||
{
|
||
}
|
||
// 深度优先遍历非连通图
|
||
void DFSTraverse_AM(ALGragh G, int visited[], int v)
|
||
{
|
||
}
|
||
|
||
// 思考2
|
||
// 对采用【邻接表】表示的图，做广度先遍历：
|
||
void BFS_AL(ALGragh G, int visited[], int v)
|
||
{
|
||
}
|
||
// 广度优先遍历非连通图
|
||
void BFSTraverse_AL(ALGragh G, int visited[], int v)
|
||
{
|
||
}
|
||
|
||
// 思考3
|
||
// 对采用【邻接矩阵】表示的图，做广度先遍历：
|
||
void BFS_AM(ALGragh G, int visited[], int v)
|
||
{
|
||
}
|
||
// 广度优先遍历非连通图
|
||
void BFSTraverse_AM(ALGragh G, int visited[], int v)
|
||
{
|
||
}
|
||
|
||
// 6、判断有无路径可达
|
||
void Judge(ALGragh G, int visited[], int v, int u)
|
||
{
|
||
for (int i = 0; i < G.vexnum; i++)
|
||
visited[i] = 0;
|
||
// todo list 以v作为起点，做深度优先遍历图，在此过程中不断将所有相互连接的邻接结点的visited[u]更新为1
|
||
DFS_AL(G, visited, v);
|
||
if (visited[u] == 1)
|
||
{
|
||
printf("\n");
|
||
printf("V%d与V%d有路径可达!\n", v, u);
|
||
}
|
||
else
|
||
{
|
||
printf("\n");
|
||
printf("V%d与V%d无路径可达!\n", v, u);
|
||
}
|
||
}
|
||
|
||
int main()
|
||
{
|
||
int v, u; // j是边的数目,v、u为顶点位置
|
||
int choose = -1;
|
||
// a是一个二维字符数组，存储顶点信息(字符串还得保存结尾的空字符\0，因此列数需要设为3)
|
||
char a[MaxSize][3] = {"V0", "V1", "V2", "V3", "V4", "V5", "V6", "V7"};
|
||
int visited[MaxSize] = {0};
|
||
ALGragh G;
|
||
G.vexnum = MaxSize;
|
||
|
||
printf("*****************************************************\n");
|
||
printf("********** 实验八 *******\n");
|
||
printf("*****************************************************\n");
|
||
printf("********** 1.构建图 *******\n");
|
||
printf("********** 2.输出邻接表 *******\n");
|
||
printf("********** 3.深度优先遍历的结果 *******\n");
|
||
printf("********** 4.判断两个点之间是否有路径可达 *******\n");
|
||
printf("********** 5.输出连通分量的个数 *******\n");
|
||
printf("********** 0.退出 *******\n");
|
||
printf("*****************************************************\n");
|
||
while (choose)
|
||
{
|
||
printf("请输入你的选择项：");
|
||
scanf("%d", &choose);
|
||
switch (choose)
|
||
{
|
||
case 1:
|
||
printf("输入边数:");
|
||
scanf("%d", &G.arcnum);
|
||
InitList(G, a);
|
||
break;
|
||
case 2:
|
||
PrintInf(G);
|
||
break;
|
||
case 3:
|
||
printf("深度优先遍历结果：");
|
||
DFSTraverse_AL(G, visited); // 3 深度优先遍历图
|
||
// DFS_AL(G, visited,v); //如果是一个连通图，直接调用 DFS_AL也可以得到正确结果
|
||
printf("\n");
|
||
break;
|
||
case 4:
|
||
printf("输入要判断的两个点:");
|
||
scanf("%d %d", &v, &u);
|
||
Judge(G, visited, v, u);
|
||
break;
|
||
case 5:
|
||
Count(G, visited);
|
||
break;
|
||
case 0:
|
||
exit(0);
|
||
break;
|
||
}
|
||
}
|
||
|
||
return 0;
|
||
} |