- 表示“多对多”的关系
-
包含
一组顶点：通常用V(Vertex)表示顶点集合
一组边：通常用E(Edge)表示边的集合
边是顶点对: (v,w) ∈ E,其中v，w ∈ v V——W
有向边<v,w> 表示从v指向w的边（单行线）V——>W
不考虑重边和回路 -
操作集：
Graph Create():建立并返回空图;
Graph InsertVertex(Graph G,Vertexv):将v插入G;
Graph InsertEdge (Graph G，Edge e):将e插入G;
void DFS (Graph G，Vertexv):从顶点v出发深度优先遍历图G;
void BFS (Graph G，Vertexv):从顶点v出发宽度优先遍历图G;
void ShortestPath(Graph G，Vertex v,int Dist[]):计算图G中顶点v到任意其他顶点的最短距离;
void MST(Graph G):计算图G的最小生成树;
常用术语
无向图： <v,w)> ∈ VR 必有<w,v> ∈ VR, 即VR是对称的，则以无序对(v,w)代替这两个有序对，此时图称为无向图。
有向图： <v,w)> ∈ VR， 从v——>w
完全图： 对于无向图，任意两个顶点都有边的图（有1/2n(n-1)条边的无向图）
有向完全图： 具有n(n-1)条弧的有向图
稀疏图： 有很少条边或弧(如e<nlogn)的图
稠密图： 跟稀疏图相反
连通: 如果从v到w存在一条(无向)路径，则称 V和w是连通的
路径: v到w的路径是一系列顶点{V，V1，V21... Vn/ W}的集合，其中任一对相邻的顶点间都有图中的边。路径的长度是路径中的边数(如果带权，则是所有边的权重和)。如果v到w之间的所有顶点都不同，则称简单路径
回路: 起点等于终点的路径
连通分量: 无向图的极大连通子图
极大顶点数:再加1个顶点就不连通了
极大边数:包含子图中所有顶点相连的所有边
强连通: 有向图中顶点v和w之间存在双向路径，则称V和w是强连通的
强连通图: 有向图中任意两顶点均强连通
强连通分量: 有同图的极大强连通子图
图的存储结构
1. 邻接矩阵表示法
-
问题：对于无向图的存储，怎么可以省一半的空间？
邻接矩阵 —— 有什么好处？
- 直观、简单、好理解
- 方便检查任意一对顶点间是否存在边
- 方便找任意顶点的所有“邻接点”（有边直接相连的顶点）
- 方便计算任一顶点的“度”（从该点发出的边数为“出度”，指向该点的边数为“入度”）
无向图：对应行（或列）非0元素的个数
有向图：对应行非0元素的个数是“出度”；对应列非0元素的个数是“入度”
- 邻接矩阵 —— 有什么不好？
- 浪费空间 —— 存稀疏图(点很多而边很少)有大量无效元素
对稠密图(特别是完全图)还是很合算的- 浪费时间 —— 统计稀疏图中一共有多少条边
#define MaxVertexNum 10
typedef struct GNode *PtrToGNode;
typedef int WeightType;
typedef char DataType;
struct GNode {
int Nv; //顶点数
int Ne; //边数
WeightType G[MaxVertexNum][MaxVertexNum];
DataType data[MaxVertexNum];
};
typedef PtrToGNode MGraph; //以邻接矩阵存储的图类型
typedef int Vertex;
MGraph CreateGraph(int vertexNum)
{
Vertex v,w;
MGraph graphRef;
graphRef = (MGraph)malloc(sizeof(struct GNode));
graphRef->Nv = vertexNum;
graphRef->Ne = 0;
for (v = 0; v<graphRef->Nv; v++)
for (w = 0; w<graphRef->Nv; w++)
graphRef->G[v][w] = 0;
return graphRef;
}
struct ENode {
Vertex v1,v2; // 有向边<V!,V2>
WeightType weight;// 权重
};
typedef struct ENode *PtrToENode;
typedef PtrToENode Edge;
void InsertEdge(MGraph graph, Edge e)
{
//插入边 <V1,V2>
graph->G[e->v1][e->v2] = e->weight;
//若是无向图，还要插入边 <V1,V2>
graph->G[e->v2][e->v1] = e->weight;
}
完整的创建一个MGraph
MGraph buildGraph()
{
MGraph graph;
Edge e;
Vertex v;
int Nv, i;
scanf("%d",&Nv);
graph = CreateGraph(Nv);
scanf("%d", &(graph->Ne));
if (graph->Ne != 0) {
e = (Edge)malloc(sizeof(struct ENode));
for (i = 0; i < graph->Ne; i++) {
scanf("%d %d %d",&e->v1, &e->v2, &e->weight);
InsertEdge(graph, e);
}
}
return graph;
}
2. 邻接表表示法
- 邻接表特点：
- 方便找任一顶点的所有“邻接点”
- 节约稀疏图的空间
需要N个头指针 + 2E个节点(每个结点至少2个)- 方便计算任一顶点的“度”
对无向图：是的
对有向图：只能计算“出度”；需要构造“逆邻接表”(存指向自己的边)来方便计算“入度”- 不方便计算任意一对顶点间是否存在边
#define MaxVertexNum 10
typedef int Vertex;
typedef int WeightType;
typedef char DataType;
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode {
Vertex adjV; //邻接点下标
WeightType weight; //边的权重
PtrToAdjVNode next;
};
typedef struct Vnode {
PtrToAdjVNode firstEdget;
DataType data; //存顶点的数据
}AdjList[MaxVertexNum];
struct GNode {
int Nv; //顶点数
int Ne; //边数
AdjList G; //邻接表
};
typedef struct GNode *PtrToGNode;
typedef PtrToGNode LGraph;
struct ENode {
Vertex v1,v2; // 有向边<V!,V2>
WeightType weight;// 权重
};
typedef struct ENode *PtrToENode;
typedef PtrToENode Edge;
LGraph CreateGraph(int vertexNum)
{
Vertex v,w;
LGraph graph;
graph = (LGraph)malloc(sizeof(struct GNode));
graph->Nv = vertexNum;
graph->Ne = 0;
for (v = 0; v < graph->Nv; v++)
graph->G[v].firstEdget = NULL;
return graph;
}
void InsertEdge(LGraph graph, Edge e)
{
PtrToAdjVNode newNode;
/************插入边 <v1, v2>***************/
newNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
newNode->adjV = e->v2;
newNode->weight = e->weight;
newNode->next = graph->G[e->v1].firstEdget;
graph->G[e->v1].firstEdget = newNode;
/************插入边 <v2, v1>***************/
newNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
newNode->adjV = e->v1;
newNode->weight = e->weight;
newNode->next = graph->G[e->v2].firstEdget;
graph->G[e->v2].firstEdget = newNode;
}
完整的创建一个MGraph
LGraph buildGraph()
{
LGraph graph;
Edge e;
Vertex v;
int Nv, i;
scanf("%d",&Nv);
graph = CreateGraph(Nv);
scanf("%d", &(graph->Ne));
if (graph->Ne != 0) {
e = (Edge)malloc(sizeof(struct ENode));
for (i = 0; i < graph->Ne; i++) {
scanf("%d %d %d",&e->v1, &e->v2, &e->weight);
InsertEdge(graph, e);
}
}
return graph;
}
图的遍历
1. 深度优先搜索(DFS)
#define MaxSize 10
int visited[MaxSize];
int adj[MaxSize][MaxSize] = {0};
int n;
int top = -1;
int stack[MaxSize];
void initAdj()
{
n = 5;
int add[5][5] = {
{0, 1, 0, 1, 0},
{1, 0, 1, 0, 1},
{0, 1, 0, 1, 1},
{1, 0, 1, 0, 0},
{0, 1, 1, 0, 0}
};
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
adj[i][j] = add[i][j];
}
}
for (int i = 0; i < n; i++) {
visited[i] = 0;
printf("\n");
for (int j = 0; j < n; j++) {
printf("%d ",adj[i][j]);
}
}
printf("\n");
}
void push(int item) {
if(top >= MaxSize-1) {
printf("\nStack Overflow.");
}
else {
stack[++top] = item;
}
}
int pop() {
if(top < 0) {
printf("\nStack Underflow.");
return -1;
}
else {
return stack[top--];
}
}
非递归法
void dfs(int v) {
int i;
push(v);
while(top >= 0) {
v = pop();
if(visited[v] == 0) {
printf("%d ", v+1);
visited[v] = 1;
}
for(i = 0; i < n; i++) {
if(adj[v][i] == 1 && visited[i] == 0) {
push(i);
}
}
}
printf("\n");
}
递归法
void dfsRecursion(int v)
{
visited[v] = 1;
printf("%d ", v+1);
for(int i = 0; i < n; i++) {
if(adj[v][i] == 1 && visited[i] == 0) {
dfsRecursion(i);
}
}
}
递归法和非递归法访问节点顺序不同
若有N个顶点、E条边，时间复杂度是
- 用邻接表存储图，有O(N+E)
- 用邻接矩阵存储图，有O(N2)
2. 广度优先搜索(BFS)
typedef int ElementType;
struct QNode{
ElementType data[MaxSize];
int front;
int rear;
};
typedef struct QNode* Queue;
void EnQueue(Queue ptrQ, ElementType item)
{
if((ptrQ->rear + 1)%MaxSize == ptrQ->front){
printf("队列已满");
return;
}
ptrQ->rear = (ptrQ->rear + 1)%MaxSize;
ptrQ->data[ptrQ->rear] = item;
}
ElementType DeQueue(Queue ptrQ)
{
if(ptrQ->front == ptrQ->rear){
printf("队列空");
return -1;
}
ptrQ->front = (ptrQ->front + 1)%MaxSize;
return ptrQ->data[ptrQ->front];
}
bool IsEmpty(Queue ptrQ)
{
return ptrQ->front == ptrQ->rear;
}
void BFS(int v)
{
struct QNode qNode;
qNode.front = qNode.rear = 0;
Queue ptrQ = &qNode;
visited[v] = 1;
EnQueue(ptrQ, v);
while (!IsEmpty(ptrQ)) {
v = DeQueue(ptrQ);
printf("%d ",v + 1);
for(int i = 0; i < n; i++) {
if(adj[v][i] == 1 && visited[i] == 0) {
visited[i] = 1;
EnQueue(ptrQ, i);
}
}
}
}
若有N个顶点、E条边，时间复杂度是
- 用邻接表存储图，有O(N+E)
- 用邻接矩阵存储图，有O(N2)
3. 图不连通怎么办？
连通分量: 无向图的极大连通子图
极大顶点数:再加1个顶点就不连通了
极大边数:包含子图中所有顶点相连的所有边
强连通: 有向图中顶点v和w之间存在双向路径，则称V和w是强连通的
强连通图: 有向图中任意两顶点均强连通
强连通分量: 有同图的极大强连通子图
typedef struct {
int visited[MaxSize];
int adj[MaxSize][MaxSize]; // 邻接矩阵
int numVertexes, numEdges; // 图中当前的顶点数和边数
} MGraph, *GraphRef;
GraphRef graphRef;
void initGraph()
{
graphRef = malloc(sizeof(MGraph));
graphRef->numVertexes = 10;
int add[10][10] = {
{0, 1, 0, 1, 0, 0, 0, 0, 0, 0},
{1, 0, 1, 0, 1, 0, 0, 0, 0, 0},
{0, 1, 0, 1, 1, 0, 0, 0, 0, 0},
{1, 0, 1, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 1, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 0, 0, 1},
{0, 0, 0, 0, 0, 1, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 1, 1, 0}
};
for (int i = 0; i < graphRef->numVertexes; i++) {
for (int j = 0; j < graphRef->numVertexes; j++) {
graphRef->adj[i][j] = add[i][j];
}
}
for (int i = 0; i < graphRef->numVertexes; i++) {
graphRef->visited[i] = 0;
printf("\n");
for (int j = 0; j < graphRef->numVertexes; j++) {
printf("%d ",graphRef->adj[i][j]);
}
}
printf("\n");
}
void DFSRecursion(int v)
{
graphRef->visited[v] = 1;
printf("%d ", v+1);
for(int i = 0; i < graphRef->numVertexes; i++) {
if(graphRef->adj[v][i] == 1 && graphRef->visited[i] == 0) {
DFSRecursion(i);
}
}
}
void listComponents()
{
for (int i = 0; i < graphRef->numVertexes; i++) {
if(!graphRef->visited[i])
DFSRecursion(i);
}
}
4. 遍历的应用实例
1. 拯救007
-
题意：007从水池中脚踩鳄鱼上岸，利用图的遍历实现算法。
总体算法借鉴void listComponents() 算法，代码如下：
int DFS ( Vertex V )
{
visited[v] = true;
if ( IsSafe(V) ) answer = YES;
else {
for ( V 的每个邻接点 W )
if ( !visited[w] ) {
answer = DFS (W) :
if(answer YEs) break;
}
}
return answer:
}
void save007 ( Graph G )
{
for ( each V in G ) {
if (!visited[v] && FirstJump(V)) {
answer = DES( V ) ;
if (answer == YES) break;
}
}
if (answer YES)output("Yes") ;
else output("No") ;
}
2. 六度空间问题
-
你和任何一个陌生人之间所间隔的人不会超过六个
- 给定社交网络图，请对每个结点计算符合“六度空间”理论的结点占结点总数的百分比。
算法思路
- 对每个结点，进行广度优先搜索
- 搜索过程中累计访问的结点数
- 需要记录“层”数，仅计算6层以内的结点数
void SDS()
{
for(each V in G){
count = BFS(V);
Output(count/N);
}
}
int BFS(Vertex V)
{
visited[V] = true;
count = 1;
level = 0;
last = V;
Enqueue(V, Q);
while(!IsEmpty(Q)){
V = Dequeue(Q);
for(V 的每个邻接点 W)
if(!visited[W]){
visited[W] = true;
Enqueue(W,Q);
count++;
tail = W;
}
if( V == last){
level++;
last = tail;
}
if(level == 6) break;
}
return count;
}
最短路径
- 单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径
有向(无权图)
有向(有权图) - 多源最短路径问题：求任意两顶点间的最短路径
单源最短路
1. 无权图的单源最短路径算法
- 按照递增(非递减)的顺序找出到各个顶点的最短路
void unweightedShortPath(LGraph graph, Vertex s)
{
int *dist = (int *)malloc(sizeof(int) * graph->Nv);
memset(dist, -1, sizeof(int) * graph->Nv);
int *path = (int *)malloc(sizeof(int) * graph->Nv);
memset(path, -1, sizeof(int) * graph->Nv);
dist[s] = 0;
struct QNode qNode;
qNode.front = qNode.rear = 0;
Queue ptrQ = &qNode;
EnQueue(ptrQ, s);
Vertex v;
while (!IsEmpty(ptrQ)) {
v = DeQueue(ptrQ);
struct Vnode *vnode = &graph->G[v];
PtrToAdjVNode adjNode = vnode->firstEdget;
while (adjNode) {
if(dist[adjNode->adjV] == -1)
{
dist[adjNode->adjV] = dist[v] + 1;
path[adjNode->adjV] = v;
EnQueue(ptrQ, adjNode->adjV);
}
adjNode = adjNode->next;
}
}
for (int i = 0; i < graph->Nv; i++) {
printf("%d -- %d\n", dist[i], path[i]);
}
}
2. 有权图的单源最短路径算法
- 有权图的单源最短路径不一定是最短路，而是权重和最小的那条路径
- 有权图中不能有负值，要不然会出现死循环 （此情况不考虑）
- 按照权重递增(非递减)的顺序找出到各个顶点的最短路
- 利用Dijkstra(迪杰斯特拉)算法解决有权图的单源最短路径
- 方法1: 直接扫描所有未收录顶点 - O(IV)
T= O(IV2+ E)对于稠密图效果好 - 方法2: 将dist存在最小堆中 - O( loglVI)
更新dist[w]的值 -(loglVI)
T= 0( IV logV + E loglVI ) = 0( E loglVI)
void shortPath_Dij(LGraph graph, Vertex s)
{
int *dist = (int *)malloc(sizeof(int) * graph->Nv);
for (int i = 0; i < graph->Nv; i++) {
dist[i] = INT_MAX;
}
int *path = (int *)malloc(sizeof(int) * graph->Nv);
memset(path, -1, sizeof(int) * graph->Nv);
bool *collected = (bool *)malloc(sizeof(bool) * graph->Nv);
memset(collected, 0, sizeof(bool) * graph->Nv);
dist[s] = 0;
collected[s] = true;
Vertex v = s;
struct Vnode *vnode = &graph->G[s];
PtrToAdjVNode adjNode = vnode->firstEdget;
while (adjNode) {
if(dist[adjNode->adjV] == INT_MAX)
{
dist[adjNode->adjV] = dist[v] + adjNode->weight;
path[adjNode->adjV] = v;
}
adjNode = adjNode->next;
}
while (1) {
int min = INT_MAX;
for (int i = 0; i < graph->Nv; i++) {
if(min > dist[i] && !collected[i])
{
min = dist[i];
v = i;
}
}
if (min == INT_MAX) {
break;
}
collected[v] = true;
vnode = &graph->G[v];
adjNode = vnode->firstEdget;
while (adjNode) {
if(dist[adjNode->adjV] > dist[v] + adjNode->weight)
{
dist[adjNode->adjV] = dist[v] + adjNode->weight;
path[adjNode->adjV] = v;
}
adjNode = adjNode->next;
}
}
for (int i = 0; i < graph->Nv; i++) {
printf("%d -- %d\n", dist[i], path[i]);
}
}
多源最短路
Floyd(弗洛伊德)算法
- Dk[i][j] = 路径{i -> {l<=k} -> j} 的最小长度
- D0,D1,...,D|v|-1[i][j]即给出了i到j的真正最短距离
- 当Dk-1已经完成，递推到Dk时：
或者k∈最短路径{i -> {l<=k} -> j} ，则Dk = Dk-1
或者k ∈/最短路径{i -> {l<=k} -> j} ，则该路径必定由两段最短路径组成: D[i][j]=D[i][k]+D[k][i]
void shortPath_Floyd()
{
int i, j, k, N;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
D[i][j] = G[i][j];
path[i][j] = -1;
}
}
for (k = 0; k < N; k++) {
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
if(D[i][k] + D[k][j] < D[i][j]){
D[i][j] = D[i][k] + D[k][j];
path[i][j] = k;
}
}
}
}
}
选择最容易变化的动物
- 先通过Floyd算法得到多源最短路径
- 然后获取每个动物最难变的动物
- 然后在最难变的动物中找最容易变的动物的那个动物
void find_minAnimal(int **D, MGraph graph);
void shortPath_Floyd(MGraph graph)
{
int **D, **path;
D = (int **)malloc(sizeof(int *) * graph->Nv);
path = (int **)malloc(sizeof(int *) * graph->Nv);
for (int i = 0; i < graph->Nv; i++) {
D[i] = (int *)malloc(sizeof(int) * graph->Nv);
path[i] = (int *)malloc(sizeof(int) * graph->Nv);
}
for (int i = 0; i < graph->Nv; i++) {
for (int j = 0; j < graph->Nv; j++) {
D[i][j] = graph -> G[i][j];
path[i][j] = -1;
}
}
printf("\n");
for (int i = 0; i < graph->Nv; i++) {
printf("\n");
for (int j = 0; j < graph->Nv; j++) {
printf("%d ",graph->G[i][j]);
}
}
for (int k = 0; k < graph->Nv; k++) {
for (int i = 0; i < graph->Nv; i++) {
for (int j = 0; j < graph->Nv; j++) {
if(i!=j && D[i][k] + D[k][j] < D[i][j]){
D[i][j] = D[i][k] + D[k][j];
path[i][j] = k;
}
}
}
}
printf("\n");
for (int i = 0; i < graph->Nv; i++) {
printf("\n");
for (int j = 0; j < graph->Nv; j++) {
printf("%d ",path[i][j]);
}
}
find_minAnimal(D,graph);
}
void find_minAnimal(int **D, MGraph graph)
{
int minAnimal = 1000, rowMaxAniaml = 0 , path;
for (int i = 0; i < graph->Nv; i++) {
rowMaxAniaml = 0;
for (int j = 0; j < graph->Nv; j++) {
if(i!=j && rowMaxAniaml < D[i][j])
rowMaxAniaml = D[i][j];
}
if (minAnimal > rowMaxAniaml) {
minAnimal = rowMaxAniaml;
path = i;
}
}
printf("weight:%d -- path:%d\n",minAnimal,path);
}
最小生成树
1. Prim算法
void prim(LGraph graph, Vertex s)
{
int *lowcost = (int *)malloc(sizeof(int) * graph->Nv);
for (int i = 0; i < graph->Nv; i++) {
lowcost[i] = INT_MAX;
}
int *parent = (int *)malloc(sizeof(int) * graph->Nv);
memset(parent, -1, sizeof(int) * graph->Nv);
bool *collected = (bool *)malloc(sizeof(bool) * graph->Nv);
memset(collected, 0, sizeof(bool) * graph->Nv);
int *mst = (int *)malloc(sizeof(Vertex) * graph->Nv);
memset(mst, -1, sizeof(Vertex) * graph->Nv);
int mstIndex = 0;
lowcost[s] = 0;
collected[s] = true;
mst[mstIndex] = s;
Vertex v = s;
struct Vnode *vnode = &graph->G[s];
PtrToAdjVNode adjNode = vnode->firstEdget;
while (adjNode) {
if (lowcost[adjNode->adjV] == INT_MAX) {
lowcost[adjNode->adjV] = adjNode->weight;
parent[adjNode->adjV] = v;
}
adjNode = adjNode->next;
}
while (1) {
int min = INT_MAX;
for (int i = 0; i < graph->Nv; i++) {
if (min > lowcost[i] && !collected[i]) {
min = lowcost[i];
v = i;
}
}
if(min == INT_MAX) break;
collected[v] = true;
mst[++mstIndex] = v;
vnode = &graph->G[v];
adjNode = vnode->firstEdget;
while (adjNode) {
if (lowcost[adjNode->adjV] > adjNode->weight && !collected[adjNode->adjV]) {
lowcost[adjNode->adjV] = adjNode->weight;
parent[adjNode->adjV] = v;
}
adjNode = adjNode->next;
}
}
for (int i = 0; i < graph->Nv; i++) {
printf("%d -- %d\n", lowcost[i], parent[i]);
}
}
2. kruskal算法
int fa[55], n, m, cnt;
struct Node {
int u,v,cost;
}edge[300];
int find(int x) //包含路径压缩
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int a, int b)
{
int x = find(a);
int y = find(b);
if(x != y) fa[y] = x;
}
void add(int a, int b, int c)
{
edge[cnt].u = a;
edge[cnt].v = b;
edge[cnt++].cost = c;
}
bool cmp(Node x, Node y)
{
return x.cost < y.cost;
}
int kruskal()
{
int sum = 0, k = 0;
sort(edge, edge + m, cmp);
for (int i = 0; i < m; i++) {
if (find(edge[i].u) == find(edge[i].v))
continue;
else
merge(edge[i].u,edge[i].v);
sum+=edge[i].cost;
k++;
if (k==n-1) {
return sum;
}
}
return 0;
}
int main(int argc, const char * argv[]) {
// insert code here...
int x,y,z;
while (cin>>n && n) {
cnt = 0;
cin>>m;
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
for (int i = 0; i < m; i++) {
cin>>x>>y>>z;
add(x, y, z);
}
cout<<kruskal()<<endl;
}
return 0;
}
