一、实验目的

1、复习图的逻辑结构、存储结构及基本操作；

2、掌握邻接矩阵、邻接表及图的创建、遍历；

3、了解图的应用。

二、实验内容

1、假设图中数据元素类型是字符型，请采用邻接矩阵或邻接表实现图的以下基本操作：

（1）构造图（包括有向图、有向网、无向图、无向网）；

（2）根据深度优先遍历图；

（3）根据广度优先遍历图。

2、给定一个无向图及两种颜色，请判定能否为这个无向图的相邻顶点着不同颜色。例如，对于有4个顶点（1、2、3、4）及3条边（(1,2)、(1,3)、(2,4)）的无向图，可以为相邻顶点着不同颜色；对于有4个顶点（1、2、3、4）及4条边（(1,2)、(1,3)、(1,4)、(2,4)）的无向图，不可以为相邻顶点着不同颜色。

3、给定若干村落及村落间可能建设成公路的若干道路成本，请计算：使每个村落都有公路连通的方案所需最低成本。

三、数据结构及算法分析与设计

1. 数据结构:

邻接矩阵int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]，用于表示图中顶点间的连接关系。

顶点表：char vexs[MAX_VERTEX_NUM]，存储图中所有顶点。

算法分析与设计：

1.图的创建（CreateGraph）：

输入：顶点数、边数以及边的连接信息。

处理：初始化邻接矩阵，填充顶点表，并根据输入的边信息更新邻接矩阵。

2.深度优先遍历（DFS）：

输入：图G，当前顶点v，访问标记数组visited。

处理：递归地访问未访问过的邻接顶点。

3.广度优先遍历（BFS）：

输入：图G，当前顶点v，访问标记数组visited。

处理：使用队列来存储待访问的顶点，按照广度优先的顺序访问顶点。

2. 数据结构:

邻接矩阵：int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]，用于表示图中顶点间的连接关系。

颜色数组：int color[MAX_VERTEX_NUM]，存储每个顶点的颜色信息。

算法分析与设计：

1.图的初始化（initGraph）：

输入：顶点数vexnum。

处理：初始化邻接矩阵和颜色数组。

2.添加边（addEdge）：

输入：边的起点start和终点end。

处理：在邻接矩阵中标记起点和终点之间的连接。

3.深度优先搜索着色（dfs）：

输入：当前顶点v。

处理：尝试为当前顶点着色，并递归地为相邻顶点着色。

4.检查是否可以着色（isBicolorable）：

输入：无。

处理：使用DFS尝试为所有未着色的顶点着色，并检查是否可能。

3. 数据结构:

边的数组：Edge edges[MAX_EDGES]，存储图中所有边的信息。

并查集：int parent[MAX_V]，用于表示并查集的父节点数组。

算法分析与设计：

1.Kruskal算法：

输入：边的数组edges，边的数量E，顶点的数量V。

处理：按照边的权重对边进行排序，然后逐个考虑每条边，如果加入这条边不会形成环，则将其加入到最小生成树中。

2.查找操作（find）：

输入：顶点编号x。

处理：递归地找到顶点x所在的集合的根节点。

3.合并操作（unionSet）：

输入：两个顶点编号x和y。

处理：将顶点x所在的集合合并到顶点y所在的集合中。

四、核心程序代码（给出必要注释）

1.

// 初始化图
void CreateGraph(MGraph *G, int isDirected) {
    int i, j;
    char v1, v2;
    G->vexnum = G->arcnum = 0;
    printf("输入顶点数和边数:\n");
    scanf("%d%d", &(G->vexnum), &(G->arcnum));
    for (i = 0; i < G->vexnum; i++) {
        printf("输入顶点:\n");
        scanf(" %c", &(G->vexs[i]));
        for (j = 0; j < G->vexnum; j++) {
            G->arc[i][j] = 0;
        }
    }
    printf("输入边(vi, vj):\n");
    for (i = 0; i < G->arcnum; i++) {
        scanf(" %c %c", &v1, &v2);
        int u = -1, v = -1;
        for (int m = 0; m < G->vexnum; m++) {
            if (G->vexs[m] == v1) {
                u = m;
                break;
            }
        }
        for (int n = 0; n < G->vexnum; n++) {
            if (G->vexs[n] == v2) {
                v = n;
                break;
            }
        }
        if (u != -1 && v != -1) {
            G->arc[u][v] = 1;
            if (!isDirected) {
                G->arc[v][u] = 1; // 无向图
            }
        }
    }
}

