PTA刷题总结-Part3.5 图专题

1 图的基本概念

图是由两个集合构成 G=(V,E)

非空但有限的定点集合V
可以为空的边的集合E

相关术语

无向图
有向图
简单图
邻接点
路径，简单路径，回路，无环图
无向完全图
有向完全图
顶点的度、入度、出度
稠密图、稀疏图
权、网图
子图
连通图、连通分量
强连通图、强连通分量
生成树
生成森林

2 图的存储结构

2.1 邻接矩阵

输入数据

6 11
3 4 70
1 2 1
5 4 50
2 6 50
5 6 60
1 3 70
4 6 60
3 6 80
5 1 100
2 4 60
5 2 80
A b c d e f

c语言实现

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

#define MaxVertexNum 100
#define INFINITY 65535
typedef int Vertex; // 顶点下标
typedef int WeightType;
typedef char DataType;

// 图
typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;// 顶点数
    int Ne;// 边数
    WeightType G[MaxVertexNum][MaxVertexNum];
    DataType Data[MaxVertexNum];
};
typedef PtrToGNode MGraph;

// 边
typedef struct ENode *PtrToEnode;
struct ENode{
    Vertex V1,V2;
    WeightType Weight;
};
typedef PtrToEnode Edge;

// 初始化
MGraph CreateGraph(int VertexNum){
    MGraph Graph = (MGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    
    for (Vertex V=0; V<Graph->Nv;V++){
        for (Vertex W=0; W<Graph->Nv;W++){
            Graph->G[V][W] = INFINITY;
        }
    }
    return Graph;
}


void InsertEdge(MGraph Graph, Edge E){
    Graph->G[E->V1][E->V2] = E->Weight;
    // 无向图
    Graph->G[E->V2][E->V1] = E->Weight;
}

MGraph BuildGraph(){
    MGraph Graph;
    int Nv=0;
    scanf("%d", &Nv);
    Graph = CreateGraph(Nv);
    
    scanf("%d", &(Graph->Ne));
    if (Graph->Ne != 0){
        Edge E = (Edge)malloc(sizeof(struct ENode));
        for (int i=0; i<Graph->Ne; i++){
            scanf("%d %d %d", &(E->V1), &(E->V2), &(E->Weight));
            InsertEdge(Graph, E);
        }
    }
    
    for (Vertex V=0; V<Graph->Nv; V++){
        scanf(" %c", &(Graph->Data[V]));
    }
    
    return Graph;
}

int main(){
    MGraph Graph = BuildGraph();
    printf("Nv = %d\n", Graph->Nv);
    printf("Ne = %d\n", Graph->Ne);
    
    for (Vertex V=0; V<Graph->Nv; V++){
        printf(" %c", Graph->Data[V]);
    }
}

2.1 邻接表

输入数据

6 11
3 4 70
1 2 1
5 4 50
2 6 50
5 6 60
1 3 70
4 6 60
3 6 80
5 1 100
2 4 60
5 2 80
A b c d e f

c语言实现

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

#define MaxVertexNum 100
#define INFINITY 65535
typedef int Vertex; // 顶点下标
typedef int WeightType;
typedef char DataType;

// 边
typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1, V2;
    WeightType Weight;
};
typedef PtrToENode Edge;

// 邻接点
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
    Vertex AdjV; // 邻接点下标
    WeightType Weight;
    PtrToAdjVNode Next;
};

// 顶点表头节点
typedef struct Vnode{
    PtrToAdjVNode FirstEdge;
    DataType Data;
} AdjList[MaxVertexNum];

// 图
typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;
    int Ne;
    AdjList G;
};
typedef PtrToGNode LGraph;

