邻接矩阵和邻接表

Question

波波老师，您好，问题在问号处。

1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

// 向图中添加一个边 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 

1 2 3 4 5 6 7 8 9 10 11 12

// 向图中添加一个边 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 ++; }

Answer 1

liuyubobobo 2019-10-27 13:56:49

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，邻接矩阵为什么是这样的，邻接表为什么是这样的：

继续加油！

• 提问者 我有明珠一颗 #1

  非常感谢！