考研复习（8）-图的基本操作

一。图的储存结构
1.临接矩阵表示
易确认两任意顶点是否有边，要确定有多少条则要遍历全图
适合稠密图
#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 100
#define inf 2000000000
typedef char vertexType;
struct vertex
{
int num;
vertexType data;
};
typedef struct graph
{
struct vertex vexs[MAXVEX];//vertex
int edges[MAXVEX][MAXVEX];//adjacency matrix
}adjmax;
2.临接表
无向图有n个顶点，e条边，则临接表需要n个结点哥2e个表节点，适合稀疏图；
无向图中vi的度为第i个链表中的结点数;
有向图中vi的出度为第i个链表中的结点数，求入度需遍历全图，可建立逆临接表；
易找到任一顶点的第一哥邻接点和下一个临接点，但搜索vi和vj之间是否有边或弧需搜索第i个或第j个链表。
#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 100
#define inf 2000000000
typedef char vertexType;
struct edgeNode{
int from;
int weight;
struct edgeNode *next;
vertexType data;
};
typedef struct vexnode
{
vertexType data;
int No;
struct edgeNode *link;
}adjlist[MAXVEX];
二。两种遍历
深搜：
类似于树的先根遍历
//deep first search
void dfs(adjlist adj,int v,int visited[])
//adj is a adjlist, v is the No. of first point,visited is a assistant array
{
int i;
struct edgeNode *p;
visited[v]=1;
printf("[%d,%c]",v,adj[v].data);
p=adj[v].link;
while(p!=NULL)
{
if(visited[p->from]==0) dfs(adj,p->from,visited);
p=p->next;
}
}
宽搜
类似树的层次遍历
访问v之后依次访问各个未曾访问过的临接点，然后分别从这些临接点出发依次访问他们的临接点
//broad first search
void bfs(adjlist adj,int v,int visited[])
{
struct edgeNode *p;
visited[v]=1;
int front=-1,rear=-1;
int i;
rear++;
printf("[%d,%c]",v,adj[v].data);
queue[rear]=v;
while(front!=rear)
{
front=(front+1)%MAXVEX;
i=queue[front];
p=adj[i].link;
while(p!=NULL)
{
if(visited[p->from]==0)
{
printf("..%d,%d:\n",p->from,visited[p->from]);
visited[p->from]=1;
printf("[%d,%c]",p->from,adj[p->from].data);
rear=(rear+1)%MAXVEX;
queue[rear]=p->from;
}
p=p->next;
}
}


}