// 初始化
LGraph CreateGraph(int VertexNum){
    LGraph Graph = (LGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    
    for(Vertex V=0; V<Graph->Nv; V++){
        Graph->G[V].FirstEdge = NULL;
    }
    
    return Graph;
}


void InsertEdge(LGraph Graph, Edge E){
    PtrToAdjVNode NewNode = (PtrToAdjVNode) malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V2;
    NewNode->Weight = E->Weight;
    NewNode->Next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = NewNode;
    
    // 无向图
    NewNode = (PtrToAdjVNode) malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V1;
    NewNode->Weight = E->Weight;
    NewNode->Next = Graph->G[E->V2].FirstEdge;
    Graph->G[E->V2].FirstEdge = NewNode;
}

LGraph BuildGraph(){
    LGraph Graph;
    int Nv=0;
    scanf("%d", &Nv);
    Graph = CreateGraph(Nv);
    
    scanf("%d", &(Graph->Ne));
    if (Graph->Ne != 0){
        Edge E = (Edge)malloc(sizeof(struct ENode));
        for (int i=0; i<Graph->Ne;i++){
            scanf("%d %d %d", &(E->V1), &(E->V2), &(E->Weight));
            InsertEdge(Graph, E);
        }
    }
    
    for (Vertex V=0;V<Graph->Nv;V++){
        scanf(" %c", &(Graph->G[V].Data));
    }
    
    return Graph;
}

int main(){
    LGraph Graph = BuildGraph();
    printf("Nv = %d\n", Graph->Nv);
    printf("Ne = %d\n", Graph->Ne);
    printf("Node = %c\n", Graph->G[0].Data);
}

使用Java做题的时候，邻接表的结构可以简单地写成
Map<T, Set<T>> = new HashMap<Integer, HashSet<Integer>>();

3 遍历

3.1 DFS深度优先搜索

06-图1 列出连通集 (25分)

#include <stdio.h>
#include <stdlib.h>
#include <queue>
using namespace std;

#define MaxVertexNum 20
#define INFINITY 65535
typedef int Vertex; // 顶点下标
typedef int WeightType;
typedef char DataType;

// 边
typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1, V2;
};
typedef PtrToENode Edge;

// 邻接点
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
    Vertex AdjV; // 邻接点下标
    PtrToAdjVNode Next;
};

// 顶点表头节点
typedef struct Vnode{
    PtrToAdjVNode FirstEdge;
    DataType Data;
} AdjList[MaxVertexNum];

// 图
typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;
    int Ne;
    AdjList G;
};
typedef PtrToGNode LGraph;

bool visited[MaxVertexNum];
// 初始化
LGraph CreateGraph(int VertexNum){
    LGraph Graph = (LGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    
    for(Vertex V=0; V<Graph->Nv; V++){
        Graph->G[V].FirstEdge = NULL;
        visited[V] = false;
    }
    
    return Graph;
}


void InsertEdge(LGraph Graph, Edge E){
    PtrToAdjVNode NewNode = (PtrToAdjVNode) malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V2;
    NewNode->Next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = NewNode;
    
    
    // 无向图
    NewNode = (PtrToAdjVNode) malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V1;
    NewNode->Next = Graph->G[E->V2].FirstEdge;
    Graph->G[E->V2].FirstEdge = NewNode;
}

LGraph BuildGraph(){
    LGraph Graph;
    int Nv=0;
    scanf("%d", &Nv);
    Graph = CreateGraph(Nv);
    
    scanf("%d", &(Graph->Ne));
    if (Graph->Ne != 0){
        Edge E = (Edge)malloc(sizeof(struct ENode));
        for (int i=0; i<Graph->Ne;i++){
            scanf("%d %d", &(E->V1), &(E->V2));
            InsertEdge(Graph, E);
        }
    }
    
    
    return Graph;
}

bool IsEdge(LGraph Graph, Vertex V, Vertex W){
    bool ans = false;
    PtrToAdjVNode p =Graph->G[V].FirstEdge;
    while (p){
        if (p->AdjV == W){
            ans = true;
            break;
        }
        p = p->Next;
    }
    return ans;
}

void DFS(LGraph Graph, Vertex V){
    printf("%d ", V);
    visited[V] = true;
    for (Vertex W=0;W<Graph->Nv;W++){
        if (V!=W && !visited[W] && IsEdge(Graph,V, W)){
            DFS(Graph, W);
        }
    }
}

void ClearVisited(int VertexNum){
    for (int i=0;i<VertexNum;i++){
        visited[i] = false;
    }
}

void BFS(LGraph Graph, Vertex V){
    queue<Vertex> Q;
    Q.push(V);
    printf("%d ", V);
    visited[V] = true;
    while (!Q.empty()){
        Vertex T = Q.front();
        Q.pop();
        for (Vertex W=0;W<Graph->Nv;W++){
            if (T!=W && !visited[W] && IsEdge(Graph,T, W)){
                printf("%d ", W);
                visited[W] = true;
                Q.push(W);
            }
        }
    }
}
int main(){
    LGraph Graph = BuildGraph();
    // DFS
    for (Vertex V=0;V<Graph->Nv;V++){
        if (!visited[V]){
            printf("{ ");
            DFS(Graph,V);
            printf("}\n");
        }
    }
    ClearVisited(Graph->Nv);
    for (Vertex V=0;V<Graph->Nv;V++){
        if (!visited[V]){
            printf("{ ");
            BFS(Graph,V);
            printf("}\n");
        }
    }
}

当然不是所有使用到深度优先搜索的题目都需要构造树结构的。很多题问你求出“所有可能”的结果时，都是可以使用DFS的。

3.2 BFS广度优先搜索

什么时候应该使用BFS

层级遍历
- 层级bfs,二叉树不用标记visited，但是图需要
- 出队列时放入数组
由点及面
- 普通bfs,标记visited
- 入队列时标记visited
拓扑排序
- 普通bfs,入度数组代替标记visited
- 节点可以在入栈/出栈时抠出
最短路径
- 层级bfs,标记visited
- 矩阵表示的点要用层级，返回int dist每层累加
- 邻接表表示的点使用map直接保存到起点的最短路径
非递归的方式找到所有方案

邻接链表的存储

Map<T, Set<T>> = new HashMap<Integer, HashSet<Integer>>();

什么时候处理数据

出队列时操作？
- （重要）层级遍历一定要在出栈时放入数组
- 拓扑排序的节点
入队列时操作？
- （重要）标记访问节点一定要在入栈时就操作
- 拓扑排序的节点

时间复杂度
O(N+M)

题目：06-图3 六度空间 (30分)

#include <stdio.h>
#include <stdlib.h>
#include <queue>
using namespace std;
#define MaxVertexNum 1001
#define INFINITY 65535
typedef int Vertex; // 顶点下标

// 边
typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1, V2;
};
typedef PtrToENode Edge;

