图的深度优先遍历_根据邻接表从顶点v1出发做深度优先遍历,写出遍历序列,并画出生成树,

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

摘要：

1.了解是如何处理某顶点是否访问过
2.了解邻接表建立过程
3.了解深度优先搜索的过程

1. 如何处理顶点的访问

在建立顶点表时，每个顶点都有其对应的下标，我们可以建立一个visited数组来进行记录，为什么能够记录呢，我们可以根据他们下标相同的特点建立一一对应的联系，例如顶点V0下标为0，访问时，可以使得visited[0]=true，表示已经访问过，顶点v1下标为1，对应visited[1],后面同理。

2.邻接表的建立过程

邻接标的建立相对复杂，将数组和链表结合起来，这里要侧重的理解数组是如何跟链表建立联系的，首先，既然想要使得顶点表中的每一个顶点都为表头，为一个节点，那么，顶点表数组里面显然要存放的类型是顶点，一个结构体，所以AdjList vexs；这个操作就是建立一个存放类型为顶点的，大小为MAXSIZE的vexs数组，然后就是建立链表，我们在每一个顶点里面设有指向弧的指针，直接使用弧。以此完成邻接表创建。

3.深度优先搜索的过程

邻接矩阵遍历过程,直接遍历每一个顶点对应的列就行，有关系的顶点传入其下标，下次递归时递归的是垓下标中的顶点，进行该顶点的递归，完成转换顶点深搜的过程，邻接表也是如此，传入符合条件的下标（有弧关系），下次递归时处理的就是这个节点，直至该节点结束返回上一层，实现主要依靠有递归的思想。

4. 邻接矩阵的深度优先搜索

深搜实现：

typedef int Boolean;
Boolean visited[MAX];//判断数组

void DFS(MGraph G, int i)
{
    int j;
    visited[i] = true;//改变状态，表示已访问过
    cout<<G.vexs[i];//打印该顶点
    for(j = 0; j < G.vexnum; j++){//对该顶点与其他顶点关系判断，存在关系且没有访问过则进行深搜
        if(G.arc[i][j]==1 && !visited[j])
        {
            DFS(G,j);
        }
    }
}

void DFSTraverse()
{
    int i;
    for(int i = 0; i < G.vexnum; i++)
    {
        visited[i] = false;//全部顶点初始状态为 false表示未访问过，true表示访问过
    }
    for(int i = 0; i < G.vexnum; i++)
    {
        if(!visited[i])//如果该顶点未访问过，则进行深搜
        {
            DFS(G, i);
        }
    }   
}
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

完整代码：

#include<iostream>

using namespace std;

#define MAXSIZE 100
typedef string VerTexType;//顶点类型
typedef int ArcType;//弧的权值
typedef int Boolean;
Boolean visited[MAXSIZE];//判断数组，判断顶点有无遍历过

typedef struct {
	VerTexType vexs[MAXSIZE];//顶点表 vertex顶点
	ArcType arcs[MAXSIZE][MAXSIZE];//邻接矩阵 arc 弧
	int vexnum, arcnum;//顶点,弧
}Graph;

int LocateIndex(Graph& G, string vex)
{
	int i;
	for (i = 0; i < G.vexnum; i++)
	{
		if (G.vexs[i] == vex)
		{
			return i;//返回其在顶点表中的索引
		}
	}
	return -1;//不能返回0，因为v0的索引也是0，存在冲突
}

void CreatGraph(Graph& G) {
	int i, j;
	
	cin >> G.vexnum >> G.arcnum;
	//输入顶点表
	for (i = 0; i < G.vexnum; i++)
	{
		cin >> G.vexs[i];
	}
	//输入顶点关系
	for (i = 0; i < G.arcnum; i++)
	{
		string ghead, gtail;//顶点
		int headIndex, tailIndex;//顶点索引

		cin >> ghead >> gtail;
		headIndex = LocateIndex(G, ghead);
		tailIndex = LocateIndex(G, gtail);
		if (headIndex!=-1 && tailIndex!=-1)//如果两个顶点在顶点表中存在
		{
			G.arcs[headIndex][tailIndex] = 1;//存在弧关系，赋值为1，其余为0表示无弧关系
			G.arcs[tailIndex][headIndex] = 1;//无向图顶点对称
		}
	}
}

void DFS(Graph& G, int i)
{
	int j;

	visited[i] = true;//改变状态
	cout << G.vexs[i] << ' ';
	for (j = 0; j < G.vexnum; j++)
	{
		if (G.arcs[i][j] == 1 && !visited[j])//如果存在弧关系并且，没有访问过
		{
			DFS(G, j);
		}
	}
}

void DFSTraverse(Graph& G)
{
	int i;
	//初始化顶点，false表示未访问，true表示已访问过
	for (i = 0; i < G.vexnum; i++)
	{
		visited[i] = false;
	}
	for (i = 0; i < G.vexnum; i++) 
	{
		if (!visited[i])
		{
			DFS(G, i);
		}
	}
}

void DestroyGraph(Graph& g)
{
	//you should do this
	g.arcnum = g.vexnum = 0;
}

