文章目录
〇、前言
这两周开始跟着【MOOC-浙江大学-陈越、何钦铭-数据结构】进行数据结构与算法的学习，特此记录复习一下，虽然记不住，但是一直记一直记一直记，成为复读机就好了。
一、什么是图
二、抽象数据类型
Graph Create()：建立并返回空图；
Graph InsertVertex(Graph G, Vertex v)：将v插入G；
Graph InsertEdge(Graph G, Edge e)：将e插入G；
void DFS(Graph G, Vertex v)：从顶点v出发深度优先遍历图G；
void BFS(Graph G, Vertex v)：从顶点v出发宽度优先遍历图G；
void ShortestPath(Graph G, Vertex v, int Dist[])：计
算图G中顶点v到任意其他顶点的最短距离；
void MST(Graph G)：计算图G的最小生成树；
三、邻接矩阵和邻接表
四、深度优先搜索和广度优先搜索
五、拯救007
六、六度空间
七、课后题
1、06-图1 列出连通集 (25分)
输入样例:
8 6
0 7
0 1
2 0
4 1
2 4
3 5
输出样例:
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10
/* 图的邻接矩阵表示法 */
#define MaxVertexNum 100 /* 最大顶点数设为100 */
#define INFINITY 0 /* ∞设为双字节无符号整数的最大值65535*/
typedef int Vertex; /* 用顶点下标表示顶点,为整型 */
typedef int WeightType; /* 边的权值设为整型 */
typedef char DataType; /* 顶点存储的数据类型设为字符型 */
typedef int Vertex;
typedef int ElementType;
typedef int Position;
int Visited_DFS[MaxVertexNum]; /* 顶点的访问标记 */
int Visited_BFS[MaxVertexNum];
/* 边的定义 */
typedef struct ENode *PtrToENode;
struct ENode{
Vertex V1, V2; /* 有向边<V1, V2> */
WeightType Weight; /* 权重 */
};
typedef PtrToENode Edge;
/* 图结点的定义 */
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv; /* 顶点数 */
int Ne; /* 边数 */
WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
DataType Data[MaxVertexNum]; /* 存顶点的数据 */
/* 注意：很多情况下，顶点无数据，此时Data[]可以不用出现 */
};
typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
struct Node{
ElementType Data;
struct Node *Next;
};
struct QNode {
struct Node *front, *rear; /* 队列的头、尾指针 */
};
typedef struct QNode *Queue;
//****************************************************
MGraph CreateGraph(int VertexNum);
void InsertEdge(MGraph,Edge E);
MGraph BuildGraph();
void Visit( Vertex V );
void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) );
void BFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) );
Queue CreateQueue();
void AddQ(Queue Q,Vertex S);
ElementType DeleteQ(Queue Q);
void ListComponents_BFS(MGraph Graph);
void ListComponents_DFS(MGraph Graph);
//****************************************************
int main(){
MGraph Graph;
Vertex V;
Graph=BuildGraph();
// DFS(Graph,V,Visit);
ListComponents_DFS(Graph);
// BFS(Graph,V,Visit);
ListComponents_BFS(Graph);
return 0;
}
//****************************************************/
/*建队列，假定为空*/
Queue CreateQueue(){
Queue Q;
Q=(Queue)malloc(sizeof(struct QNode));
Q->front=Q->rear=NULL;
return Q;
}
/*进队列*/
void AddQ(Queue Q,Vertex S){
struct Node *temp;
temp=(struct Node*)malloc(sizeof(struct Node));
temp->Data=S;
temp->Next=NULL;
if(Q->front==NULL){
Q->front=temp;
Q->rear=temp;
}
else{
Q->rear->Next=temp;
Q->rear=temp;
}
// return Q;
}
/*出队列*/
ElementType DeleteQ(Queue Q){
struct Node *FrontCell;
ElementType FrontElem;
if(Q->front==NULL){
return -1;
}
FrontCell=Q->front;
if(Q->front==Q->rear)
Q->front=Q->rear=NULL;
else Q->front=Q->front->Next;
FrontElem=FrontCell->Data;
free(FrontCell);
return FrontElem;
}
MGraph CreateGraph( int VertexNum )
{ /* 初始化一个有VertexNum个顶点但没有边的图 */
Vertex V, W;
MGraph Graph;
Graph = (MGraph)malloc(sizeof(struct GNode)); /* 建立图 */
Graph->Nv = VertexNum;
Graph->Ne = 0;
/* 初始化邻接矩阵 */
/* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */
for (V=0; V<Graph->Nv; V++)
for (W=0; W<Graph->Nv; W++)
Graph->G[V][W] = 0;
return Graph;
}
void InsertEdge( MGraph Graph, Edge E )
{
/* 插入边 <V1, V2> */
Graph->G[E->V1][E->V2] = E->Weight;
/* 若是无向图，还要插入边<V2, V1> */
Graph->G[E->V2][E->V1] = E->Weight;
}
MGraph BuildGraph()
{
MGraph Graph;
Edge E;
Vertex V;
int Nv, i;
scanf("%d", &Nv); /* 读入顶点个数 */
Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */
scanf("%d", &(Graph->Ne)); /* 读入边数 */
if ( Graph->Ne != 0 ) { /* 如果有边 */
E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */
/* 读入边，格式为"起点 终点 权重"，插入邻接矩阵 */
for (i=0; i<Graph->Ne; i++) {
scanf("%d %d", &E->V1, &E->V2);
/* 注意：如果权重不是整型，Weight的读入格式要改 */
E->Weight=1;
InsertEdge( Graph, E );
}
}
/* 如果顶点有数据的话，读入数据 */
for (V=0; V<Graph->Nv; V++) {
Visited_DFS[V]=0;
Visited_BFS[V]=0;
}
return Graph;
}
/* 邻接表存储的图 - DFS */
void Visit( Vertex V )
{
printf(" %d", V);
}
void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) )
{ /* 以V为出发点对邻接表存储的图Graph进行DFS搜索 */
Vertex W;
Visit( V ); /* 访问第V个顶点 */
Visited_DFS[V] = 1; /* 标记V已访问 */
for(W = 0; W < Graph->Nv ; W++){
if (Graph->G[V][W] ==1 && !Visited_DFS[W]){
DFS( Graph, W, Visit ); /* 则递归访问之 */
}
}
}
/* 邻接矩阵存储的图 - BFS */
void BFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) )
{ /* 以S为出发点对邻接矩阵存储的图Graph进行BFS搜索 */
Queue Q;
Vertex V, W;
Q = CreateQueue( MaxSize ); /* 创建空队列, MaxSize为外部定义的常数 */
/* 访问顶点S：此处可根据具体访问需要改写 */
Visit( S );
Visited_BFS[S] = 1; /* 标记S已访问 */
AddQ(Q, S); /* S入队列 */
while (Q->front!=NULL) {
V = DeleteQ(Q); /* 弹出V */
for( W=0; W<Graph->Nv; W++ ){ /* 对图中的每个顶点W */
/* 若W是V的邻接点并且未访问过 */
if (Graph->G[V][W] ==1 && !Visited_BFS[W]) {
/* 访问顶点W */
Visit( W );
Visited_BFS[W] = 1; /* 标记W已访问 */
AddQ(Q, W); /* W入队列 */
}
}
} /* while结束*/
}
/* IsEdge(Graph, V, W)检查<V, W>是否图Graph中的一条边，即W是否V的邻接点。 */
/* 此函数根据图的不同类型要做不同的实现，关键取决于对不存在的边的表示方法。*/
/* 例如对有权图, 如果不存在的边被初始化为INFINITY, 则函数实现如下: */
//int IsEdge( MGraph Graph, Vertex V, Vertex W )
//{
// return Graph->G[V][W]<INFINITY ? true : false;
//}
void ListComponents_DFS(MGraph Graph){
Vertex i;
for(i=0; i<Graph->Nv; i++){
if(!Visited_DFS[i]){
printf("{");
DFS(Graph, i, Visit);
printf(" }");
printf("
");
}
}
}
void ListComponents_BFS(MGraph Graph){
Vertex i;
for(i=0; i<Graph->Nv; i++){
if(!Visited_BFS[i]){
printf("{");
BFS(Graph, i, Visit);
printf(" }");
printf("
");
}
}
}
2、06-图2 Saving James Bond - Easy Version (25分)
Sample Input 1:
14 20
25 -15
-25 28
8 49
29 15
-35 -2
5 28
27 -29
-8 -28
-20 -35
-25 -20
-13 29
-30 15
-35 40
12 12
Sample Output 1:
Yes
Sample Input 2:
4 13
-12 12
12 12
-12 -12
12 -12
Sample Output 2:
No
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MaxN 150
int N,D;
int visited[MaxN];
struct Cro{
int x,y;
}cro[MaxN];
//****************************************************
void Save007();
int FirstJump();
int IsSafe(int v);
double ComputeDistance(int a,int b);
int Jump(int a,int b);
int DFS(int v);
//****************************************************
int main(){
int i;
scanf("%d %d",&N,&D);
for(i=0;i<N;i++){
scanf("%d %d",&cro[i].x,&cro[i].y);
}
Save007();
return 0;
}
//****************************************************
double ComputeDistance(int a,int b){
double x=abs(cro[a].x-cro[b].x);
double y=abs(cro[b].y-cro[b].y);
return sqrt(pow(x,2)+pow(y,2));
}
int FirstJump(struct Cro dot){
double dis=sqrt(pow(dot.x,2)+pow(dot.y,2));
double cap=D+7.5;
if(cap>=dis) return 1;
else return 0;
}
int IsSafe(int v){
int x=abs(cro[v].x);
int y=abs(cro[v].y);
if((x+D>=50) || (y+D>=50)) return 1;
else return 0;
}
int Jump( int a, int b ) {
double dis = ComputeDistance(a, b);
if( D >= dis) return 1;
else return 0;
}
int DFS(int v){
int i;
int answer=0;
visited[v] = 1;
if(IsSafe(v)){
answer=1;
}
else{
for(i=0;i<N;i++){
if(!visited[i]&&Jump(v,i)){
answer=DFS(i);
if (answer==1) break;
}
}
}
return answer;
}
void Save007(){
int i;
int answer=0;
for (i=0;i<N;i++) {
if ((!visited[i]) && (FirstJump(cro[i]))) {
answer = DFS(i);
if (answer==1) break;
}
}
if (answer==1) printf("Yes");
else printf("No");
}
3、06-图3 六度空间 (30分)
输入样例:
10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
输出样例:
1: 70.00%
2: 80.00%
3: 90.00%
4: 100.00%
5: 100.00%
6: 100.00%
7: 100.00%
8: 90.00%
9: 80.00%
10: 70.00%
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAXN 1000
//建立图
int G[MAXN][MAXN] = {0};
//N是节点数，M是边数
int N,M;
int visited[MAXN] = {0};//初始化的访问列表
//****************************************************
void init();
int BFS(int v);
//****************************************************
int main(){
int i,v1,v2;
scanf("%d %d",&N,&M);
for (i=0;i<M;i++) {
scanf("%d %d",&v1,&v2);
v1--;v2--;
G[v1][v2]=1;
G[v2][v1]=1;
}
int count;
double Output;
for (i=0;i<N;i++) {
init();
count = BFS(i);
Output=count * 1.0 / N * 100;
printf("%d: %.2f%%
",i+1,Output);
}
return 0;
}
//****************************************************
void init(){
int i;
for(i=0;i<N;i++){
visited[i]=0;
}
}
int BFS ( int v ){
const int MAXNUM = 10002;
int Queue[MAXNUM];
int front=-1;
int rear=-1;
visited[v] = 1;
int count = 1;
int level = 0;
int last = v;
Queue[++rear]=v;
int tail;
while(front<rear){
int de=Queue[++front];
int i;
for (i=0;i<N;i++){
if ( !visited[i]&&G[de][i] ) {
visited[i] = 1;
Queue[++rear]=i; count++;
tail = i;
}
}
if ( de == last ) {
level++; last = tail;
}
if ( level == 6 ) break;
}
return count;
}
总结
开始难度加大了，之所以这一期这么慢，是因为重头翻开了书，数据结构，陈越等，浙大课程原版的书，需要的可以去公众号自取。
如果想要更多的资源，欢迎关注 @我是管小亮，文字强迫症MAX~
回复【数据结构】即可获取我为你准备的大礼！！！
想看更多文（段）章（子），欢迎关注微信公众号「程序员管小亮」~