文档介绍：个人收集整理仅供参考学习
7_1
对于图题（ P235）地无向图，给出：
1）表示该图地邻接矩阵 .
2）表示该图地邻接表 .
3）图中每个顶点地度 .
解：
（1）邻接矩阵：
0111000
1001100
1001010
1110111
0101001
0011001
0001110
2）邻接表：
： 2----3----4----NULL;
1----4----5----NULL;
1----4----6----NULL;
1----2----3----5----6----7----NULL;
2----4----7----NULL;
3----4----7----NULL;
4----5----6----NULL;
3）图中每个顶点地度分别为： 3， 3， 3， 6，3， 3， 3.
7_2
对于图题
地无向图，给出：
（ 1）从顶点
1
出发，按深度优先搜索法遍历图时所得到地顶点序
（ 2）从顶点
1
出发，按广度优先法搜索法遍历图时所得到地顶点序列
.
1） DFS法：
存储结构：
本题采用邻接表作为图地存储结构，邻接表中地各个链表地结点形式由类型 L_NODE规定，
而各个链表地头指针存放在数组 head 中 . b5E2RGbCAP
数组 e 中地元素 e[0],e[1], ..,e[m -1] 给出图中地 m条边， e 中结点形式由类型 E_NODE规
定 .visit[i] 数组用来表示顶点 i 是否被访问过 . 遍历前置 visit 各元素为 0，若顶点 i 被访问
过 , 则置 visit[i] 为 1. p1EanqFDPw
算法分析：
首先访问出发顶点 v. 接着，选择一个与 v 相邻接且未被访问过地地顶点 w 访问之，再从 w 开始进行深度优先搜索 . 每当到达一个其所有相邻接地顶点都被访问过地顶点，就从最后访问
地顶点开始，依次退回到尚有邻接顶点未曾访问过地顶点 u, 并从 u 开始进行深度优先搜索 .
1/12
个人收集整理仅供参考学习
这个过程进行到所有顶点都被访问过，或从任何一个已访问过地顶点出发，再也无法到达未
曾访问过地顶点，则搜索过程就结束 . DXDiTa9E3d
另一方面，先建立一个相应地具有 n 个顶点 ,m 条边地无向图地邻接表 . 初始化 visit 数组，
使其各个元素置为 0，表示图中每个顶点都没被访问过 . RTCrpUDGiT 下面给出程序：
#include<>
#define MAXN 50
#define MAXM 100
typedef struct l_node{int ver;
struct l_node *link;
}L_NODE;
typedef struct e_node{int ver1;
int ver2;
}E_NODE;
void creat_adj_list(L_NODE *head[],int n,E_NODE e[],int m) 5PCzVD7HxA {int i,u,v;
L_NODE *p,*q;
for(i=1;i<=n;i++)
head[i]=NULL;
for(i=0;i<m;i++)
{u=e[i].ver1;
v=e[i].ver2;
p=(L_NODE*)malloc(sizeof(L_NODE));
p->ver=v;
p->link=NULL;
if(head[u]==NULL) head[u]=p;
else {q=head[u];
while(q->link!=NULL) q=q->link;
q->link=p;}
p=(L_NODE*)malloc(sizeof(L_NODE));
p->ver=u;
p->link=NULL;
if(head[v]==NULL) head[v]=p;
else {q=head[v];
while(q->link!=NULL) q=q->link;
q->link=p;}
}
}
void init(int visit[],i