// 深度优先遍历辅助函数
void DFS(MGraph G, int v, int visited[]) {
    int i;
    visited[v] = TRUE;
    printf("%c ", G.vexs[v]);
    for (i = 0; i < G.vexnum; i++) {
        if (G.arc[v][i] == 1 && !visited[i]) {
            DFS(G, i, visited);
        }
    }
}

// 深度优先遍历图
void DFSTraverse(MGraph G) {
    int visited[MAX_VERTEX_NUM] = {FALSE};
    printf("深度优先遍历:\n");
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            DFS(G, i, visited);
        }
    }
    printf("\n");
}

// 广度优先遍历
void BFS(MGraph G, int v, int visited[]) {
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
    queue[rear++] = v;
    visited[v] = TRUE;
    while (front != rear) {
        v = queue[front++];
        printf("%c ", G.vexs[v]);
        for (int i = 0; i < G.vexnum; i++) {
            if (G.arc[v][i] == 1 && !visited[i]) {
                visited[i] = TRUE;
                queue[rear++] = i;
            }
        }
    }
}

// 广度优先遍历图
void BFSTraverse(MGraph G) {
    int visited[MAX_VERTEX_NUM] = {FALSE};
    printf("广度优先遍历:\n");
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            BFS(G, i, visited);
        }
    }
    printf("\n");
}

2.

// 尝试着色

bool dfs(Graph *G, int v) {

    for (int i = 1; i <= 2; i++) { // 只有两种颜色

        if (G->color[v] == 0) { // 如果当前顶点未着色

            G->color[v] = i; // 尝试着色

            bool colorable = true;

            for (int w = 0; w < G->vexnum; w++) { // 检查相邻顶点

                if (G->arc[v][w] && G->color[w] == G->color[v]) { // 如果相邻顶点着相同颜色

                    colorable = false;

                    break;

                }

            }

            if (colorable) {

                for (int w = 0; w < G->vexnum; w++) {

                    if (G->arc[v][w] && G->color[w] == 0 && !dfs(G, w)) { // 递归着色相邻顶点

                        colorable = false;

                        break;

                    }

                }

            }

            if (colorable) return true;

            G->color[v] = 0; // 回溯，撤销着色

        }

    }

    return false;

}

// 检查是否可以着色

bool isBicolorable(Graph *G) {

    for (int i = 0; i < G->vexnum; i++) {

        if (G->color[i] == 0 && !dfs(G, i)) { // 如果有未着色的顶点，尝试着色

            return false;

        }

    }

    return true;

}

3.

// 边的结构
typedef struct {
    int u, v; // 边的两个顶点
    int w; // 边的权重
} Edge;

// 并查集的结构
int parent[MAX_V];

// 查找并查集中的根节点
int find(int x) {
    if (x != parent[x]) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

// 合并两个集合
void unionSet(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootX] = rootY;
    }
}

// 比较函数，用于qsort
int compare(const void *a, const void *b) {
    return ((Edge *)a)->w - ((Edge *)b)->w;
}

// Kruskal算法

int kruskal(Edge *edges, int E, int V) {

    int i, j, minCost = 0;

    int edgeCount = 0;

    // 初始化并查集

    for (i = 0; i < V; i++) {

        parent[i] = i;

    }

    // 按照权重对边进行排序

    qsort(edges, E, sizeof(Edge), compare);

    // 遍历所有边

    for (i = 0; i < E; i++) {

        if (find(edges[i].u) != find(edges[i].v)) {

            unionSet(edges[i].u, edges[i].v);

            minCost += edges[i].w;

            edgeCount++;

            if (edgeCount == V - 1) {

                break;

            }

        }

    }

    return minCost;

}

五、测试及结果（给出测试用例及测试结果）

1.

 

2.

 

3.