//code by virtualtan 寒七

//注：本代码包括了三种，可能有点杂

加边：

#include <cstdio>
#include <algorithm>

#define MAXN 1111
#define MAXM 2222222

int n, m, cnt;
int a[MAXN][MAXN], b[MAXN][MAXN];

struct edge { 
	int x, y, val, next;//起点 终点 权 上一条起点相同的边 的编号 
}e[MAXM];

void add_edge(int x, int y, int val) { 
	cnt++;//边的序数 
	e[cnt].x = x;
	e[cnt].y = y;
	e[cnt].val = val;
	e[cnt].next = head[x];//head【x】表示cnt 之前的一条首顶点为 x 的边 的编号 ——可以直接跳转到e[].next 
	head[x] = cnt;//更新首顶点为 x 的最后一条边 
	return ;
}

//有向无权图 
int main() { 
	scanf("%d%d", &n, &m);
	memset(a, 0x3f, sizeof(a));//主要是针对矩阵
	for(int i = 1; i <= n; i++) { 
		a[i][i] = 0;//这个应该是解决自环问题
	}
	for(int i = 1; i <= m; i++) { 
		int x, y;
		scanf("%d%d", &x, &y);
		//邻接矩阵
		a[x][y] = 1;
		//邻接表 
		b[x][++b[x][0]] = y;
		//链式前向星(重点)
		add_edge(x, y, 1); 
	}

//补：
有权图解决两节点间的重边问题，只需加一个判断就行：

if(a[i][j] > w) { 
	a[i][j] = w;
}

或者用min（a[i][j] , w）;个人喜好

还有注意自环问题，特殊处理

图的遍历

一般采用搜索算法

遍历出所有与1相连的边：

//邻接矩阵做法
	for(int i = 1; i <= n; i++) { 
		if(a[1][i] == 1) { 
      //大体是这样就行
		}
	}
//邻接表做法
	for(int i = 1; i <= b[1][0]; i++) { 
		b[1][i];
	}
	// 因为e[1].next最开始初始化的时候给它赋值的 head[1] 等于0（默认的0） 
	// 从后向前找 “i”表示'i > 0' i = e[i].next 起点为x（找所有与x相连的点)的最后一条边 
	// 此处x = 1； 
	for(int i = head[1]; i; i = e[i].next) { 
		int x = e[i].x, y = e[i].y, val = e[i].val;
	}
}

最后附上：
/*邻接表 的模样
0 1 2 3 4 5
1 2 3 4
2 4
3 3
4 5
5 4 */

/*测试数据
5
1 2
2 4
1 4
5 4
4 5
1 3
*/
链式前向星的作用:
我一开始总是因为可以直接求出最短路的
遍历时，对于一个点u，枚举这个点所有向外的边

转载于:https://www.cnblogs.com/tyner/p/10701731.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/95136369

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。