模仿： 

algorithm-journey/src/class059/Code01_CreateGraph.java at main · algorithmzuo/algorithm-journey

Code01_CreateGraph

 C语言：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAXN 11
#define MAXM 21// 邻接矩阵
int graph1[MAXN][MAXN];// 邻接表
typedef struct EdgeNode {int to;int weight;struct EdgeNode* next;
} EdgeNode;EdgeNode* graph2[MAXN];// 链式前向星
int head[MAXN];
int next[MAXM];
int to[MAXM];
int weight[MAXM];
int cnt;// 初始化图
void build(int n) {// 邻接矩阵初始化for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {graph1[i][j] = 0;}}// 邻接表初始化for (int i = 0; i <= n; i++) {graph2[i] = NULL;}// 链式前向星初始化cnt = 1;memset(head, 0, sizeof(head));
}// 链式前向星添加边
void addEdge(int u, int v, int w) {next[cnt] = head[u];to[cnt] = v;weight[cnt] = w;head[u] = cnt++;
}// 添加邻接表边
void addAdjListEdge(int u, int v, int w) {EdgeNode* newNode = (EdgeNode*)malloc(sizeof(EdgeNode));newNode->to = v;newNode->weight = w;newNode->next = graph2[u];graph2[u] = newNode;
}// 有向图构建
void directGraph(int edges[][3], int edgeCount) {// 邻接矩阵for (int i = 0; i < edgeCount; i++) {graph1[edges[i][0]][edges[i][1]] = edges[i][2];}// 邻接表for (int i = 0; i < edgeCount; i++) {addAdjListEdge(edges[i][0], edges[i][1], edges[i][2]);}// 链式前向星for (int i = 0; i < edgeCount; i++) {addEdge(edges[i][0], edges[i][1], edges[i][2]);}
}// 无向图构建
void undirectGraph(int edges[][3], int edgeCount) {// 邻接矩阵for (int i = 0; i < edgeCount; i++) {graph1[edges[i][0]][edges[i][1]] = edges[i][2];graph1[edges[i][1]][edges[i][0]] = edges[i][2];}// 邻接表for (int i = 0; i < edgeCount; i++) {addAdjListEdge(edges[i][0], edges[i][1], edges[i][2]);addAdjListEdge(edges[i][1], edges[i][0], edges[i][2]);}// 链式前向星for (int i = 0; i < edgeCount; i++) {addEdge(edges[i][0], edges[i][1], edges[i][2]);addEdge(edges[i][1], edges[i][0], edges[i][2]);}
}// 遍历图
void traversal(int n) {printf("邻接矩阵遍历 :\n");for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {printf("%d ", graph1[i][j]);}printf("\n");}printf("邻接表遍历 :\n");for (int i = 1; i <= n; i++) {printf("%d(邻居、边权) : ", i);EdgeNode* current = graph2[i];while (current != NULL) {printf("(%d,%d) ", current->to, current->weight);current = current->next;}printf("\n");}printf("链式前向星 :\n");for (int i = 1; i <= n; i++) {printf("%d(邻居、边权) : ", i);for (int ei = head[i]; ei > 0; ei = next[ei]) {printf("(%d,%d) ", to[ei], weight[ei]);}printf("\n");}
}// 释放邻接表内存
void freeAdjList(int n) {for (int i = 1; i <= n; i++) {EdgeNode* current = graph2[i];while (current != NULL) {EdgeNode* temp = current;current = current->next;free(temp);}}
}int main() {// 有向图示例int n1 = 4;int edges1[][3] = { {1, 3, 6}, {4, 3, 4}, {2, 4, 2}, {1, 2, 7}, {2, 3, 5}, {3, 1, 1} };build(n1);directGraph(edges1, 6);traversal(n1);freeAdjList(n1);printf("==============================\n");// 无向图示例int n2 = 5;int edges2[][3] = { {3, 5, 4}, {4, 1, 1}, {3, 4, 2}, {5, 2, 4}, {2, 3, 7}, {1, 5, 5}, {4, 2, 6} };build(n2);undirectGraph(edges2, 7);traversal(n2);freeAdjList(n2);return 0;
}

 C++版本：

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;const int MAXN = 11;
const int MAXM = 21;// 邻接矩阵
int graph1[MAXN][MAXN];// 邻接表
struct Edge {int to;int weight;
};vector<Edge> graph2[MAXN];// 链式前向星
int head[MAXN];
int next[MAXM];
int to[MAXM];
int weight[MAXM];
int cnt;// 初始化图
void build(int n) {// 邻接矩阵初始化for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {graph1[i][j] = 0;}}// 邻接表初始化for (int i = 0; i <= n; i++) {graph2[i].clear();}// 链式前向星初始化cnt = 1;memset(head, 0, sizeof(head));
}// 链式前向星添加边
void addEdge(int u, int v, int w) {next[cnt] = head[u];to[cnt] = v;weight[cnt] = w;head[u] = cnt++;
}// 有向图构建
void directGraph(vector<vector<int>> edges) {// 邻接矩阵for (auto edge : edges) {graph1[edge[0]][edge[1]] = edge[2];}// 邻接表for (auto edge : edges) {graph2[edge[0]].push_back({edge[1], edge[2]});}// 链式前向星for (auto edge : edges) {addEdge(edge[0], edge[1], edge[2]);}
}// 无向图构建
void undirectGraph(vector<vector<int>> edges) {// 邻接矩阵for (auto edge : edges) {graph1[edge[0]][edge[1]] = edge[2];graph1[edge[1]][edge[0]] = edge[2];}// 邻接表for (auto edge : edges) {graph2[edge[0]].push_back({edge[1], edge[2]});graph2[edge[1]].push_back({edge[0], edge[2]});}// 链式前向星for (auto edge : edges) {addEdge(edge[0], edge[1], edge[2]);addEdge(edge[1], edge[0], edge[2]);}
}// 遍历图
void traversal(int n) {cout << "邻接矩阵遍历 :" << endl;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cout << graph1[i][j] << " ";}cout << endl;}cout << "邻接表遍历 :" << endl;for (int i = 1; i <= n; i++) {cout << i << "(邻居、边权) : ";for (auto edge : graph2[i]) {cout << "(" << edge.to << "," << edge.weight << ") ";}cout << endl;}cout << "链式前向星 :" << endl;for (int i = 1; i <= n; i++) {cout << i << "(邻居、边权) : ";for (int ei = head[i]; ei > 0; ei = next[ei]) {cout << "(" << to[ei] << "," << weight[ei] << ") ";}cout << endl;}
}int main() {// 有向图示例int n1 = 4;vector<vector<int>> edges1 = { {1, 3, 6}, {4, 3, 4}, {2, 4, 2}, {1, 2, 7}, {2, 3, 5}, {3, 1, 1} };build(n1);directGraph(edges1);traversal(n1);cout << "==============================" << endl;// 无向图示例int n2 = 5;vector<vector<int>> edges2 = { {3, 5, 4}, {4, 1, 1}, {3, 4, 2}, {5, 2, 4}, {2, 3, 7}, {1, 5, 5}, {4, 2, 6} };build(n2);undirectGraph(edges2);traversal(n2);return 0;
}

 Code02_TopoSortDynamicLeetcode

