图论(Graph Theory)是数学的一个分支.它以图为研究对象.
图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系.
图论本身是应用数学的一部份.图论起源于著名的哥尼斯堡七桥问题,关于图论的文字记载最早出现在欧拉1736年的著作中,他所考虑的原始问题有很强的实际背景.
图论算法在计算机科学种扮演着很重要的角色,它提供了对很多问题都有效的一种简单而系统的建模方式.很多问题都可以转化为图论问题,然后用图论的基本算法加以解决.
图中最基本的元素是边和点,可以使用点和连接点的边来表示,下面就是一些图的表示.
使用计算机解决图论问题最基本的问题就是如何在程序中存储图.
常用的图的存储方式有邻接矩阵和邻接表.下面分别介绍一下这两种存储结构.
邻接矩阵采用一个矩阵来表示点和点的邻接关系.如果一个图有N个顶点那么用一个N*N的0-1矩阵来表示这个图,如果第i个节点和第j个节点如果有边相连,那么第i行第j个元素就是1,否则为0.这样的方式就需要O(N^2)的存储空间.
当一个图中边很少,但点很多(或者叫稀疏图)的时候,这个邻接矩阵中有大量的0元素,浪费了很大的空间.
邻接表采用的是另外一种思想,直接存储存在的邻接关系.对应每一个顶点,用一个表存放和它邻接的顶点.这样需要的空间就只是O(E),E为图中边的数目.
现在,我们需要把一个图从邻接矩阵表示转换到邻接表表示.
例如,下面表示了从一个图到邻接矩阵和邻接表的转换过程
图:
邻接矩阵:
邻接表:
1: 2 3
2: 1 4 5
3: 1 4
4: 2 3 5
5: 2 4
Input
输入数据第1行是一个整数N(N<=500),代表所给是一个有N个顶点的图.
接下来从第2行到第N+1行,给出了1个N*N阶0-1矩阵,第i+1行第j个元素给出了邻接矩阵第i行第j列的元素.同一行的各个元素使用1个空格隔开.
Output
输出数据有N行.
第i行格式如下:
i: v1 v2 v3....
v1,v2,v3是和第i个顶点邻接的点的编号,并且v1<v2<v3<....编号之间使用空格隔开,冒号后面有1个空格.第N行末尾有1个换行符.
Sample Input
5 0 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 1 0 1 0 1 0
Sample Output
1: 2 3 2: 1 4 5 3: 1 4 4: 2 3 5 5: 2 4
Hint
输入数据很多,使用scanf,printf避免超时
Source
Author
解题思路：
对于邻接表的深刻理解罢了，没有什么难的，但是要注意不要PE，，用flag变量，边标记边计算是个不错的方法啊。
代码：
#include <cstdio>
#include <string>
#include <iostream>
#include <cstdlib>
using namespace std;
# define MAX 500+4
# define inf 99999999
int edge[MAX][MAX];
int n;
void init()
{
for ( int i = 1;i <= n;i++ )
{
for ( int j = 1;j <= n;j++ )
{
if ( i==j )
edge[i][j] = 0;
else
edge[i][j] = inf;
}
}
}
void input()
{
for ( int i = 1;i <= n;i++ )
{
for ( int j = 1;j <= n;j++ )
{
cin>>edge[i][j];
}
}
}
int main(void)
{
while ( cin>>n )
{
init();
input();
for ( int i = 1;i <= n;i++ )
{
int flag = 0;
printf ("%d: ",i);
for ( int j = 1;j <= n;j++ )
{
if ( edge[i][j] )
{
if ( !flag )
{
printf("%d",j);
flag = 1;
}
else
printf(" %d",j);
}
}
cout<<endl;
}
}
return 0;
}