图的存储和搜索算法代码,C代码库,德仔网

代码语言
代码分类
【C】图的存储和搜索算法
作者:Dezai.CN / 发布于2011/8/1/ 552
1。建立一个无向图的邻接表存储2。对该图进行深度优先搜索，按顺序输出所访问的
<div><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">==============================================================================================
</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">==============================================================================================</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">#include</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">iostream.h</span><span style="color: rgb(0,0,0)">></span><span style="color: rgb(0,0,0)">
</span><span style="color: rgb(0,0,255)">#define</span><span style="color: rgb(0,0,0)"> MAX_VERTEX_NUM 20</span><span style="color: rgb(0,0,0)">
typedef </span><span style="color: rgb(0,0,255)">char</span><span style="color: rgb(0,0,0)"> VertexType;
typedef </span><span style="color: rgb(0,0,255)">enum</span><span style="color: rgb(0,0,0)">{FALSE,TRUE}Boolean;
Boolean visited[MAX_VERTEX_NUM];
typedef </span><span style="color: rgb(0,0,255)">struct</span><span style="color: rgb(0,0,0)"> EdgeNode </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">表结点</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">{
 </span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> adjvex;
 </span><span style="color: rgb(0,0,255)">struct</span><span style="color: rgb(0,0,0)"> EdgeNode </span><span style="color: rgb(0,0,0)">*</span><span style="color: rgb(0,0,0)">nextedge;
}EdgeNode;
typedef </span><span style="color: rgb(0,0,255)">struct</span><span style="color: rgb(0,0,0)"> VerNode </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">头结点</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">{
 VertexType vex;
 EdgeNode </span><span style="color: rgb(0,0,0)">*</span><span style="color: rgb(0,0,0)">firstedge;
}VerNode,AdjList[MAX_VERTEX_NUM];
typedef </span><span style="color: rgb(0,0,255)">struct</span><span style="color: rgb(0,0,0)">
{
 AdjList vertices;
 </span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> vexnum,edgenum;
}ALGraph;
</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">================================================================================================
</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">================================================================================================</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> LocateVex_ALG(ALGraph G,VertexType x) </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">确定x在G中的位置</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">{
 </span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> k</span><span style="color: rgb(0,0,0)">=-</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">;
 </span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(k</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;(k</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">G.vexnum)</span><span style="color: rgb(0,0,0)">&&</span><span style="color: rgb(0,0,0)">(G.vertices[k].vex</span><span style="color: rgb(0,0,0)">!=</span><span style="color: rgb(0,0,0)">x);</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">k);
 </span><span style="color: rgb(0,0,255)">return</span><span style="color: rgb(0,0,0)"> k;
}
</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> CreateNDG_ALG(ALGraph </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">G) </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">构造图的邻接表</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">{
 </span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> i,j,k;
 VertexType v1,v2;
 cout</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">请输入图的顶点数和边数：\n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">;
 cin</span><span style="color: rgb(0,0,0)">>></span><span style="color: rgb(0,0,0)">G.vexnum</span><span style="color: rgb(0,0,0)">>></span><span style="color: rgb(0,0,0)">G.edgenum;
 cout</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">请输入顶点的内容：\n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">;
 </span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(i</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;i</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">G.vexnum;</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">i)
 {
 cin</span><span style="color: rgb(0,0,0)">>></span><span style="color: rgb(0,0,0)">G.vertices[i].vex;
 G.vertices[i].firstedge</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">NULL;
 }
 cout</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">请依次输入每条边的初始和终点的顶点内容：\n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">;
 </span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(k</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;k</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">G.edgenum;</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">k)
 {
 cin</span><span style="color: rgb(0,0,0)">>></span><span style="color: rgb(0,0,0)">v1</span><span style="color: rgb(0,0,0)">>></span><span style="color: rgb(0,0,0)">v2;
 i</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">LocateVex_ALG(G,v1);
 j</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">LocateVex_ALG(G,v2);
 EdgeNode </span><span style="color: rgb(0,0,0)">*</span><span style="color: rgb(0,0,0)">p</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,255)">new</span><span style="color: rgb(0,0,0)"> EdgeNode;
 p</span><span style="color: rgb(0,0,0)">-></span><span style="color: rgb(0,0,0)">adjvex</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">j;
 p</span><span style="color: rgb(0,0,0)">-></span><span style="color: rgb(0,0,0)">nextedge</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">G.vertices[i].firstedge;
 G.vertices[i].firstedge</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">p;
 }
}
</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">=================================================================================================
</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">=================================================================================================</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> DFS(ALGraph G,</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> v)
{
 </span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> w;
 EdgeNode </span><span style="color: rgb(0,0,0)">*</span><span style="color: rgb(0,0,0)">p;
 visited[v]</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">TRUE;
 cout</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(0,0,0)">G.vertices[v].vex</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)"> </span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">; </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">输出顶点数据</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(p</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">G.vertices[v].firstedge;p;p</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">p</span><span style="color: rgb(0,0,0)">-></span><span style="color: rgb(0,0,0)">nextedge)
 {
 w</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">p</span><span style="color: rgb(0,0,0)">-></span><span style="color: rgb(0,0,0)">adjvex;
 </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(</span><span style="color: rgb(0,0,0)">!</span><span style="color: rgb(0,0,0)">visited[w])
 DFS(G,w);
 }
}
</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> DFSTraverse(ALGraph G)
{
 </span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> v;
 </span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(v</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;v</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">G.vexnum;</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">v)
 visited[v]</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">FALSE;
 cout</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">按深度优先遍历顺序依次输出顶点为：\n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">;
 </span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(v</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;v</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">G.vexnum;</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">v)
 </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(</span><span style="color: rgb(0,0,0)">!</span><span style="color: rgb(0,0,0)">visited[v])
 DFS(G,v);
 cout</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(0,0,0)">endl;
}
</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">==================================================================================================
</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">==================================================================================================</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> main()
{
 ALGraph G;
 CreateNDG_ALG(G); </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">由邻接表构造无向图</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)"> DFSTraverse(G); </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">按深度优先遍历顺序遍历该无向图</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">}
</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">=========================================================================================================
</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">=========================================================================================================</span></div>
试试其它关键字
　图的存储和搜索　
同语言下
可能有用的
Dezai.CN贡献的其它代码(4037)