邻接矩阵和邻接表
来源：7-2 图的表示
我有明珠一颗
2019-10-27
波波老师，您好，问题在问号处。
1
// 向图中添加一个边
void addEdge( int v , int w ){
assert( v >= 0 && v < n );
assert( w >= 0 && w < n );
if( hasEdge( v , w ) )
return;
g[v][w] = true;
if( !directed )
g[w][v] = true;//这行代码表示什么意思？是不是说，纵向的边的编号w,横向的起始顶点的编号v,对应的元素=true,这个true表示相连
m ++;
}2
// 向图中添加一个边
void addEdge( int v, int w ){
assert( v >= 0 && v < n );
assert( w >= 0 && w < n );
g[v].push_back(w);
if( v != w && !directed )//为什么要有v!=w这个判断呢？
g[w].push_back(v);//w表示边，那么g[w]是不是表示这条边对应顶点v？而这个顶点是不是起始顶点呢
m ++;
}写回答
1回答
-
1
表示顶点v和顶点w之间有边
2
如果没有这个判断，假设有自环边，这个自环边将存两次。比如如果1到1之间有自环边，没有 v != w 的判断的话，g[1]中就会存两个1，这是不对的。
不过，由于这个课程只处理简单图，不会有自环边，所以没有这个判断也没关系。
3
w 不表示边，w 表示顶点。g[v] 中包括 w，表示 v-w 两个顶点相连，即 v-w 之间存在边。
对于无向图，边没有起始点终止点的区分，因为没有方向，所以 g[v]中有w，g[w]中有v。
请再仔细理解一下邻接矩阵和邻接表的定义。我们的代码都是在实现原理。请一定要搞明白下面两页的 ppt，邻接矩阵为什么是这样的，邻接表为什么是这样的：
继续加油！
112019-10-27
相似问题