1. 图的存储结构
常见的图存储结构主要分为邻接矩阵和邻接表两种。
1.1 图的邻接矩阵表示：
image.png
图结构：
#include <stdio.h>
#include <stdlib.h>
#define maxVertices 30 //最大顶点数目
#define maxEdges 450 //最大边数目
typedef char Type;
struct MGrap{
Type VerticesList[maxVertices];
int Edges[maxVertices][maxVertices];
int numVertices,numEdges;
};
图的创建：
#include "MGraph.h"
#include <limits.h>
#include <queue>
int getVertexPos(MGrap &G, Type v)//根据顶点数据获取顶点号
{
for(int i = 0; i < G.numVertices; i++)
{
if(G.VerticesList[i].data == v)
{
return i;
}
}
return -1;
}
int numOfVertices(MGrap &G)
{
return G.numVertices;
}
int numOfEdges(MGrap &G)
{
return G.numEdges;
}
int firstNeighbor(MGrap &G, int v)
{
if(v!=-1)
{
for(int i = 0; i < G.numVertices; i++)
{
if(G.Edges[v][i]>0&&G.Edges[v][i]<INT_MAX)
{
return i;
}
}
}
return -1;
}
int nextNeighbor(MGrap &G, int v, int w)
{
if(v!=-1 && w!=-1)
{
for(int i = w+1; i < G.numVertices; i++)
{
if(G.Edges[v][i]>0&&G.Edges[v][i]<INT_MAX)
{
return i;
}
}
}
return -1;
}
void createALGrap(MGrap &G, Type v[], int n, Type ed[][2], int c[], int e, int d)
{
G.numVertices = n;
G.numEdges = e;
for(int i = 0; i < n; i++)//建立顶点集
{
G.VerticesList[i] = v[i];
for(int j = 0; j < G.numVertices; j++)
{
G.Edges[i][j] = (i==j)?0:INT_MAX;
}
}
for(int i = 0; i < G.numEdges; i++)
{
int e1 = getVertexPos(G,ed[i][0]);
int e2 = getVertexPos(G,ed[i][1]);
G.Edges[e1][e2] = c[i];
if(d == 0) G.Edges[e2][e1] = c[i];
}
}
1.2 图的邻接表表示
image.png
邻接表结构：
#include <stdio.h>
#include <stdlib.h>
#define maxVertices 30 //最大顶点数目
#define maxEdges 450 //最大边数目
typedef char Type;
typedef int Weight;
struct Enode{//边节点
int dest;//边的另一个顶点
int cost;//权重
struct Enode *link;//下一个边节点位置
};
struct Vnode{//顶点定义
Type data;
Enode *adj;//顶点的边
};
struct ALGrap{
Vnode VerticesList[maxVertices];
int numVertices,numEdges;
};
图的创建：
#include "MGraph.h"
#include <limits.h>
#include <queue>
int getVertexPos(MGrap &G, Type v)//根据顶点数据获取顶点号
{
for(int i = 0; i < G.numVertices; i++)
{
if(G.VerticesList[i].data == v)
{
return i;
}
}
return -1;
}
int numOfVertices(MGrap &G)
{
return G.numVertices;
}
int numOfEdges(MGrap &G)
{
return G.numEdges;
}
int firstNeighbor(MGrap &G, int v)
{
if(v!=-1)
{
for(int i = 0; i < G.numVertices; i++)
{
if(G.Edges[v][i]>0&&G.Edges[v][i]<INT_MAX)
{
return i;
}
}
}
return -1;
}
int nextNeighbor(MGrap &G, int v, int w)
{
if(v!=-1 && w!=-1)
{
for(int i = w+1; i < G.numVertices; i++)
{
if(G.Edges[v][i]>0&&G.Edges[v][i]<INT_MAX)
{
return i;
}
}
}
return -1;
}
void createALGrap(MGrap &G, Type v[], int n, Type ed[][2], int c[], int e, int d)
{
G.numVertices = n;
G.numEdges = e;
for(int i = 0; i < n; i++)//建立顶点集
{
G.VerticesList[i] = v[i];
for(int j = 0; j < G.numVertices; j++)
{
G.Edges[i][j] = (i==j)?0:INT_MAX;
}
}
for(int i = 0; i < G.numEdges; i++)
{
int e1 = getVertexPos(G,ed[i][0]);
int e2 = getVertexPos(G,ed[i][1]);
G.Edges[e1][e2] = c[i];
if(d == 0) G.Edges[e2][e1] = c[i];
}
}
void DFS1(MGrap &G, int v, int visit[])
{
cout<<v;
visit[v] = true;
for(int w = firstNeighbor(G,v); w!=-1; w = nextNeighbor(G,v,w))
{
if(!visit[w]) DFS1(G,w,visit);
}
}
void DFS_Traversal(MGrap &G, int v)
{
int n = G.numVertices;
bool visit[n];
for(int i = 0; i < n; i++)
{
visit[i] = false;
}
DFS1(G,v,visit);
}
void BFS(MGrap &G)
{
int n = G.numVertices;
bool visit[n];
for(int i = 0; i < n; i++)
{
visit[i] = false;
}
queue<int> Q;
for(int i = 0; i < n; i++)
{
if(!visit[i])
{
cout<<G.numVertices[i];
visit[i] = true;
Q.push(i);
while(!Q.empty())
{
int j = Q.front();
Q.pop();
for(int w = firstNeighbor(G,j); w!=-1; w = nextNeighbor(G,j,w))
{
if(!visit[w])
{
cout<<G.numVertices[w];
visit[w] = true;
Q.push(w);
}
}
}
}
}
}
2. 图遍历
深度优先遍历DFS
void DFS1(MGrap &G, int v, int visit[])
{
cout<<v;
visit[v] = true;
for(int w = firstNeighbor(G,v); w!=-1; w = nextNeighbor(G,v,w))
{
if(!visit[w]) DFS1(G,w,visit);
}
}
void DFS_Traversal(MGrap &G, int v)
{
int n = G.numVertices;
bool visit[n];
for(int i = 0; i < n; i++)
{
visit[i] = false;
}
DFS1(G,v,visit);
}
广度优先遍历BFS
void BFS(MGrap &G)
{
int n = G.numVertices;
bool visit[n];
for(int i = 0; i < n; i++)
{
visit[i] = false;
}
queue<int> Q;
for(int i = 0; i < n; i++)
{
if(!visit[i])
{
cout<<G.numVertices[i];
visit[i] = true;
Q.push(i);
while(!Q.empty())
{
int j = Q.front();
Q.pop();
for(int w = firstNeighbor(G,j); w!=-1; w = nextNeighbor(G,j,w))
{
if(!visit[w])
{
cout<<G.numVertices[w];
visit[w] = true;
Q.push(w);
}
}
}
}
}
}
