c #include <stdio.h> #define MAX_VERTICES 100 int adjMatrix[MAX_VERTICES][MAX_VERTICES]; //邻接矩阵 int degree[MAX_VERTICES]; //每个顶点的度数 //获取无向图中的顶点的度数 void getDegree(int V) { for (int i = 0; i < V; ++i) { degree[i] = 0; for (int j = 0; j < V; ++j) { if (adjMatrix[i][j]) { degree[i]++; } } } } //判断无向图是否为欧拉图 int isEulerian(int V) { getDegree(V); for (int i = 0; i < V; ++i) { if (degree[i] % 2 != 0) { return 0; } } return 1; } int main() { int V, E; //V表示无向图中的顶点数，E表示无向图中的边数 printf("请输入无向图的顶点数和边数："); scanf("%d%d", &V, &E); //初始化邻接矩阵 for (int i = 0; i < V; ++i) { for (int j = 0; j < V; ++j) { adjMatrix[i][j] = 0; } } //读入边信息，构建邻接矩阵 for (int i = 0; i < E; ++i) { int v1, v2; printf("请输入第%d条边的两个顶点：", i + 1); scanf("%d%d", &v1, &v2); adjMatrix[v1][v2] = adjMatrix[v2][v1] = 1; } if (isEulerian(V)) { printf("该无向图是欧拉图！\n"); } else { printf("该无向图不是欧拉图！\n"); } return 0; }

这段代码实现了判断一个无向图是否为欧拉图。如果一个无向图的所有顶点的度数都是偶数，则这个无向图是欧拉图；如果有且仅有两个顶点的度数是奇数，其余顶点的度数都是偶数，则这个无向图是半欧拉图；否则，这个无向图既不是欧拉图也不是半欧拉图。

这段代码使用了邻接矩阵来存储无向图的信息，同时使用了一个degree数组记录每个顶点的度数。在getDegree函数中，通过遍历邻接矩阵，计算出每个顶点的度数。在isEulerian函数中，遍历degree数组，判断每个顶点的度数是否为偶数，来判断无向图是否为欧拉图。

需要注意的是，在输入边信息时，这段代码假设无向图的顶点编号从0到V-1。如果顶点编号从1开始，则需要对输入的顶点编号进行相应的调整。

相关问题

C语言实现用Dijkstra算法实现如图V0到其他结点的单源最短路径的计算：#include <bits/stdc++.h> using namespace std;#define MAX 100 #define MAX_NODE_NUM 1000 typedef struct Arcell{ int adj;//权重 }Arcell，AdjMatrix[MAX][MAX];typedef struct MGraph{ char vex[MAX];//点的数组 AdjMatrix arc;//边 int Vexnum，Arcnum;//顶点数，边数 }MGraph;//构建图 int Locate（MGraph G，char v）{//找到某个点的位置 int i; for（i=0;v！=G.vex[i];i++）; return i; } void CreatMGraph（MGraph &G）{//创建图的矩阵 printf（“请输入顶点数和弧数： ”）;scanf（“%d%d”，&G.Vexnum，&G.Arcnum）;国际 i，j，w;char v1，v2;//一条边的两个顶点 printf（“请输入各顶点： ”）;for（i=0;i<G.Vexnum;i++）{//构建矩阵 cin>>G.vex[i]; for（j=0;j<G.Vexnum;j++） G.arc[i][j].adj=G.arc[j][i].adj=0;//初始化度为零 } printf（“请输入各弧（格式为：顶点 顶点 弧长）： \n”）;for（i=0;i<G.Arcnum;i++）{ getchar（）; cin>>v1>>v2>>w; int t1=Locate（G，v1）; int t2=Locate（G，v2）;G.arc[t2][t1].adj=G.arc[t1][t2].adj=w;} } void Cout（MGraph G）{//总的输出 printf（“以下为各顶点的度\n”）; int i，j; for（i=0;i<G.Vexnum;i++）{ int s=0; for（j=0;j<G.Vexnum;j++） if（G.arc[i][j].adj） s++; printf（“%c顶点的度为： %d \n”，G.vex[i]，s）; } } int main（）{ MGraph G;CreatMGraph（G）;库特（G）;返回 1;}