// 邻接点
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
    Vertex AdjV; // 邻接点下标
    PtrToAdjVNode Next;
};

// 顶点表头节点
typedef struct Vnode{
    PtrToAdjVNode FirstEdge;
} AdjList[MaxVertexNum];

// 图
typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;
    int Ne;
    AdjList G;
};
typedef PtrToGNode LGraph;

bool visited[MaxVertexNum];
// 初始化
LGraph CreateGraph(int VertexNum){
    LGraph Graph = (LGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    
    for(Vertex V=1; V<Graph->Nv; V++){
        Graph->G[V].FirstEdge = NULL;
    }
    
    return Graph;
}


void InsertEdge(LGraph Graph, Edge E){
    PtrToAdjVNode NewNode = (PtrToAdjVNode) malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V2;
    NewNode->Next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = NewNode;
    
    // 无向图
    NewNode = (PtrToAdjVNode) malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V1;
    NewNode->Next = Graph->G[E->V2].FirstEdge;
    Graph->G[E->V2].FirstEdge = NewNode;
}

LGraph BuildGraph(){
    LGraph Graph;
    int Nv=0;
    scanf("%d", &Nv);
    Graph = CreateGraph(Nv);
    
    scanf("%d", &(Graph->Ne));
    if (Graph->Ne != 0){
        Edge E = (Edge)malloc(sizeof(struct ENode));
        for (int i=1; i<=Graph->Ne;i++){
            scanf("%d %d", &(E->V1), &(E->V2));
            InsertEdge(Graph, E);
        }
    }
    return Graph;
}

void ClearVisited(LGraph Graph){
    for (int i=1; i<=Graph->Nv;i++){
        visited[i] = false;
    }
}

int BFS(LGraph Graph, Vertex V){
    int ans = 1;
    int level = 0;
    Vertex end=V; // end 当前这一层访问的最后一个节点
    Vertex tail=0;// tail 每次进入队列的最后一个节点，也是x当前这一层的下一层
    visited[V] = true;
    queue<Vertex> Q;
    Q.push(V);
    while (!Q.empty()){
        Vertex Temp = Q.front();
        Q.pop();
        for (PtrToAdjVNode p = Graph->G[Temp].FirstEdge; p ; p = p->Next){
            if (!visited[p->AdjV]){
                visited[p->AdjV] = true;
                Q.push(p->AdjV);
                ans++;
                tail = p->AdjV;
            }
        }
        if (Temp == end){
            level++;
            // 向外推了一层
            end = tail;
        }
        if (level == 6){
            break;
        }
    }
    return ans;
}

int main(){
    LGraph Graph = BuildGraph();
    for (int i=1; i<=Graph->Nv;i++){
        ClearVisited(Graph);
        int count = BFS(Graph, i);
        double ans = (double)count/(double)Graph->Nv;
        printf("%d: %.2lf%%\n", i, ans*100);
    }
}

subsets

public class Solution {
    /**
     * @param nums: A set of numbers
     * @return: A list of lists
     */
    public List<List<Integer>> subsets(int[] nums) {
        if (nums == null) {
            return null;
        }
        Arrays.sort(nums);
        int n = nums.length;
         List<List<Integer>> results = new LinkedList<>();
         Queue<List<Integer>> queue = new LinkedList<>();
         queue.offer(new LinkedList<>());
         while (!queue.isEmpty()) {
             List<Integer> curr = queue.poll();
             results.add(curr);
             for (int i = 0; i< n; i++) {
                 if (curr.size() == 0 || curr.get(curr.size() - 1) < nums[i]) {
                     List<Integer> intList = new LinkedList<>(curr);
                     intList.add(nums[i]);
                     queue.offer(intList);
                 }
             }
         }
         return results;
    }
}

4 最短路径

不考虑负值圈。

4.1 单源无权最短路

使用BFS，按路径长度递增的次序产生找到各个顶点。

4.2 单源有权最短路-Dijkstra

按路径长度递增的次序产生最短路径。

4.3 多源最短路-Floyd

要求出每对顶点之间的最短距离
稠密图，邻接矩阵
动态规划

07-图4 哈利·波特的考试 (25分)

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

#define MaxVertexNum 101
#define INFINITY 65535
typedef int Vertex; // 顶点下标
typedef int WeightType;

// 图
typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;// 顶点数
    int Ne;// 边数
    WeightType G[MaxVertexNum][MaxVertexNum];
};
typedef PtrToGNode MGraph;

