网站结构形式有哪些,合作网站登录制作,wordpress幻灯片设置,新乡网站关键字优化文章目录 0. 实例图1. 邻接矩阵2. 邻接矩阵2.1 链表数组2.2 链式前向星 3. 参考 0. 实例图
考虑下面这样一个图
1. 邻接矩阵
vis[i][j] 表示从i 到j有一条边。直接用二维数组就可以了。
using namespace std;
int vertex_num 5;
vectorvectorint graph(v… 文章目录 0. 实例图1. 邻接矩阵2. 邻接矩阵2.1 链表数组2.2 链式前向星 3. 参考 0. 实例图
考虑下面这样一个图
1. 邻接矩阵
vis[i][j] 表示从i 到j有一条边。直接用二维数组就可以了。
using namespace std;
int vertex_num 5;
vectorvectorint graph(vertex_num, vectorint(vertex_num, 1));void add_edge(int u, int v){graph[u][v] 1;
}
bool have_edge(int u,int v) {return graph[u][v];
}对于上图矩阵的输出就为: ( 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 ) \left ( \begin{array}{} 0 1 1 0 0 \\ 0 0 1 0 0 \\ 0 0 0 1 0 \\ 1 0 0 0 1 \\ 1 0 0 0 0 \end{array} \right) 0001110000110000010000010
2. 邻接矩阵
对于节点i可达的点都链接在一条链上而不是存储所有可能边而是存实际的边。 就像是哈希表一样链表数组。 2.1 链表数组
直接用链表数组模拟还是用vectorvectorint
int vertex_num 5;
vectorvectorint adj(5);void add_edge(int u,int v){adj[u].push_back(v);
}
bool find_edge(int u, int v) {for (int i 0; i adj[u].size(); i) {if (adj[u][i] v) {return true;}}return false;
}2.2 链式前向星
把所有边存在了一个数组中而已。即用两个数组模拟上面的过程。 对于以u为入点的边我们存储时就不能存第一条以u为入点的边了因为那样不方便插入。所以这种方式加边实际上是链表的尾插法。
我们需要存储以u为入点组成边的链表的头节点(head数组)也就是最后插入的以u为入点的边在边数组中的下标。
注 图中的加边顺序为边顶点坐标的字符序。 cnt edge.size() - 1
上代码
#define MAXN 10000 10struct edge {int to;int next;int w;
};struct edge eg[MAXN];
int cnt -1;
int head[MAXN];void add_edge(int u, int v)
{eg[cnt].next head[u];eg[cnt].to v;head[u] cnt;
}
bool have_edge(int u, int v)
{for (int i head[u]; i ! -1; i eg[i].next)if (eg[i].to v)return true;return false;
}memset(head, -1,sizeof(head));3. 参考
主要内容是OIWIKI 只是画图理解下链式前向星。