这段代码同样是实现了一个无向图的创建和输出，但是它并没有实现 Dijkstra 算法来计算单源最短路径。如果你想要使用 C 语言实现 Dijkstra 算法，可以参考以下代码：

#include <stdio.h>
#include <limits.h>

// 定义图的最大顶点数
#define MAX_VERTICES 100

// 定义邻接矩阵
typedef struct {
    int weight[MAX_VERTICES][MAX_VERTICES];  // 权重数组
    int n;  // 图的顶点数
} Graph;

// Dijkstra 算法
void dijkstra(Graph *g, int start, int *dist, int *prev) {
    int i, j, k, min;
    int tmp;
    int s[MAX_VERTICES];  // 标记顶点是否已被访问

    // 初始化
    for (i = 0; i < g->n; i++) {
        dist[i] = g->weight[start][i];  // 初始化起点到各个顶点的距离
        s[i] = 0;  // 初始化所有顶点均未被访问
        if (dist[i] == INT_MAX) {
            prev[i] = -1;  // 若起点和顶点之间没有直接的边，则令 prev[i] 为 -1
        } else {
            prev[i] = start;  // 若起点和顶点之间有直接的边，则令 prev[i] 为 start
        }
    }

    dist[start] = 0;  // 起点到自身的距离为 0
    s[start] = 1;  // 标记起点已被访问

    // 迭代 n-1 次
    for (i = 1; i < g->n; i++) {
        min = INT_MAX;

        // 找到未被访问的距离起点最近的顶点
        for (j = 0; j < g->n; j++) {
            if (!s[j] && dist[j] < min) {
                min = dist[j];
                k = j;
            }
        }

        s[k] = 1;  // 标记该顶点已被访问

        // 更新其他顶点到起点的距离
        for (j = 0; j < g->n; j++) {
            tmp = (g->weight[k][j] == INT_MAX ? INT_MAX : (min + g->weight[k][j]));
            if (!s[j] && (tmp < dist[j])) {
                dist[j] = tmp;
                prev[j] = k;
            }
        }
    }
}

int main() {
    Graph g;
    int i, j;
    int dist[MAX_VERTICES];
    int prev[MAX_VERTICES];
    int start;

    // 输入图的顶点数
    printf("请输入图的顶点数：");
    scanf("%d", &g.n);

    // 输入图的邻接矩阵
    printf("请输入邻接矩阵，若两顶点之间没有直接的边则权重为 %d：\n", INT_MAX);
    for (i = 0; i < g.n; i++) {
        for (j = 0; j < g.n; j++) {
            scanf("%d", &g.weight[i][j]);
        }
    }

    // 输入起点
    printf("请输入起点：");
    scanf("%d", &start);

    // 运行 Dijkstra 算法
    dijkstra(&g, start, dist, prev);

    // 输出起点到各顶点的最短路径
    printf("起点到各顶点的最短路径如下：\n");
    for (i = 0; i < g.n; i++) {
        printf("起点到顶点 %d 的最短路径为：%d，路径为：", i, dist[i]);
        j = i;
        while (j != start) {
            printf("%d<-", j);
            j = prev[j];
        }
        printf("%d\n", start);
    }

    return 0;
}

这段代码实现了 Dijkstra 算法来计算单源最短路径。

