无向图邻接表（深度优先算法）

#include <iostream>
using namespace std;
#define MaxVertexNum 100// 最大顶点数为100
#define VertexType char//顶点域为字符型
int visited[MaxVertexNum];//标记结点是否被访问过
typedef struct enode//边表中的结点
{
	int adjvex;//边表顶点域
	struct enode* next;//指针域
}EdgeNode;
typedef   struct vnode//顶点表
{
	VertexType vertex;//顶点域
	EdgeNode* firstedge;//边表头指针
}VertexNode;
typedef struct//邻接表
{
	VertexNode vexs[MaxVertexNum];//节点表
	int n, e;//顶点数和边数
}ALGraph;
void InsertNode(ALGraph& G, int i, int j)//在边表中插入结点
{
	EdgeNode* s;
	s = (EdgeNode*)malloc(sizeof(EdgeNode));//生成新边表结点s
	s->adjvex = j;//邻接点序号为j 
	s->next = G.vexs[i].firstedge;
	G.vexs[i].firstedge = s;//将新边表结点s插入到顶点Vi的边表头部
}
ALGraph CreateALGraph()//建立邻边表
{
	ALGraph G;
	int i, j;
	cout << "请输入顶点数和边数：\n";
	cin >> G.n >> G.e;
	cout << "请输入顶点信息：\n";
	for (i = 0; i < G.n; i++)//建立有n个顶点的顶点表
	{
		cin >> G.vexs[i].vertex;//输入顶点
		G.vexs[i].firstedge = NULL;//顶点的边表头指针设为空
	}
	cout << "请输入边的信息(输入格式为：i (空格) j )：\n";
	for (int k = 0; k < G.e; k++)//建立邻接表
	{
		cin >> i >> j;
		InsertNode(G, i, j);
		InsertNode(G, j, i);
	}
	return G;
}
void DFSAL(ALGraph G, int i) //以Vi为出发点对图G搜索
{
	EdgeNode* p;
	cout << G.vexs[i].vertex << "  ";//访问顶点Vi
	visited[i] = 1;//标记Vi已访问
	p = G.vexs[i].firstedge;//取Vi边表的头指针
	while (p)//依次搜索Vi的邻接点Vj
	{
		if (visited[p->adjvex] == 0)//若Vj尚未访问，则以Vj为出发点继续搜索
			DFSAL(G, p->adjvex);
		p = p->next;//找Vi的下一个邻接点
	}
}
void DFSTraverseAL(ALGraph G)
{
	int  i;
	for (i = 0; i < G.n; i++)
		visited[i] = 0;//初始化
	for (i = 0; i < G.n; i++)
		if (visited[i] == 0)
			DFSAL(G, i);//Vi未访问过，从Vi开始搜索
}
int main()
{
	ALGraph G = CreateALGraph();
	cout << "该图的深度优先搜索遍历得到的顶点序列为：";
	DFSTraverseAL(G);
	system("pause");
	return 0;
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
 

有问题留言

文章来源: chuanchuan.blog.csdn.net，作者：川川菜鸟，版权归原作者所有，如需转载，请联系作者。

原文链接：chuanchuan.blog.csdn.net/article/details/118554945