基于“图”的算法训练

“图”的基本功训练

邻接矩阵的数据结构定义

#define  MAXV 6
typedef struct {
    int numVertices, numEdges;    // 顶点数和边数
    char VerticesList[MAXV];       // 顶点表（存储顶点数据）
    int edge[MAXV][MAXV];         // 邻接矩阵
} MGraph;

MGraph* createMGraph(){
    //初始化邻接矩阵
    MGraph *graph = (MGraph*)malloc(sizeof(MGraph));
    for(int i = 0; i < MAXV; i++)  	 // 初始化邻接矩阵（所有元素设为0） 
        for(int j = 0; j < MAXV; j++)
            graph->edge[i][j] = 0;
    
    graph->numEdges = 1;
    graph->numVertices = 2;
    graph->VerticesList[0] = 'a';
    graph->VerticesList[1] = 'b';
    graph->edge[0][1] = 1;

    return graph;
}

邻接表的数据结构定义

#define  MAXV 6

typedef struct EdgeNode {
    int index;              // 该边指向的顶点在数组中的索引
    struct EdgeNode *next;  // 指向下一条边的指针
    int weight;             // 边的权值
} EdgeNode;

typedef struct VertexNode {
    char data;              // 顶点的数据
    EdgeNode *first;        // 指向该顶点的第一条边
} VertexNode, VertexList[MAXV]; // VertexList是VertexNode的数组类型

typedef struct ALgraph {
    VertexList list;         // 顶点数组
    int numVertex, numEdge; // 顶点数和边数
} ALgraph;

void add(ALgraph* graph,int a, int b, int weight){
    EdgeNode* edge = (EdgeNode*)malloc(sizeof(EdgeNode));
    edge->index = b;
    edge->weight = weight;

    //头插法
    edge->next = graph->list[a].first;      //list[a]是结构体实例，
    graph->list[a].first = edge;
    
}
// graph：指向 ALgraph的指针，所以用 ->
// graph->list：是 VertexList类型，即 VertexNode数组
// graph->list[a]：数组的第 a个元素，是一个 VertexNode结构体（不是指针）
// graph->list[a].first：访问结构体的 first成员，所以用 .

ALgraph* createMGraph(){
    ALgraph *graph = (ALgraph*)malloc(sizeof(ALgraph));	
    for(int i = 0; i < MAXV; i++)	// 初始化所有顶点的first指针为NULL
    {
        graph->list[i].first = NULL;
    }
    graph->numEdge = 1;
    graph->numVertex = 2;
    graph->list[0].data = 'a';
    graph->list[0].data = 'b';

    add(graph,0,1,1);
    return graph;
}

“图”的真题训练

2021

1.设计思想

由题意知度为奇数的顶点个数只能为2个或0个，由于G是无向连通图，因此第i行非0元素的个数就是该顶点的度。

统计度为奇数的顶点，不为0或2返回0。若是的话返回1。

2.代码

#define MAXV 10

typedef struct{
    int numVertices,numEdges;
    char VerticesList[MAXV];
    int Edge[MAXV][MAXV];
}MGraph;

int IsExistEL(MGraph G){
    int cnt = 0;    //度为奇数的顶点个数
    int V = G.numVertices;  //顶点个数
    for(int i = 0; i < V; i++)
    {
        int tt = 0;   //统计顶点的度
        for(int j = 0; j < V; j++)
        {
            if(G.Edge[i][j]!=0)
                tt++;
        }
        if(tt%2!=0)
            cnt++;
    }
    if(cnt == 2 || cnt == 0)
        return 1;
    else
        return 0;
}

3.复杂度

时间复杂度O(V^2)，空间复杂度O(1)

4.改进

2023

1.设计思想

由于G是有向图，因此第i行存放的是顶点i的出度，第i列存放的是顶点的入度。

若出度大于入度，则输出顶点并计数。否则遍历下一顶点。

2.代码

#define MAXV 10

typedef struct{
    int numVertices,numEdges;
    char VerticesList[MAXV];
    int Edge[MAXV][MAXV];
}MGraph;

int printVertices(MGraph G)
{
    int kcnt = 0; //统计K顶点
    int v = G.numVertices;  //顶点数
    for(int i = 0; i < v; i++)
    {
        int indegree = 0,outdegree = 0;
        for(int j = 0; j < v; j++)
        {
            if(G.Edge[i][j]!=0)
            {
                outdegree++;
            }
        }
        for(int j = 0; j < v; j++)
        {
            if(G.Edge[j][i]!=0)
            {
                indegree++;
            }
        }
        if(outdegree>indegree)
        {
            kcnt++;
            printf("%c ",G.VerticesList[i]);
        }
    }
    return kcnt;
}

3.复杂度

O(v^2)，空间复杂度O(1)

4.改进

等价：

degree += G.Edge[i][j];	
if(G.Edge[i][j] != 0) {
    degree++;
}