图：
1.图的基本概念
2.图的存储和遍历
3.最小生成树
4.最短路径
5.拓扑排序和关键路径
一、图的基本概念
图的定义：不允许没有顶点，但边集可以为空
{无向图
{有向图：边==弧，弧头（有箭头），弧尾
{简单图：
图中不能有从顶点到其自身的边
同一条边在图中不能出现两次或者两次以上
{多重图
完全图：对于一个具有n个顶点的无向完全图，边的最大数量为n（n-1）/2
有向完全图 n（n-1）
路径：路径
路径长度
回路（环）
简单路径
简单回路
顶点的度
度与边的关系
连通图
连通分量：连通分量==子图；子图==连通图；
极大连通子图：再加一个点，它不再是连通图
强连通图
生成树：指含有图中全部顶点的极小连通子树
包含所有顶点，但只有足以构成一棵树的n-1条边
边的权和网
图的存储结构
邻接矩阵
邻接表
十字链表
邻接多重表
最小生成树
洛谷p3613题代码
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100005
#define MAX_Q 100005typedef struct {int item[MAX_N];int maxItem;
} Locker;
Locker lockers[MAX_N];
int n, q;
void store(int lockerIndex, int cellIndex, int item) {if (item == 0) {lockers[lockerIndex].item[cellIndex] = 0;} else {if (lockers[lockerIndex].maxItem < cellIndex + 1) {lockers[lockerIndex].maxItem = cellIndex + 1;}lockers[lockerIndex].item[cellIndex] = item;}
}
int query(int lockerIndex, int cellIndex) {return lockers[lockerIndex].item[cellIndex];
}
int main() {scanf("%d %d", &n, &q);for (int i = 0; i < n; i++) {lockers[i].maxItem = 0;for (int j = 0; j < MAX_N; j++) {lockers[i].item[j] = 0;}}for (int i = 0; i < q; i++) {int op, lockerIndex, cellIndex，item;scanf("%d", &op);if (op == 1) {scanf("%d %d %d", &lockerIndex, &cellIndex, &item);store(lockerIndex, cellIndex - 1, item); // Adjust for 0-based index} else if (op == 2) {scanf("%d %d", &lockerIndex, &cellIndex);if (lockers[lockerIndex].maxItem >= cellIndex) {printf("%d\n", query(lockerIndex, cellIndex - 1)); // Adjust for 0-based index} else {printf("0\n");}}}return 0;
}洛谷p1449代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#define MAX 100
int stack[MAX];
int top = -1;
void push(int value) {if (top >= MAX - 1) {printf("Stack underflow\n");exit(1);}stack[++top] = value;
}
int pop() {if (top < 0) {printf("Stack underflow\n");exit(1);}return stack[top--];
}
int is_operator(char ch) {return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}
int evaluate_postfix(char* expression) {int i = 0;while (expression[i] != '@') {if (isdigit(expression[i])) {int num = 0;while (isdigit(expression[i])) {num = num * 10 + (expression[i] - '0');i++;}push(num);}else if (expression[i] == '.') {i++;}else if (is_operator(expression[i])) {int operand2 = pop();int operand1 = pop();switch (expression[i]) {case'+':push(operand1 + operand2);break;case'-':push(operand1 - operand2);break;case'*':push(operand1 * operand2);break;case'/':push(operand1 / operand2);break;}i++;}else {i++;}}return pop();
}
int main() {char expression[MAX];fgets(expression, MAX, stdin);expression[strcspn(expression, "\n")] = 0;int result = evaluate_postfix(expression);printf("%d\n", result);return 0;
}