图构建

邻接矩阵不用说ez

主要讲一下邻接表的数组实现和链式前向星:

链式前向星

是一个结构体数组

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;//点数最大值
int n, m, cnt;//n个点，m条边
struct Edge
{
 int to, w, next;//终点，边权，同起点的上一条边的编号
}edge[maxn];//边集
int head[maxn];//head[i],表示以i为起点的第一条边在边集数组的位置（编号）
void init()//初始化
{
 for (int i = 0; i <= n; i++) head[i] = -1;
 cnt = 0;
}
void add_edge(int u, int v, int w)//加边，u起点，v终点，w边权
{
 edge[cnt].to = v; //终点
 edge[cnt].w = w; //权值
 edge[cnt].next = head[u];//以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
 head[u] = cnt++;//更新以u为起点上一条边的编号
}
int main()
{
 cin >> n >> m;
 int u, v, w;
 init();//初始化
 for (int i = 1; i <= m; i++)//输入m条边
 {
     cin >> u >> v >> w;
     add_edge(u, v, w);//加边
     /*
     加双向边
     add_edge(u, v, w);
     add_edge(v, u, w);
     */
 }
 for (int i = 1; i <= n; i++)//n个起点
 {
     cout << i << endl;
     for (int j = head[i]; j != -1; j = edge[j].next)//遍历以i为起点的边
     {
         cout << i << " " << edge[j].to << " " << edge[j].w << endl;
     }
     cout << endl;
 }
 return 0;
}

邻接表数组实现

是多个数组实现

u,v,w是起点,终点,权,first是第一个起点,next是同起点上一个起点

u其实可以省略,思路就链式前向星类似了,基本一模一样

const int MaxN = 5e5+1;
int first[MaxN],_next[MaxN],to[MaxN],w[MaxN];



//构造邻接表 
void creat(){
	int n,m;
	cin>>n>>m;
	//初始化
	for(int i = 1;i<=n;i++){
		first[i]=-1;
	}
	for(int i = 1;i<=m;i++){
		int index;
		cin>>index>>to[i]>>w[i];
		_next[i] = first[index];
		first[index] = i;
	}
}

邻接表链表实现

感觉挺麻烦,我不想写第二次,贴个实现

//创建有向图的邻接表
#include <iostream>
using namespace std;
const int MaxVnum=100;//顶点数最大值

typedef char VexType;//顶点的数据类型为字符型
typedef struct AdjNode{ //定义邻接点类型
	int v; //邻接点下标
	struct AdjNode *next; //指向下一个邻接点
}AdjNode;

typedef struct VexNode{ //定义顶点类型
	VexType data; // VexType为顶点的数据类型，根据需要定义
	AdjNode *first; //指向第一个邻接点
}VexNode;

typedef struct{//定义邻接表类型
 VexNode  Vex[MaxVnum];
 int vexnum,edgenum; //顶点数，边数
}ALGragh;

int locatevex(ALGragh G,VexType x)
{
 for(int i=0;i<G.vexnum;i++)//查找顶点信息的下标
    if(x==G.Vex[i].data)
     return i;
 return -1;//没找到
}

void insertedge(ALGragh &G,int i,int j)//插入一条边
{
 AdjNode *s;
 s=new AdjNode;
 s->v=j;
 s->next=G.Vex[i].first;
 G.Vex[i].first=s;
}

void printg(ALGragh G)//输出邻接表
{
cout<<"----------邻接表如下：----------"<<endl;
for(int i=0;i<G.vexnum;i++)
{
    AdjNode *t=G.Vex[i].first;
    cout<<cout<<G.Vex[i].data<<"：  ";
    while(t!=NULL)
    {
        cout<<"["<<t->v<<"]  ";
        t=t->next;
    }
    cout<<endl;
}
}

void CreateALGraph(ALGragh &G)//创建有向图邻接表
{
 int i,j;
 VexType u,v;
 cout<<"请输入顶点数和边数:"<<endl;
 cin>>G.vexnum>>G.edgenum;
 cout << "请输入顶点信息:"<<endl;
 for(i=0;i<G.vexnum;i++)//输入顶点信息，存入顶点信息数组
     cin>>G.Vex[i].data;
 for(i=0;i<G.vexnum;i++)
     G.Vex[i].first=NULL;
 cout<<"请依次输入每条边的两个顶点u,v"<<endl;
 while(G.edgenum--)
 {
     cin>>u>>v;
     i=locatevex(G,u);//查找顶点u的存储下标
     j=locatevex(G,v);//查找顶点v的存储下标
     if(i!=-1&&j!=-1)
         insertedge(G,i,j);
     else
     {
        cout << "输入顶点信息错！请重新输入！"<<endl;
        G.edgenum++;//本次输入不算
     }
 }
}

int main()
{
 ALGragh G;
 CreateALGraph(G);//创建有向图邻接表
 printg(G);//输出邻接表
 return 0;
}

三叶姐的最短路和图构建总结

https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/solutions/2526052/gong-shui-san-xie-han-gai-suo-you-cun-tu-svq7/