#include#include //#include #define INFINITY INT_MAX // 无穷大 #define INITIAL_VALUE INFINITY // 邻接矩阵初始值 #define INITIAL_PRINT "∞" // 定义初始值的打印值 #define MaxVertexNum 20 // 邻接矩阵最大顶点数 #define OVERFLOW -2 // 空间分配失败、溢出 // 邻接矩阵 typedef char VertexType; typedef int EdgeType; typedef int InfoType; typedef struct { VertexType Vex[MaxVertexNum]; // 顶点表 EdgeType Edge[MaxVertexNum][MaxVertexNum]; // 边表（邻接矩阵） int vexnum, arcnum; // 顶点数、边数 }MGraph; // 邻接表 typedef struct ArcNode { // 边表结点 int adjvex; // 该弧所指向的顶点的位置(下标) struct ArcNode* next; // 指向下一条弧的指针 InfoType info; //权值 }ArcNode; typedef struct VNode { // 顶点表结点 VertexType data; // 顶点信息 ArcNode* first; // 指向第一条依附于此顶点的弧的指针 }VNode, AdjList[MaxVertexNum]; typedef struct { // 邻接表 AdjList vertices; // 一维数组的顶点表，各顶点结点内又放置了一个单链表的边表头指针 int vexnum, arcnum; // 图的顶点数和弧数 }ALGraph; // 返回图的邻接矩阵存储结构中值为v的顶点下标 int LocateVex(MGraph G, VertexType v); // 创建带权图（网）的邻接矩阵存储结构 flag为true时创建有向图，flag为false时创建无向图 void createMGraph(MGraph& G, bool flag); // 返回图的邻接表中值为v的顶点下标 int LocateVex(ALGraph G, VertexType v); // 创建带权图的邻接表存储结构 flag为true时创建有向图，为false时创建无向图 void createALGraph(ALGraph& G, bool flag); // 从图的邻接表表示转换为邻接矩阵表示 MGraph ALGraphToMGraph(ALGraph algraph); void printMGraph(MGraph G); // 定义访问的行为 void visit(VertexType name); int FirstNeighbor(MGraph G, int v); int NextNeighbor(MGraph G, int v, int w); // 广度优先搜索 void BFSTraverse(MGraph G); void BFS(MGraph G, int v); // 深度优先搜索 void DFSTraverse(MGraph G); void DFS(MGraph G, int v); // 返回图的邻接矩阵存储结构中值为v的顶点下标 int LocateVex(MGraph G, VertexType v) { for (int i = 0; i < G.vexnum; i++) { if (G.Vex[i] == v) return i; } return -1; } // 创建带权图（网）的邻接矩阵存储结构 flag为true时创建有向图，flag为false时创建无向图 void createMGraph(MGraph& G, bool flag) { scanf("%d %d", &G.vexnum, &G.arcnum); // 首先输入顶点数和边数 // 输入各顶点字母 for (int i = 0; i < G.vexnum; i++) scanf(" %c", &G.Vex[i]); // 初始化邻接矩阵 for (int i = 0; i < G.vexnum; i++) { for (int j = 0; j < G.vexnum; j++) { G.Edge[i][j] = INITIAL_VALUE; } } // 构造邻接矩阵 for (int k = 0; k < G.arcnum; k++) { VertexType v1, v2; // 顶点 EdgeType w; // 权值 scanf(" %c %c %d", &v1, &v2, &w); // 输入一条边及其权值 // 定位v1和v2在邻接矩阵中的位置 int i = LocateVex(G, v1), j = LocateVex(G, v2); G.Edge[i][j] = w; if (flag == false) // 若创建无向图，则对称位置也设置为此值 G.Edge[j][i] = w; } } // 返回图的邻接表中值为v的顶点下标 int LocateVex(ALGraph G, VertexType v) { for (int i = 0; i < G.vexnum; i++) { if (G.vertices[i].data == v) return i; } return -1; } // 创建带权图的邻接表存储结构 flag为true时创建有向图，为false时创建无向图 void createALGraph(ALGraph& G, bool flag) { scanf("%d %d", &G.vexnum, &G.arcnum); // 首先输入顶点数和边数 // 输入各顶点字母，构造表头向量 for (int i = 0; i < G.vexnum; i++) { scanf(" %c", &G.vertices[i].data); G.vertices[i].first = NULL; // 初始化边表头指针 } // 构造边表 for (int k = 0; k < G.arcnum; k++) { VertexType v1, v2; InfoType info; scanf(" %c %c %d", &v1, &v2, &info); // 输入一条边及其权值 int i = LocateVex(G, v1), j = LocateVex(G, v2); ArcNode* p; if (!(p = (ArcNode*)malloc(sizeof(ArcNode)))) exit(OVERFLOW); p->adjvex = j; p->info = info; // 采用头插法 p->next = G.vertices[i].first; G.vertices[i].first = p; if (flag == false) { // 若为无向图，则在另一个顶点处也加入该边 ArcNode* q; if (!(q = (ArcNode*)malloc(sizeof(ArcNode)))) exit(OVERFLOW); q->adjvex = i; q->info = info; // 采用头插法 q->next = G.vertices[j].first; G.vertices[j].first = q; } } } // 从图的邻接表表示转换为邻接矩阵表示 MGraph ALGraphToMGraph(ALGraph algraph) { // 先初始化邻接矩阵所有元素，然后遍历邻接表顶点表每一行，直接填写相应邻接矩阵元素值 MGraph res; res.vexnum = algraph.vexnum; res.arcnum = algraph.arcnum; // 初始化邻接表元素为0 for (int i = 0; i < res.vexnum; i++) { for (int j = 0; j < res.vexnum; j++) { res.Edge[i][j] = INITIAL_VALUE; } } for (int i = 0; i < res.vexnum; i++) { VNode vv = algraph.vertices[i]; res.Vex[i] = vv.data; // 顶点赋值 // 遍历边表 ArcNode* t = vv.first; while (t != NULL) { // 邻接矩阵赋值 int j = t->adjvex; res.Edge[i][j] = t->info; t = t->next; } } return res; } void printMGraph(MGraph G) { for (int i = 0; i < G.vexnum; i++) { for (int j = 0; j < G.vexnum; j++) { if (G.Edge[i][j] == INITIAL_VALUE) { printf("%st", INITIAL_PRINT); } else { printf("%dt", G.Edge[i][j]); } } printf("n"); } } bool visited[MaxVertexNum]; // 访问标记数组 void visit(VertexType name) { printf("%c ", name); } int FirstNeighbor(MGraph G, int v) { return NextNeighbor(G, v, -1); } int NextNeighbor(MGraph G, int v, int w) { for (int i = w+1; i < G.vexnum; i++) { if (G.Edge[v][i] != INITIAL_VALUE) { return i; } } return -1; // 返回小于0的值，说明找不到 } // 广度优先搜索 void BFSTraverse(MGraph G) { // 先初始化标记数组 for (int i = 0; i < G.vexnum; i++) visited[i] = false; for (int i = 0; i < G.vexnum; i++) { if (!visited[i]) BFS(G, i); } } // 非递归广度优先算法 void BFS(MGraph G, int v) { visit(G.Vex[v]); // 访问初始顶点 visited[v] = true; // 置该点为访问了 VertexType queue[MaxVertexNum]; int front = -1, rear = -1; // 辅助队列Q rear = (rear + 1) % MaxVertexNum; queue[rear] = v; // 顶点入队列 while (rear != front) { // 队列非空 front = (front + 1) % MaxVertexNum; v = queue[front];// 队头出队列 // 检测v的所有邻接点 for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) { // 查找失败时w = -1 if (!visited[w]) { visit(G.Vex[w]); visited[w] = true; rear = (rear + 1) % MaxVertexNum; queue[rear] = w; // 顶点入队列 } } } } // 深度优先搜索 void DFSTraverse(MGraph G) { // 初始化标记数组 for (int v = 0; v < G.vexnum; v++) { visited[v] = false; } for (int v = 0; v < G.vexnum; v++) { if (!visited[v]) DFS(G, v); } } // 递归算法 void DFS(MGraph G, int v) { visit(G.Vex[v]); visited[v] = true; // 检测v的所有邻接点 for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) { // 查找失败时w = -1 if (!visited[w]) { DFS(G, w); } } } int main(char* argv[]) { MGraph G; createMGraph(G, true); printMGraph(G); printf("广度优先搜索:n"); BFSTraverse(G); printf("n"); printf("深度优先搜索:n"); DFSTraverse(G); printf("n"); //ALGraph G2; //createALGraph(G2, true); //MGraph G = ALGraphToMGraph(G2); MGraph G2; createMGraph(G2, false); printMGraph(G2); printf("广度优先搜索:n"); BFSTraverse(G2); printf("n"); printf("深度优先搜索:n"); DFSTraverse(G2); printf("n"); printf("Finishn"); return 0; }
测试图
运行效果
