图的开始--第一天打卡之图的储存
作者:
lgd123
,
2021-07-25 16:53:15
,
所有人可见
,
阅读 262
/*图的储存(该题是邻接表转化成邻接矩阵)-_-算是模板吧_
1、图:图是一种数据结构,它分为有向图、无向图、加权有向图和加权无向图
2、对于图:图有边和点构成,,两个顶点之间为一条边,如果两条边的顶点相同,这这俩顶点和俩边构成一个环
3、在一个图中没有环,并且是有向图则被称为DAG。
4、与无向图不同的是,有向图的每个顶点,因为有方向,所以有出度和入度之分。
5、连通图:对于任意俩顶点都存在一条路径,则该图为连通图
6、子图:如果一个图的所欲顶点或所边都被另一个图包括,则前者为后者的子图
7、储存图的结构有:邻接表和邻接矩阵
8、遍历图的基本算法为:搜索,其中最常用的是深度优先搜索和宽度优先搜索
9、宽度优先搜索图的还可用作求最短路径的一种方式。
10、对于邻接表:它是由N个单链表组成,即有多少个顶点,就有多少个单链表,每一单链表储存着与一个顶点相连的所有边
11、对于邻接矩阵:它是二维矩阵,所以可以直观显示,任意俩点之间是否有边。但是比较浪费空间,在边数很稀疏的情况下,经常使用邻接表。
12、注:邻接矩阵对于增边和删边操作起来比较方便,还可以直观看出两点之间是否有边。但是也只能表示这一种关系。
*/
----------
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
int m[N][N];
int main()
{
int a,b,c,d;
cin>>a;
memset(m,0,sizeof(m));
for(int i=0;i<a;i++)
{
cin>>b>>c;
for(int j=0;j<c;j++)
{
cin>>d;
m[b][d]=1;
}
}
for(int i=1;i<=a;i++)
{
for(int j=1;j<=a;j++)
{
if(j>1) cout<<" ";
cout<<m[i][j];
}
cout<<endl;
}
//system("pause");
return 0;
}