图的表示

邻接矩阵

使用graph[i][j]>0graph[i][j]>0表示顶点ii与jj之间存在一条边，graph[i][j]graph[i][j]的值可以表示边的权值。

1
2
3
4
5
6
7
8
9
10
void getGraph(int n, int m)
{
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        graph[u][v] = 1;
        //无向图graph[v][u] = 1;
    }
}

邻接表

数组模拟

使用graph[i][0]graph[i][0]表示和顶点ii相连的点有多少个，graph[i][j]graph[i][j]表示第jj个与ii相连的点的编号。例如graph[2][0]=5graph[2][0]=5表示与22号顶点相连的点有5个，graph[2][1]=3graph[2][1]=3表示33号顶点是与22号顶点相连的第一个点。

1
2
3
4
5
6
7
8
9
10
void getGraph(int n, int m)
{
    int u, v;
    for (int i = 0; i < m; i++)
    {
        cin >> u >> v;
        graph[u][++graph[u][0]] = v;
        //无向图graph[v][++graph[v][0]] = u;
    }
}
1
2
3
4
5
//查找与x相连的点
for(int i = 1; i < graph[x][0]; i++)
{
	cout << graph[x][i];
}

vector

graph[i].size()graph[i].size()表示和第ii个顶点相连的点有多少个，graph[i][j]graph[i][j]与上面相同。

1
2
3
4
5
6
7
8
9
10
11
vector<int> graph[MAX];
void getGraph(int n, int m)
{
    int u, v;
    for(int i = 0; i < m; i++)
    {
        cin >> u >> v;
        graph[u].push_back(v);
        //无向图graph[v].push_back(u);
	}
}
1
2
3
4
5
//查找与x相连的点
for(int i = 0; i < graph[x].size(); i++)
{
    cout << graph[x][i];
}

链式前向星

首先定义一个边的结构体。

1
2
3
4
5
6
struct Edge
{
    int to;//表示该边指向的节点
    int nextEdge;//表示下一条边的序号
    int weigh;//权值
}edge[MAX];

然后需要定义一个变量用来存储edge[]edge[]​存储到的位置，一个数组用来存放顶点与边的连接情况。

1
2
int cnt = 0;
int head[MAX];

其中head[i]head[i]表示与顶点ii相连的最后一条边的序号，比如head[2]=3head[2]=3表示顶点22的最后一条边是edge[3]edge[3]。

1
2
3
4
5
6
7
8
9
10
11
12
13
void addEdge(int u, int v)
{
        cin >> u >> v;
        edge[++cnt].to = v;
        edge[cnt].nextEdge = head[u];
        head[u] = cnt;
}
void getGraph(int n, int m)
{
    int u, v;
    addEdge(u, v);
    //无向图addEdge(v, u);
}
1
2
3
4
5
6
7
//事实上当我们查找与x相连的点的时候都是先从最后一条边所指开始。
//所以head[i]表示的也许是最后读取的"第一条边"?
//当edge[i].nextEdge == 0时表示当前边为最后一条边(第一条边?)
for(int i = head[x]; i != 0; i = edge[i].nextEdge)
{
    cout << edge[i].to;
}