有关图的存储结构

(1)顺序存储方法

该方法把逻辑上相邻的结点存储在物理位置上相邻的存虚模信储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。

由此得到的存储表示称为顺序存储结构 (Sequential Storage Structure)，通差轮常借助程序码者语言的数组描述。

该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。 (2)链接存储方法

该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构(Linked Storage Structure),通常借助于程序语言的指针类型描述。

代码

/*输入：先输入两个数，代表点的数量和边的数量，

再输入各个边，起点编号 >终点编号，编号从0开始

例子：

6 10

0 3

0 4

1 4

1 3

3 5

0 1

4 5

5 2

4 2

4 3

输出:

0 1 4 3 5 2

思路：

用vector建立邻接表

计算每个饥或点的入度

如果是偏序无环的，一定存在入度为0的点，输出并且删除它，同烂键伍时删除它出发的边，更新其他点的入度

循环直到移除所有点，输出顺序就是拓扑排序

*/

#include<iostream>

#include<vector>

using namespace std

int main() {

freopen("in.txt","r",stdin)//重定向亮陵输入流//in.txt 建在程序所在的文件夹里

int M,N

scanf("%d%d",&M,&N)//M个点，N条边

vector<int>maps[M]

int innode[M]={0}//入度

for(int i=0i<Ni++)

{

int tx,ty

scanf("%d%d",&tx,&ty)

maps[tx].push_back(ty)

++innode[ty]

}

for(int time=0time<Mtime++)

for(int i=0i<Mi++)

{

if(innode[i]==0)

{

printf("%d ",i)

for(vector<int>::iterator it = maps[i].begin()it != maps[i].end()++it)

{

--innode[*it]

}

innode[i]=-1

break

}

}

}

---