问链式前向星存储

#include<iostream>
#include<queue>
using namespace std;
const int maxn=1e5+5;  // 适配N,M≤1e5的规模
int head[maxn],node;   // head：链式前向星头数组，node：边计数器
int vis[maxn];         // 标记顶点是否被访问（DFS/BFS共用）

// 边结构体（链式前向星）：pre记录上一条边索引，v记录目标顶点
struct Edge{
	int pre,v;
}edge[maxn];  // 存储所有边（大小适配1e5条边）

// 功能：添加有向边（u→v）
void add_edge(int u,int v){
	edge[++node].v=v;    // 边的目标顶点为v
	edge[node].pre=head[u];// 边的前驱指向u之前的第一条边
	head[u]=node;         // u的第一条边更新为当前边
}

// 功能：深度优先遍历（DFS），从u出发遍历所有可达顶点并输出
void dfs(int u){
	cout<<u<<" ";        // 访问当前顶点并输出
	vis[u]=1;            // 标记为已访问
	// 遍历u的所有出边，递归访问未标记的邻接顶点
	for(register int i=head[u];i;i=edge[i].pre){
		int v=edge[i].v;
		if(!vis[v]){
			dfs(v);
		}
	}
	return ;
}

// 功能：广度优先遍历（BFS），从u出发遍历所有可达顶点并输出
void bfs(int u){
	queue<int> q;        // 存储待访问顶点的队列
	q.push(u);           // 起始顶点入队
	vis[u]=1;            // 标记为已访问
	while(!q.empty()){
		int cur=q.front();// 取出队首顶点
		q.pop();
		cout<<cur<<" ";  // 访问当前顶点并输出
		// 遍历当前顶点的所有出边，未标记的邻接顶点入队
		for(register int i=head[cur];i;i=edge[i].pre){
			int v=edge[i].v;
			if(!vis[v]){
				vis[v]=1;
				q.push(v);
			}
		}
	}
	return ;
}

int main(){
	int n,m,u,v,start;
	cin>>n>>m>>start;    // 输入顶点数n、边数m、起始遍历顶点start
	// 输入m条有向边，构建链式前向星
	for(register int i=1;i<=m;++i){
		cin>>u>>v;
		add_edge(u,v);   // 直接构建正向图（u→v）
	}
	
	// 执行DFS遍历并输出结果
	cout<<"DFS遍历结果：";
	dfs(start);
	cout<<endl;
	
	// 重置访问标记数组（为BFS做准备）
	for(register int i=1;i<=n;++i){
		vis[i]=0;
	}
	
	// 执行BFS遍历并输出结果
	cout<<"BFS遍历结果：";
	bfs(start);
	cout<<endl;
	
	return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int ednum;
int nodnum;
int cnt;
int head[100];//此处对应的是点
//head[i]表示存储边集中，以i为起点的第一条边的位置；
struct edge
{
    int u;//起点
    int v;//终点
    int w;//改变对应的代价
    int next;//相同起点下一个边的位置
}edge[100];//此处对应的是边
void add(int u, int v, int w)
{
    edge[cnt].u = u;
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
}
int main()
{
    cnt = 0;
    memset(head,-1,sizeof(head));
    scanf("%d %d", &nodnum, &ednum);
    for(int i = 0; i < ednum; i ++)
    {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        add(u,v,w);
    }
    //输入：
    // 5 7
    // 1 2 1
    // 2 3 1
    // 3 4 1
    // 1 3 1
    // 4 1 1
    // 1 5 1
    // 4 5 1
    for(int i = 1; i <= nodnum; i ++)
    {
        for(int j = head[i]; ~j; j = edge[j].next)//j代表只要不是-1就
        {
            printf("u = %d v = %d\n", i, edge[j].v);
        }
    }
    //输出：
    // u = 1 v = 5
    // u = 1 v = 3
    // u = 1 v = 2
    // u = 2 v = 3
    // u = 3 v = 4
    // u = 4 v = 5
    // u = 4 v = 1
    return 0;
}