// 边
typedef struct ENode *PtrToEnode;
struct ENode{
    Vertex V1,V2;
    WeightType Weight;
};
typedef PtrToEnode Edge;

// 初始化
MGraph CreateGraph(int VertexNum){
    MGraph Graph = (MGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    
    for (Vertex V=0; V<Graph->Nv;V++){
        for (Vertex W=0; W<Graph->Nv;W++){
            Graph->G[V][W] = INFINITY;
        }
    }
    return Graph;
}


void InsertEdge(MGraph Graph, Edge E){
    Graph->G[E->V1][E->V2] = E->Weight;
    // 无向图
    Graph->G[E->V2][E->V1] = E->Weight;
}

MGraph BuildGraph(){
    MGraph Graph;
    int Nv=0;
    scanf("%d", &Nv);
    Graph = CreateGraph(Nv);
    
    scanf("%d", &(Graph->Ne));
    if (Graph->Ne != 0){
        Edge E = (Edge)malloc(sizeof(struct ENode));
        for (int i=0; i<Graph->Ne; i++){
            scanf("%d %d %d", &(E->V1), &(E->V2), &(E->Weight));
            E->V1--;
            E->V2--;
            InsertEdge(Graph, E);
        }
    }
    
    return Graph;
}

void Floyd(MGraph Graph, WeightType D[][MaxVertexNum]){
    for (Vertex k =0; k<Graph->Nv;k++){
        for (Vertex i=0;i<Graph->Nv;i++){
            for (Vertex j=0; j<Graph->Nv;j++){
                if (D[i][k] + D[k][j] < D[i][j]){
                    D[i][j] =D[i][k] + D[k][j];
                }
            }
        }
    }
}

void FindAnimal(MGraph Graph){
    Vertex minI=0;
    int minw = INFINITY;
    for (Vertex i=0;i<Graph->Nv;i++){
        int maxrow = -1;
        for (Vertex j=0; j<Graph->Nv;j++){
            if (i!=j && Graph->G[i][j] > maxrow){
                maxrow =Graph->G[i][j];
            }
        }
        if (maxrow < minw){
            minI = i;
            minw = maxrow;
        } else if (maxrow == INFINITY) {
            printf("0\n");
            return;
        }
    }
    printf("%d %d\n", minI+1, minw);
}
int main(){
    MGraph Graph = BuildGraph();
    Floyd(Graph, Graph->G);
    FindAnimal(Graph);
}

5 最小生成树

5.1 稠密图-Prim

从顶点出发

5.2 稀疏图-Kruskal

把森林合并成一颗树
从边出发

6 拓扑排序

使用队列存储入度为0的节点

最后编辑于：2020.04.20 11:23:34

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 217,734评论 6赞 505
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,931评论 3赞 394
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 164,133评论 0赞 354
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,532评论 1赞 293
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,585评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,462评论 1赞 302
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,262评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,153评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,587评论 1赞 314
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,792评论 3赞 336
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,919评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,635评论 5赞 345
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,237评论 3赞 329
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,855评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,983评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,048评论 3赞 370
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,864评论 2赞 354