PTA甲级之图的考查_pta甲级是什么

图的存储

图常用的两种存储方式是邻接矩阵跟邻接表

邻接矩阵

邻接矩阵定义

    const int maxn=1005;	//最大顶点数 
    int G[maxn][maxn];  //G存储图的边
1
2

图的邻接矩阵的遍历方式

深度优先遍历（DFS）

    void dfs(int v){	//邻接矩阵的深度优先遍历
        visit[v]=1;     //标记已访问
        cout<<v<<' ';   //访问方式
        for(int i=1;i<=N;i++){
            if(visit[i]==0&&G[v][i]==1) //如果i未被访问且i与v有相连的边，则把i入队
                dfs(i); //访问i
        }
    }

1
2
3
4
5
6
7
8
9
10

广度优先遍历（BFS）

    void bfs(int s){         //s为访问的起点
        queue<int>q;         //定义队列
        q.push(s);           //把起始顶点入队
        visit[s]=1;          //把起始顶点标记为已访问
        while(!q.empty()){   //当队列不为空时，一直循环
            int v=q.front(); //取队首顶点
            cout<<v<<' ';    //访问的方式
            q.pop();         //访问完该顶点，即可将其出队
            for(int i=1;i<=N;i++){
                if(visit[i]==0&&G[v][i]==1){    //如果i未被访问且i与v有相连的边，则把i入队
                    visit[i]=1;     //访问标记要在此处写
                    q.push(i);      //入队
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

完整程序代码

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1005;    //最大顶点数 
    int G[maxn][maxn],N,M;
    int visit[maxn]={0};    //初始化未访问
    void dfs(int v){    //邻接矩阵的深度优先遍历
        visit[v]=1;     //标记已访问
        cout<<v<<' ';   //访问方式
        for(int i=1;i<=N;i++){  //零阶矩阵需要遍历1~N
            if(visit[i]==0&&G[v][i]==1) //如果i未被访问且i与v有相连的边，则dfs(i) 
                dfs(i); //访问i
        }
    }
    void bfs(int s){         //s为访问的起点
        queue<int>q;         //定义队列
        q.push(s);           //把起始顶点入队
        visit[s]=1;          //把起始顶点标记为已访问
        while(!q.empty()){   //当队列不为空时，一直循环
            int v=q.front(); //取队首顶点
            cout<<v<<' ';    //访问的方式
            q.pop();         //访问完该顶点，即可将其出队
            for(int i=1;i<=N;i++){
                if(visit[i]==0&&G[v][i]==1){    //如果i未被访问且i与v有相连的边，则把i入队
                    visit[i]=1;     //访问标记要在此处写
                    q.push(i);      //入队
                }
            }
        }
    }
    int main(){
        cin>>N>>M;  //N为定点数1~N，M为边的个数 
        for(int i=0;i<M;i++){
            int a,b;
            scanf("%d %d",&a,&b);
            G[a][b]=G[b][a]=1;//有向图的输入
            //G[a][b]=1;    有向图的输入
        }
    //  dfs(1);     //深度优先遍历 
    //  bfs(1);     //广度优先遍历 
        return 0;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

//输入
7 7
4 1
4 6
1 3
6 5
6 7
3 2
3 5
1
2
3
4
5
6
7
8
9

邻接表

邻接表的定义

    vector<int>G[maxn];		//初始化maxn 
1

图的邻接矩阵的遍历方式

深度优先遍历（DFS）

    void dfs(int v){
        visit[v]=1;
        cout<<v<<' ';
        for(int i=0;i<G[v].size();i++){
            if(visit[G[v][i]]==0)
                dfs(G[v][i]);
        }
    }

1
2
3
4
5
6
7
8
9

广度优先遍历（BFS）

    void bfs(int s){
        queue<int>q;
        q.push(s);
        visit[s]=1;
        while(!q.empty()){
            int v=q.front();
            q.pop();
            cout<<v<<' ';
            for(int i=0;i<G[v].size();i++){
                if(visit[G[v][i]]==0){	//注意顶点是G[v][i]，而不是i 
                    visit[G[v][i]]=1;
                    q.push(G[v][i]);
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

完整程序代码

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1005;	//最大定点数 
    int N,M;
    vector<int>G[maxn];		//初始化maxn 
    int visit[maxn]={0};    //初始化全部顶点为未访问
    void dfs(int v){
        visit[v]=1;     //标记已访问
        cout<<v<<' ';   //访问方式
        for(int i=0;i<G[v].size();i++){ //与邻接矩阵不同的是，只需要遍历与v相连接的顶点
            if(visit[G[v][i]]==0)   //如果未访问
                dfs(G[v][i]);   //访问
        }
    }
    void bfs(int s){
        queue<int>q;
        q.push(s);
        visit[s]=1;
        while(!q.empty()){
            int v=q.front();
            q.pop();
            cout<<v<<' ';
            for(int i=0;i<G[v].size();i++){
                if(visit[G[v][i]]==0){	//注意顶点是G[v][i]，而不是i 
                    visit[G[v][i]]=1;
                    q.push(G[v][i]);
                }
            }
        }
    }
    int main(){
        cin>>N>>M;	//N为定点数1~N，M为边的个数 
        for(int i=0;i<N;i++){
            int a,b;
            scanf("%d %d",&a,&b);
            //无向图输入 
            G[a].push_back(b);  //表示a与b相连
            G[b].push_back(a);	//表示b与a相连
            
            //有向图输入
            //G[a].push_back(b); //表示a指向b 
        }
    	dfs(1);		//深度优先遍历 
    //	bfs(1);		//广度优先遍历 
        return 0;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

图的相关算法

最短路径

单源最短路径(Dijktra)

Dijkstra脱单法则：找到所有自己亲近的朋友，以这些朋友为中介，让他们找到你想追的女孩的最短路径