int main()
{
	Graph G;
	CreatGraph(G);
	DFSTraverse(G);
	DestroyGraph(G);
	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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

输入示例：

8 9
v1 v2 v3 v4 v5 v6 v7 v8
v1 v2
v1 v3
v2 v4
v2 v5
v3 v6
v3 v7
v4 v8
v5 v8
v6 v7
1
2
3
4
5
6
7
8
9
10
11

输出：

v1 v2 v4 v8 v5 v3 v6 v7 
1

5.邻接表的深度优先搜索

void DFS(Graph& G, int i)
{
	int j;
	ArcNode* P;

	visited[i] = true;
	cout << G.vexs[i].data << ' ';
	P = G.vexs[i].FristNode;

	while(P)//for (j = 0; j < G.vexs[i].size; j++)，不理解为什么这    		个循环为什么会输出错误结果
	{		//size表示相应链表的长度，为什么会跳过这个for循环呢
		if (!visited[P->Vindex]) 
        {
			DFS(G, P->Vindex);
		}
		P = P->NextArc;
	}
}

void DFSTraverse(Graph& G)
{
	int i;

	for (i = 0; i < G.vexnum; i++)
	{
		visited[i] = false;
	}

	for (i = 0; i < G.vexnum; i++)
	{
		if (!visited[i])
		{
			DFS(G, i);
		}
	}
}
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

完整代码：

#include<iostream>

using namespace std;

#define MAXSIZE 100
typedef string VerTexType;//顶点类型
typedef int ArcType;//弧的类型，这里我们使用下标表示弧
typedef int Boolean;
Boolean visited[MAXSIZE];//判断数组

//关于弧信息的结构体
typedef struct ArcNode
{
	ArcType Vindex;//顶点索引,表示X->Vindex的弧关系
	struct ArcNode* NextArc;//下一个弧
}ArcNode;

//建立顶点链表的结构体,首元节点
typedef struct VexNode
{
	VerTexType data;
	ArcNode* FristNode;//都是指向ArcNode类型的指针，所以能够与ArcNode结构体一起操作
	int size;

}VexNode, AdjList[MAXSIZE];//AdjList里面储存的类型为VexNode，即一个顶点节点

//建立顶点表
typedef struct
{
	AdjList vexs;//建立顶点表，顶点数组
	int vexnum, arcnum;
}Graph;

int LocateIndex(Graph& G, string vex)
{
	int i;
	for (i = 0; i < G.vexnum; i++)
	{
		if (G.vexs[i].data == vex)
		{
			return i;
		}
	}
	return -1;
}

void SortArc(ArcNode* adjlist)
{
	int i, j;
	ArcNode* ptr1, * ptr2;
	for (ptr1 = adjlist; ptr1; ptr1 = ptr1->NextArc)
	{
		for (ptr2 = ptr1->NextArc; ptr2; ptr2 = ptr2->NextArc) {
			if (ptr1->Vindex > ptr2->Vindex)
			{
				int temp = ptr1->Vindex;
				ptr1->Vindex = ptr2->Vindex;
				ptr2->Vindex = temp;
			}
		}
	}
}

void CreateGraph(Graph& G)
{
	int i, j;
	string ghead, gtail;
	int gheadIndex, gtailIndex;

	cin >> G.vexnum >> G.arcnum;
	for (i = 0; i < G.vexnum; i++)
	{
		cin >> G.vexs[i].data;
		G.vexs[i].FristNode = NULL;
	}
	//输入弧关系
	for (i = 0; i < G.arcnum; i++)
	{
		cin >> ghead >> gtail;
		gheadIndex = LocateIndex(G, ghead);
		gtailIndex = LocateIndex(G, gtail);

		if (gheadIndex != -1 && gtailIndex != -1)
		{
			ArcNode* p1 = new ArcNode;
			ArcNode* p2 = new ArcNode;
			//存放到相应的链表中
			p1->Vindex = gtailIndex;
			p1->NextArc = G.vexs[gheadIndex].FristNode;
			G.vexs[gheadIndex].FristNode = p1;
			//G.vexs[gheadIndex].size++;//方便后面的深搜遍历

			p2->Vindex = gheadIndex;
			p2->NextArc = G.vexs[gtailIndex].FristNode;
			G.vexs[gtailIndex].FristNode = p2;
			//G.vexs[gtailIndex].size++;
		}
	}
	for (i = 0; i < G.vexnum; i++)//一个一个排序解决了一堆一起排的麻烦情况，即SortArc(G)
	{
		SortArc(G.vexs[i].FristNode);//排序
	}
}

void DFS(Graph& G, int i)
{
	int j;
	ArcNode* P;

	visited[i] = true;//已访问，改变状态
	cout << G.vexs[i].data << ' ';
	P = G.vexs[i].FristNode;

	while(P)//for (j = 0; j < G.vexs[i].size; j++)，不理解为什么这个循环为什么会输出错误结果
	{		//size表示相应链表的长度，为什么会跳过这个for循环呢
		if (!visited[P->Vindex]) {
			DFS(G, P->Vindex);
		}
		P = P->NextArc;
	}
}

void DFSTraverse(Graph& G)
{
	int i;

	for (i = 0; i < G.vexnum; i++)//顶点初始化为false表示未访问，true表示已访问过
	{
		visited[i] = false;
	}

	for (i = 0; i < G.vexnum; i++)
	{
		if (!visited[i])
		{
			DFS(G, i);
		}
	}
}

void DestroyGraph(Graph& G)
{
	int i;
	ArcNode* p, * q;
	for (i = 0; i < G.vexnum; i++)
	{
		p = G.vexs[i].FristNode;
		while (p)
		{
			q = p;
			p = p->NextArc;
			delete q;
		}
	}
	G.vexnum = 0;
	G.arcnum = 0;
}

int main()
{
	Graph G;

	CreateGraph(G);
	DFSTraverse(G);
	DestroyGraph(G);

	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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169