@skyword
2017-06-03T10:59:46.000000Z
字数 7048
阅读 1078
邻接表存图
邻接表存图:对于图中每个结点,维护一个链表,存储该点的各个邻接点
DFS:深度优先搜索,在每个结点,沿每条路径向内遍历并输出,没有后继结点时回溯
BFS:队列实现
删除点:首先对于要删除的点u,查找所有的邻接点v,调用删边函数delete_edge(u,v)。其次对于所有其他结点v,查找其邻接点中是否有u,若有,删除边(v,u),最后G->V--,即图中结点数目减一
ADJD.h
typedef struct Adj_Graph //图
void Adj_Graph::Adj_Graph_Init() //初始化
main.cpp 测试主程序
没有额外函数
ADJD.h
#ifndef ADJD_H_INCLUDED
#define ADJD_H_INCLUDED
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
#define Max_V 20
typedef struct node
{
int head;
node* nxt;
} edge; //for edge in adj_graph
typedef struct
{
char val;
int start;
edge* adj;//head node of adj list for each node
} Adj_List_Ele;
typedef struct
{
int V;
int E;
Adj_List_Ele L[Max_V];
void Adj_Graph_Init();
void Adj_Destroy();
void print();
void print_vertex(int index, int type);
void Adj_Delete_Vertex(int index);
} Adj_Graph;
void Adj_Graph::Adj_Graph_Init()
{
this->E = 0;
this->V = 0;
for(int i = 0; i < Max_V; i++)//that is, we number vertex from 0
{
this->L[i].adj = NULL;
this->L[i].start = i;
}
}
void Adj_Graph::Adj_Destroy()
{
edge* p,* q;
for(int i = 0; i < this->V; i++)
{
p = this->L[i].adj;
while(p != NULL)
{
q = p->nxt;
free(p);
p = q;
}
}
}
void Adj_Insert_Vertex(Adj_Graph* G, int index, char val)//add a vertex whose value = val, numbered index.
{
if(index >= 0 && index < Max_V)
{
G->L[index].val = val;
G->V ++;
}
else printf("Add vertex failed. Its index should between 0 ~ %d.\n",Max_V-1);
}
void Adj_Insert_Edge(Adj_Graph* G, int s, int t)//add an edge from s to t
{
if(s < 0 || t < 0 || s >= G->V || t >= G->V)
{
printf("Add edge failed. The index of these two vertex should between 0 ~ %d.\n",(G->V)-1);
return;
}
edge* p;
p = (edge*)malloc(sizeof(edge));
p->head = t;
p->nxt = G->L[s].adj;
G->L[s].adj = p;
G->E ++;
}
void Adj_Delete_Edge(Adj_Graph* G, int s, int t, int type)//delete edge from s to t
//Here, type is operation type; type = 0 means using this function manually, type = 1 means using this function by other functions
{
if(s < 0 || t < 0 || s >= G->V || t >= G->V)
{
printf("Delete edge failed. The index of these two vertex should between 0 ~ %d.\n",(G->V)-1);
return;
}
edge* pre, *now;
pre = NULL;
now = G->L[s].adj;
while(now != NULL && now->head != t)
{
pre = now;
now = now->nxt;
}
if(now != NULL && pre == NULL && now->head == t)//pre is null means t is the first link-node of v1
{
G->L[s].adj = now->nxt;
free(now);
G->E --;
}
else if(now != NULL && now->head == t)//we find t, but t is not the first link-node of v1
{
pre->nxt = now->nxt;//jump off "now"
free(now);
G->E --;
}
else
{
if(type == 0)printf("There isn't an edge from %d to %d, though graph G has these two vertexes in it.\n",s,t);
}
}
int Adj_GetFirst(Adj_Graph* G, int index)//get the first node of v
{
if(index < 0 || index >= G->V)printf("The index should between 0 and %d.\n",(G->V)-1);
edge* p;
p = G->L[index].adj;
if(p == NULL)return -1;
else return p->head;
}
int Adj_GetSecond(Adj_Graph* G, int index1, int index2)
{
if(index1 < 0 || index1 >= G->V || index2 < 0 || index2 >= G->V)
{
printf("The index should between 0 and %d.\n",(G->V)-1);
return 0;
}
edge* p;
p = G->L[index1].adj;
while(p->head != NULL)
{
if(p->head != index2)
{
p = p->nxt;
}
else break;
}
p = p->nxt;
if(p != NULL)return p->head;
else return -1;
}
void Adj_Graph::Adj_Delete_Vertex(int index)//delete single vertex in graph
{
if(index < 0 || index >= this->V)
{
printf("The index should between 0 and %d.\n",(this->V)-1);
return;
}
edge* e;
e = this->L[index].adj;
while(e != NULL)
{
Adj_Delete_Edge(this, index, e->head, 1);
e = e->nxt;
}
//cout<<"****"<<endl;
for(int i = 0; i < this->V; i++)
{
if(i == index)continue;
e = this->L[i].adj;
while(e != NULL)
{
if(e->head != index)
e = e->nxt;
else
{
Adj_Delete_Edge(this, i, e->head, 1);
break;
}
}
}
this->L[index].val='#';
/*
for(int i = 0; i < this->V; i++)
{
if(i != index)continue;
//now i == index
else
{
for(int j = i+1; j < this->V; j++)
{
this->L[j-1] = this->L[j];
//int now = this->L[j-1].adj->nxt->head;
//printf("****%c ",this->L[now].val);
}
break;
}
}
*/
//this->V--;
}
void Adj_Graph::print()
//print graph by order following: print each link-node for each node ordered by index
{
for(int i = 0; i < this->V; i++)
{
if(this->L[i].val == '#')continue;
printf("Vertex #%d : %c \n",i,this->L[i].val);
printf("It's suffix vertex: ");
edge* n;
n = (edge*)malloc(sizeof(edge));
n = this->L[i].adj;
int cnt = 0;
while(n != NULL)
{
cnt++;
int now = n->head;
n = n->nxt;
printf("%c ",this->L[now].val);
}
if(cnt == 0)printf("empty.");
printf("\n");
}
}
void Adj_Graph::print_vertex(int index, int type)
//print single vertex of graph, type = 0 means manually using, type = 1 means by other functions
{
char c = this->L[index].val;
if(c == '#')return;
else printf("%c",this->L[index].val);
if(type == 0)printf("\n");
else printf(" ");
}
//Search by DFS and BFS
void Adj_DFS(Adj_Graph* G, int v, int vis[])
{
int nxt;
vis[v] = 1;
G->print_vertex(v, 1);
nxt = Adj_GetFirst(G, v);
while(nxt != -1)
{
if(vis[nxt] == 0) Adj_DFS(G, nxt, vis);
nxt = Adj_GetSecond(G, v, nxt);
}
}
void Adj_BFS(Adj_Graph* G, int v, int vis[])
{
int u,w;
queue<int>q;
vis[v] = 1;
G->print_vertex(v, 1);
q.push(v);
while(!q.empty())
{
u = q.front();
q.pop();
w = Adj_GetFirst(G, u);
while(w != -1)
{
if(vis[w] == 0)
{
vis[w] = 1;
G->print_vertex(w, 1);
q.push(w);
}
w = Adj_GetSecond(G, u, w);
}
}
}
#endif // ADJD_H_INCLUDED
main.cpp
#include <malloc.h>
#include <cstdio>
#include <iostream>
#include <cstring>
#include "ADJD.h"
using namespace std;
int vis[20]={0};
int main()
{
Adj_Graph* G;
G = (Adj_Graph*)malloc(sizeof(Adj_Graph));
G->Adj_Graph_Init();
//Insert 6 vertexes as the graph described.
for(int i = 0; i < 6; i++)
{
char c = 'A'+i;
Adj_Insert_Vertex(G, i, c);
}
Adj_Insert_Edge(G, 5, 0); Adj_Insert_Edge(G, 4, 0); Adj_Insert_Edge(G, 0, 1);
Adj_Insert_Edge(G, 2, 1); Adj_Insert_Edge(G, 3, 2); Adj_Insert_Edge(G, 1, 3);
Adj_Insert_Edge(G, 3, 4); Adj_Insert_Edge(G, 5, 4); Adj_Insert_Edge(G, 1, 5);
Adj_Insert_Edge(G, 2, 5); Adj_Insert_Edge(G, 3, 5);
G->print();
//Illegally adding vertex
Adj_Insert_Vertex(G, 21, 'd');
//Illegally adding edge
Adj_Insert_Edge(G, 5, 9);
//Delete an edge,legally and illegally
//printf("Delete edge from 0 to 1.\n");
//Adj_Delete_Edge(G, 0, 1, 0);
//G->print();
//Adj_Delete_Edge(G, 0, 1, 0);
//Adj_Delete_Edge(G, 0, 9, 0);
//printf("**%d",Adj_GetFirst(G, 0));
printf("DFS-order of G: \n");
Adj_DFS(G, 0, vis);
printf("\n");
memset(vis, 0 , sizeof(vis));
printf("BFS-order of G: \n");
Adj_BFS(G, 0, vis);
printf("\n");
G->Adj_Delete_Vertex(0);
G->print();
}
基本函数
Vertex #0 : A
It's suffix vertex: B
Vertex #1 : B
It's suffix vertex: F D
Vertex #2 : C
It's suffix vertex: F B
Vertex #3 : D
It's suffix vertex: F E C
Vertex #4 : E
It's suffix vertex: A
Vertex #5 : F
It's suffix vertex: E A
Add vertex failed. Its index should between 0 ~ 19.
Add edge failed. The index of these two vertex should between 0 ~ 5.
Delete edge from 0 to 1.
Vertex #0 : A
It's suffix vertex: empty.
Vertex #1 : B
It's suffix vertex: F D
Vertex #2 : C
It's suffix vertex: F B
Vertex #3 : D
It's suffix vertex: F E C
Vertex #4 : E
It's suffix vertex: A
Vertex #5 : F
It's suffix vertex: E A
There isn't an edge from 0 to 1, though graph G has these two vertexes in it.
Delete edge failed. The index of these two vertex should between 0 ~ 5.
搜索
Vertex #0 : A
It's suffix vertex: B
Vertex #1 : B
It's suffix vertex: F D
Vertex #2 : C
It's suffix vertex: F B
Vertex #3 : D
It's suffix vertex: F E C
Vertex #4 : E
It's suffix vertex: A
Vertex #5 : F
It's suffix vertex: E A
DFS-order of G:
A B F E D C
BFS-order of G:
A B F D E C
Process returned 0 (0x0) execution time : 0.034 s
Press any key to continue.
删点
Delete vertex F
Vertex #0 : A
It's suffix vertex: B
Vertex #1 : B
It's suffix vertex: D
Vertex #2 : C
It's suffix vertex: B
Vertex #3 : D
It's suffix vertex: E C
Vertex #4 : E
It's suffix vertex: A
Process returned 0 (0x0) execution time : 0.022 s
Press any key to continue.