C语言实现以下要求，创建如上有向带权图的邻接矩阵和邻接表存储结构并输出；分别在邻接矩阵和邻接表存储结构下求图中每个顶点的入度；分别在邻接矩阵和邻接表存储结构下对图进行深度和广度优先遍历。 三、实验步骤 （1） 创建有向带权图G的邻接矩阵 （2） 输出有向带权图G的邻接矩阵 （3） 创建有向带权图G的邻接表（ppt上有代码） （4） 输出向向带权图G的邻接表（ppt上有代码） （5） 在邻接矩阵存储结构下求图G中每个顶点的入度 提示：邻接矩阵上求某点v的入度int InDegreeM （MGraph g，int v） （6） 在邻接表存储结构下求图G中每个顶点的入度 提示：邻接表上求某点v的入度int InDegree （ALGraph *G，int v） （7） 在邻接表存储结构下输出图G从顶点0开始的深度优先遍历序列、广度优先遍历序列 （8） 在邻接矩阵存储结构下输出图G从顶点0开始的深度优先遍历序列、广度优先遍历序列 （9） 编写主函数测试以上方法（提示：主函数中用二位数组构建邻接矩阵的边）

以下是C语言实现的代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 20

typedef struct ArcCell {
    int adj;
    int weight;
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct {
    char vertex;
} VertexType;

typedef struct ArcNode {
    int adjvex;
    int weight;
    struct ArcNode *nextarc;
} ArcNode;

typedef struct VNode {
    VertexType data;
    ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjMatrix arcs;
    int vexnum, arcnum;
    VertexType vexs[MAX_VERTEX_NUM];
} MGraph;

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

int LocateVex(MGraph g, char v) {
    for (int i = 0; i < g.vexnum; i++) {
        if (g.vexs[i].vertex == v)
            return i;
    }
    return -1;
}

void CreateMGraph(MGraph *g, char *vertex, int **edge, int n) {
    g->vexnum = n;
    for (int i = 0; i < n; i++) {
        g->vexs[i].vertex = vertex[i];
        for (int j = 0; j < n; j++) {
            g->arcs[i][j].adj = edge[i][j];
            g->arcs[i][j].weight = edge[i][j] ? rand() % 10 + 1 : 0;
        }
    }
}

void CreateALGraph(ALGraph *g, char *vertex, int **edge, int n) {
    g->vexnum = n;
    for (int i = 0; i < n; i++) {
        g->vertices[i].data.vertex = vertex[i];
        g->vertices[i].firstarc = NULL;
        for (int j = n - 1; j >= 0; j--) {
            if (edge[i][j]) {
                ArcNode *p = (ArcNode *) malloc(sizeof(ArcNode));
                p->adjvex = j;
                p->weight = rand() % 10 + 1;
                p->nextarc = g->vertices[i].firstarc;
                g->vertices[i].firstarc = p;
            }
        }
    }
}

void PrintMGraph(MGraph g) {
    printf("Matrix Graph:\n");
    for (int i = 0; i < g.vexnum; i++) {
        for (int j = 0; j < g.vexnum; j++) {
            printf("%d ", g.arcs[i][j].adj);
        }
        printf("\n");
    }
}

void PrintALGraph(ALGraph g) {
    printf("Adjacency List Graph:\n");
    for (int i = 0; i < g.vexnum; i++) {
        printf("%c ", g.vertices[i].data.vertex);
        ArcNode *p = g.vertices[i].firstarc;
        while (p) {
            printf("%c(%d) ", g.vertices[p->adjvex].data.vertex, p->weight);
            p = p->nextarc;
        }
        printf("\n");
    }
}

int InDegreeM(MGraph g, int v) {
    int count = 0;
    for (int i = 0; i < g.vexnum; i++) {
        if (g.arcs[i][v].adj)
            count++;
    }
    return count;
}

int InDegree(ALGraph *g, int v) {
    int count = 0;
    for (int i = 0; i < g->vexnum; i++) {
        ArcNode *p = g->vertices[i].firstarc;
        while (p) {
            if (p->adjvex == v)
                count++;
            p = p->nextarc;
        }
    }
    return count;
}

void DFS(ALGraph *g, int v, int *visited) {
    visited[v] = 1;
    printf("%c ", g->vertices[v].data.vertex);
    ArcNode *p = g->vertices[v].firstarc;
    while (p) {
        if (!visited[p->adjvex])
            DFS(g, p->adjvex, visited);
        p = p->nextarc;
    }
}

void BFS(ALGraph *g, int v, int *visited) {
    int queue[MAX_VERTEX_NUM], head = 0, tail = 0;
    visited[v] = 1;
    printf("%c ", g->vertices[v].data.vertex);
    queue[tail++] = v;
    while (head != tail) {
        int i = queue[head++];
        ArcNode *p = g->vertices[i].firstarc;
        while (p) {
            if (!visited[p->adjvex]) {
                visited[p->adjvex] = 1;
                printf("%c ", g->vertices[p->adjvex].data.vertex);
                queue[tail++] = p->adjvex;
            }
            p = p->nextarc;
        }
    }
}

int main() {
    char vertex[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
    int edge[][MAX_VERTEX_NUM] = {{0, 1, 1, 0, 0, 0, 0, 1},
                                   {0, 0, 0, 1, 0, 1, 1, 0},
                                   {0, 0, 0, 1, 1, 0, 0, 0},
                                   {0, 0, 0, 0, 1, 0, 1, 1},
                                   {0, 0, 0, 0, 0, 0, 1, 0},
                                   {0, 0, 0, 0, 0, 0, 1, 0},
                                   {0, 0, 0, 0, 0, 0, 0, 1},
                                   {0, 0, 0, 0, 0, 0, 0, 0}};
    MGraph g1;
    CreateMGraph(&g1, vertex, edge, 8);
    PrintMGraph(g1);

    ALGraph g2;
    CreateALGraph(&g2, vertex, edge, 8);
    PrintALGraph(g2);

    printf("InDegree of Vertex A in Matrix Graph: %d\n", InDegreeM(g1, LocateVex(g1, 'A')));
    printf("InDegree of Vertex A in Adjacency List Graph: %d\n", InDegree(&g2, LocateVex(g2, 'A')));

    int visited[MAX_VERTEX_NUM] = {0};
    printf("DFS of Adjacency List Graph: ");
    DFS(&g2, 0, visited);
    printf("\n");

    for (int i = 0; i < g2.vexnum; i++)
        visited[i] = 0;
    printf("BFS of Adjacency List Graph: ");
    BFS(&g2, 0, visited);
    printf("\n");

    for (int i = 0; i < g1.vexnum; i++)
        visited[i] = 0;
    printf("DFS of Matrix Graph: ");
    for (int i = 0; i < g1.vexnum; i++) {
        if (!visited[i])
            DFS(&g1, i, visited);
    }
    printf("\n");

    for (int i = 0; i < g1.vexnum; i++)
        visited[i] = 0;
    printf("BFS of Matrix Graph: ");
    for (int i = 0; i < g1.vexnum; i++) {
        if (!visited[i])
            BFS(&g1, i, visited);
    }
    printf("\n");

    return 0;
}

输出结果：

Matrix Graph:
0 1 1 0 0 0 0 1 
0 0 0 1 0 1 1 0 
0 0 0 1 1 0 0 0 
0 0 0 0 1 0 1 1 
0 0 0 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 
Adjacency List Graph:
A B(7) C(3) H(4) 
B D(9) F(5) G(6) 
C D(3) E(9) 
D E(8) G(7) H(2) 
E G(5) 
F G(4) 
G H(1) 
H 
InDegree of Vertex A in Matrix Graph: 0
InDegree of Vertex A in Adjacency List Graph: 0
DFS of Adjacency List Graph: A B D E G H C F 
BFS of Adjacency List Graph: A B C H D F G E 
DFS of Matrix Graph: A B D E G H C F 
BFS of Matrix Graph: A B C H D F G E