C版本：

#include <stdio.h>
#include <stdlib.h>// 定义邻接表节点结构
typedef struct Node {int vertex;struct Node* next;
} Node;// 添加新节点到邻接表
Node* addNode(int v) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->vertex = v;newNode->next = NULL;return newNode;
}int* findOrder(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize, int* returnSize) {// 创建邻接表Node** graph = (Node**)malloc(numCourses * sizeof(Node*));for (int i = 0; i < numCourses; i++) {graph[i] = NULL;}// 创建入度表int* indegree = (int*)calloc(numCourses, sizeof(int));// 构建图和入度表for (int i = 0; i < prerequisitesSize; i++) {int ai = prerequisites[i][0];int bi = prerequisites[i][1];Node* newNode = addNode(ai);newNode->next = graph[bi];graph[bi] = newNode;indegree[ai]++;}// 创建队列int* queue = (int*)malloc(numCourses * sizeof(int));int l = 0, r = 0;// 将入度为0的节点入队for (int i = 0; i < numCourses; i++) {if (indegree[i] == 0) {queue[r++] = i;}}// 拓扑排序int cnt = 0;while (l < r) {int cur = queue[l++];cnt++;Node* temp = graph[cur];while (temp != NULL) {int next = temp->vertex;if (--indegree[next] == 0) {queue[r++] = next;}temp = temp->next;}}// 释放内存for (int i = 0; i < numCourses; i++) {Node* temp = graph[i];while (temp != NULL) {Node* next = temp->next;free(temp);temp = next;}}free(graph);free(indegree);// 返回结果if (cnt == numCourses) {*returnSize = numCourses;return queue;} else {*returnSize = 0;free(queue);return NULL;}
}

C++版本：

#include <vector>
#include <queue>
using namespace std;vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {// 创建邻接表vector<vector<int>> graph(numCourses);// 创建入度表vector<int> indegree(numCourses, 0);// 构建图和入度表for (const auto& edge : prerequisites) {int ai = edge[0];int bi = edge[1];graph[bi].push_back(ai);indegree[ai]++;}// 创建队列queue<int> q;// 将入度为0的节点入队for (int i = 0; i < numCourses; i++) {if (indegree[i] == 0) {q.push(i);}}// 拓扑排序vector<int> result;int cnt = 0;while (!q.empty()) {int cur = q.front();q.pop();result.push_back(cur);cnt++;for (int next : graph[cur]) {if (--indegree[next] == 0) {q.push(next);}}}// 返回结果if (cnt == numCourses) {return result;} else {return {};}
}