图结构
邻接矩阵的存储方式
(需要与矩阵压缩重点复习)
① 二维数组存储
②一维数组压缩存储
很显然一维数组压缩存储方式，只严格存储下三角部分。
第0行不存元素，第1行存储一个元素，第二行存储2个元素…，第n-1行存储n-1个元素，共需要存储：
邻接表的存储方式
①边结点结构
typedef struct edge_node
{
int adjacent; //编号域
cost_type cost; //长度域
struct edge_node *next; //边结点的next指针
}edge_node,*Eptr;
②0/1图的边结点结构
typedef struct edge_node //边结点
{
int adjacent; //编号域
struct edge_node *next; //边结点的next指针
}edge_node,*Eptr;
邻接链表的表头结点(顶点结点)结构
typedef struct
{
Vname_type name;
Eptr firsedge;
} hnode;
先深搜索遍历算法
void dfsmian()
{
int v; // 结点变量
for(v=0;v<n;n++)L[v].mark=0; //循环将每一个结点标记值清零
for(v=0;v<n;n++) //对每一个标记值进行判断
{
if(L[v].mark==0) //如果没有标记过
dfs(v); //对该结点进行dfs
}
}
void dfs(int v)
{
Eptr p; int w; //创建一个新的结点，结点变量
visit(v); //对结点v进行访问
L[v].mark=1; //标记该结点代表已经访问过
p=L[v].firstedge; //指向已经访问过的结点的邻接表的首结点
while(p!=NULL) //当邻接表的首结点存在时
{
w=p->adjacent; //将编号赋给新结点w
if(L[w].mark==0) //如果新结点w未被访问过
dfs(w); //访问新结点w
p=p->next; //递归结束后，结点下移
}
}
求无向图的连通分量的算法
void dfsmian()
{
int v,k=0;
for(v=0;v<n;v++)L[v].mark=0;
for(v=0;v<n;v++)
{
if (L[v].mark==0)
{
k++;
printf("第%d个连通分量的顶点集:\n {",k);
dfs(v);
printf(" }\n");
}
}
}
求无向图先深生成树的算法
void dfsmian()
{
int v; // 结点变量
for(v=0;v<n;n++)L[v].mark=0; //循环将每一个结点标记值清零
for(v=0;v<n;n++) //对每一个标记值进行判断
{
if(L[v].mark==0) //如果没有标记过
{
将(v,w)加进树边集;
dfs(v); //对该结点进行dfs
}
}
}
判断有向图是否存在回路的算法
int cycle; //cycle是整体量，"有回路否"标记
void dfsmian()
{
int v; // 结点变量
cycle=0;
for(v=0;v<n;n++)L[v].mark=0; //循环将每一个结点标记值清零
for(v=0;v<n;n++) //对每一个标记值进行判断
{
if(L[v].mark==0) //如果没有标记过
dfs(v); //对该结点进行dfs
if(cycle)
printf("图中有回路\n");
else
printf("图中没有回路\n");
}
}
void dfs(int v)
{
Eptr p; int w; //创建一个新的结点，结点变量
visit(v); //对结点v进行访问
L[v].mark=1; //标记该结点代表已经访问过
p=L[v].firstedge; //指向已经访问过的结点的邻接表的首结点
while(p!=NULL) //当邻接表的首结点存在时
{
w=p->adjacent; //将编号赋给新结点w
if(L[w].mark==0) //如果新结点w未被访问过
dfs(w); //访问新结点w
else if(L[w].mark==1) //dfs(w)尚未终止，置有回路标记
cycle=1;
p=p->next; //递归结束后，结点下移
}
L[v].mark=2; //置dfs(v)终止标记
}
求无向连通图关节点的算法
int count=0;root_sons=0;
void dfsmian()
{
int v; // 结点变量
for(v=0;v<n;n++)
L[v].mark=0; //对顶点作未标记访问
v=0;
L[v].father=0;
dfs(v);
if(root_sons>1)
printf("%s\n",L[v].name);
}
void dfs(int v)
{
Eptr p; int w;
L[v].mark=1;
L[v].low=L[v].dfnumb=++count; //置v的先深编号和low(v)初值
p=L[v].firstedge;
while(p)
{
w=p->adjacent;
if(L[w].mark==0)
{
L[w].father=v; //使w作v的儿子，递归调用
dfs(w);
if(L[v].dfnumb==1)//若v是根，根的儿子计数加1
root_sons++;
else //若不是
if(L[w].low>=L[v].dfnumb) //发现v是关结点
if(v没被输出过)
printf("%s\n",L[v].name);//输出关结点名
if(L[v].low>L[w].low)
L[v].low=L[w].low;
//使父亲v的low值不大于儿子w的low值
}
else //L[w].mark 不等于 0，表示 w 已被访问过
if(L[v].father!=w && L[v].low> L[w].dfnumb)
L[v].low=L[w].dfnumb;
//若 w 不是 v 的父亲，则（v，w）是回边
p=p->next;
}
}
网友评论