图的遍历（邻接矩阵、邻接表）

邻接矩阵

初始化：结点i到i的距离自然是0，其他都是const int INF=0x3f3f3f3f;

1
2
3
4
5
6
7
8
9
10
for(i = 1; i <= m; i++)
{
    for(j = 1; j <= m; j++)
	{
		if(i == j)
			edge[i][j] = 0;
		else
			edge[i][j] = INF;
	}
}

输入的时候以此录入即可，遍历就是两层for循环了，这里不再赘述

1
2
cin>>s>>e>>value;
edge[s][e]=value;

邻接表

邻接表的出现是因为很多结点之间没有关联，使用INF太蠢了，完全可以使用链表的形式

vector实现邻接表

链表中的data、next使用结构体存储，vector将它们关联起来

1
2
3
4
5
struct edge
{
	int to, cost;
};
vector<edge> G[100];

输入

1
2
3
4
5
for(int i = 0; i < n; ++i)
{
	scanf("%d%d%d", &start, &point, &weight);
	G[start].push_back({point, weight});
}

这样输出时，内层遍历结点i时只需

1
2
3
4
for(int j = 0; j < G[i].size(); ++j)
{
	printf(" %d", G[i][j].to, G[i][j].cost);
}

数组实现邻接表

既然有数组实现链表（http:），自然也有数组实现邻接表了；
虽然关联结点时需要两个数组first[] Next[]实现，但没有插入、删除操作
既然是数组肯定要先给个范围了

1
2
3
//Max_m边，Max_n点
int start[Max_m+1], point[Max_m+1], weight[Max_m+1];
int first[Max_n+1], Next[Max_n+1];


总结一下上面邻接矩阵和vecotor的实现，只需给某个结点，就能遍历到和这个点有关联的结点，并输出权值；

算法实现
对于某个结点，只需知道它作为起点在录入时的次序即可得到相应的值，后面我都将这作为起点录入时的次序简称为索引（如果能得到索引，顺着start[i],point[i],weight[i]就都能得到了），显然如果某结点与多个结点相关联，它的索引有很多，这样问题就指向了如何找到某结点的所有索引。

  • first[]最终存放各结点的最后索引（通过结点找索引）
  • Next[]存放各索引的结点的前一个索引（通过索引找索引）
    1
    2
    3
    4
    5
    6
    7
    8
    for(int i=1; i<=n; i++)
    	first[i]=-1;//first[]初始化-1
    for(int i=1; i<=m; i++)
    {
    	cin>>start[i]>>point[i]>>weight[i];
    	Next[i]=first[start[i]];
    	first[start[i]]=i;
    }
遍历到某个结点i时，这样找它的所有索引 
1
2
3
4
5
6
k=first[i];
while(k!=-1)
{
	printf("%d %d %d\n",start[k], point[k], weight[k]);
	k=Next[k];
}

最后，如果理解了这一过程就不难发现，输出的i相关联的结点的顺序，是逆序的。（从最后的索引一个一个往前找的过程）