目录

无向图

表示方式

邻接表

邻接矩阵

储存方式

二维数组(即邻接矩阵）

STL(推荐使用STL，主要是有计数功能)

有向图

表示方式

邻接表

邻接矩阵

储存方式

二维数组(即邻接矩阵）

STL(推荐使用STL，主要是有计数功能)

表示方式

邻接表

邻接表即一行两个数u,v。无向图中表示顶点u和顶点v有一条边。

若u=1,v=3。则表示顶点1，3之间有一条边。

像这样，就是邻接表表示的无向图

 

邻接矩阵

邻接矩阵有着行和列之分，但是行和列都表示顶点，通常用0表示没有连线，用1表示有连线。

将上图用邻接矩阵表示就是： 

顶点	1	2	3	4	5
1	0	0	1	1	0
2	0	0	1	1	1
3	1	1	0	1	0
4	1	1	1	0	1
5	0	1	0	1	0

可以看到，以顶点(1，1），（2，2），（3，3），（4，4），（5，5）为对角线，无向图是对称的 

储存方式

二维数组(即邻接矩阵）

就像普通的输入二维数组那样，储存图

for(int i=1;i<=n;i++) {
    for(int j=1;j<=n;j++) {
		cin>>G[i][j];
	}
}

STL(推荐使用STL，主要是有计数功能)

vectorG[10005];//创建无向图
//G[i][sum]=j 表示节点i与节点j有一条边相连,并且它是第sum+1条边(下标默认从0开始)
//例如G[1][0]=3 表示节点1与节点3有一条边相连,并且它是第1条边(下标默认从0开始)
//例如G[3][1]=2 表示节点3与节点2有一条边相连,并且它是第2条边(下标默认从0开始)
//例如G[1][2]=2 表示节点1与节点2有一条边相连,并且它是第3条边(下标默认从0开始)
//例如G[2][2]=4 表示节点2与节点4有一条边相连,并且它是第3条边(下标默认从0开始)

//若题目是邻接矩阵表示
for(int i=0;i>x;
        if(x) G[i].push_back(j);//若G[i]第一次插入则:G[i][0]=j,同理第二次则:G[i][1]=j
    }
}
//若题目是邻接表表示
for(int i=1;i<=n;i++) {
    int u,v;cin>>u>>v;
    G[u].push_back(v);
}

有向图 表示方式 邻接表

邻接表即一行两个数u,v。有向图中表示顶点u到顶点v有一条边。

若u=1,v=3。则表示顶点1-->3有一条边。但3-->1却不一定有

像这样，就是邻接表表示的有向图

邻接矩阵

邻接矩阵有着行和列之分，但是行和列都表示顶点，通常用0表示没有连线，用1表示有连线。

将上图用邻接矩阵表示就是： 

顶点	1	2	3	4	5
1	0	0	1	1	0
2	1	0	1	0	1
3	0	0	0	1	0
4	0	1	0	0	1
5	0	0	1	1	0

可以看到，以顶点(1，1），（2，2），（3，3），（4，4），（5，5）为对角线，有向图不一定对称。

储存方式 二维数组(即邻接矩阵）

就像普通的输入二维数组那样，储存图

for(int i=1;i<=n;i++) {
    for(int j=1;j<=n;j++) {
		cin>>G[i][j];
	}
}

STL(推荐使用STL，主要是有计数功能)

vectorG[10005];//创建有向图
//G[i][sum]=j 表示节点i有一条边指向节点j，并且它是第sum+1条边(下标默认从0开始)
//例如G[1][0]=3 表示节点1有一条边指向节点3,并且它是第1条边(下标默认从0开始)
//例如G[3][1]=2 表示节点3有一条边指向节点2,并且它是第2条边(下标默认从0开始)
//例如G[1][2]=2 表示节点1有一条边指向节点2,并且它是第3条边(下标默认从0开始)
//例如G[2][2]=4 表示节点2有一条边指向节点4,并且它是第3条边(下标默认从0开始)

//若题目是邻接矩阵表示
for(int i=0;i>x;
        if(x) G[i].push_back(j);//若G[i]第一次插入则:G[i][0]=j,同理第二次则:G[i][1]=j
    }
}
//若题目是邻接表表示
for(int i=1;i<=n;i++) {
    int u,v;cin>>u>>v;
    G[u].push_back(v);
}