同城根据邻接表看深度优先自动接单

点击联系发帖人 时间：2020-12-12 12:21

根据邻接表看深度优先

邻接表是图的一种链式存储结构对图的每个顶点建立一个单链表（n个顶点建立n个单链表）

//由于是无向图,存在反向链接 if(!visited[i]) //选取一个未访问过的顶点进行根据邻接表看深度优先优先遍历,如果是连通图DFS只执行一次

}

本算法以无向网为例存储方式采用邻接链表

1）将该网以邻接链表的方式存储

2）选取A点为起始点，访问此顶点用一个visit的bool型数组记录访问状态（false表示未被访问，true表示已访問）

3）从A的未被访问的邻接点出发根据邻接表看深度优先优先遍历图，直到图中所有和v有路径相通的顶点都被访问到

二、算法复杂度：O(n+e)

彡、在实际编写代码时笔者发现

1）对采用邻接链表作为存储方式的图做DFS时，由于建立邻接链表时可采用不同的插入方法：比如头插法和尾插法会使得做DFS时相同的图结构会有不一样的结果；

2）即使相同的图结构，采用不同的存储方式（邻接矩阵和邻接链表）做DFS时它们的結果有时也会不一样；

笔者认为这都是正常现象，DFS的思想还是没变

本算法的测试用例为《大话数据结构》p239中的图7-5-2。如下图所示：

/**无向图嘚邻接链表的建立**/ //顶点表结点数据结构 //邻接链表图的数据结构 /**无向图邻接链表的建立**/ printf("请输入无向图邻接链表的顶点数和边数：\n"); //输入顶点信息建立顶点表 printf("边表的建立：输入边（vi,vj）的顶点下标，权值统一为1如：0 1 1(权值)\n"); //无向图，因此是对称的同样的操作将下标为i的顶点插入与の相连的下标为j的结点的链表中 //无向图的邻接链表的第i个顶点的DFS //对整个无向图进行DFS

六、测试代码及测试结果

}

图论中一个基本的概念就是遍历就是访问到图的每一个顶点，同时每个顶点只访问一次

DFS和BFS的概念和思路网上说明的很详细了。但是网上很多代码实现有缺陷基本都沒有考虑图不连通的情况，比如某个顶点A和其它任何一个顶点都不关联那么这个顶点A就访问不到了。如果遍历的起点刚好是孤立的顶点A就只能访问顶点A了，其它顶点就访问不到了

int index; //邻接顶点在顶点数组中的索引值 //这里我们通过出度表来遍历 //与vertexIndex相邻的顶点并且未访问过的頂点全部入栈 //图并不一定是连通的，因此要确保每个顶点都遍历过 //这里我们通过出度表来遍历 //与vertexIndex相邻的顶点并且未访问过的顶点全部入队 //圖并不一定是连通的因此要确保每个顶点都遍历过

}

我爱游戏网