您的位置:

python自定义邻接表图类,python构造无向图的邻接表

本文目录一览:

用python实现邻接矩阵转换为邻接表,python语言实现

graph = {'A': ['B', 'C'],

'B': ['C', 'D'],

'C': ['D'],

'D': ['C','G','H'],

'E': ['F'],

'F': ['C']}

#从图中找出任意一条从起始顶点到终止顶点的路径

def find_path(graph, start, end, path=[]):

if start == end:

print "path", path

return True

if not graph.get(start):

path.pop()

return False

for v in graph:

if v not in path:

path.append(v)

if find_path(graph,v,end,path):

return True

return False

path = []

if find_path(graph, 'A', 'C', path=path):

print(path)

else:

print(1)

#从图中找出从起始顶点到终止顶点的所有路径

import copy

def find_path_all(curr, end, path):

'''

:param curr: 当前顶点

:param end: 要到达的顶点

:param path: 当前顶点的一条父路径

:return:

'''

if curr == end:

path_tmp = copy.deepcopy(path)

path_all.append(path_tmp)

return

if not graph.get(curr):

return

for v in graph[curr]:

#一个顶点在当前递归路径中只能出现一次,否则会陷入死循环。

if v in path:

print("v %s in path %s" %(v, path))

continue

#构造下次递归的父路径

path.append(v)

find_path_all(v,end,path)

path.pop()

path_all = []

find_path_all('A', 'G',path=['A'])

print path_all

#遍历图中所有顶点,按照遍历顺序将顶点添加到列表中

vertex = []

def dfs(v):

if v not in graph:

return

for vv in graph[v]:

if vv not in vertex:

vertex.append(vv)

dfs(vv)

for v in graph:

if v not in vertex:

vertex.append(v)

dfs(v)

print(vertex)

请编写一个完整的程序,建立有向图的邻接表存储结构,要求:

给你一个邻接表的完整程序:

#include iostream.h

struct node

{

int data;

node *next;

};

class list

{

public:

list(){head=NULL;};

void MakeEmpty();

int Length();

void Insert(int x,int i);//将x插入到第i个结点(不含头结点)的之后

void Insertlist(int a,int b);//将节点b插入a之前

int Delete(int x);

int Remove(int i);

int Find(int x);

void Display();

private:

node *head;

};

void list::Display()

{

node *current=head;

while (current!=NULL)

{

coutcurrent-data" ";

current=current-next;

}

coutendl;

}

void list::MakeEmpty()

{

head=NULL;

}

int list::Length()

{int n=1;

node *q=head;

if(q==NULL)

n=1;

else

while(q!=NULL)

{

n++;

q=q-next;

}

return n;

}

int list::Find(int x)//在链表中查找数值为x的结点,成功返回1,否则返回0

{

node *p=head;

while(p!=NULLp-data!=x)

p=p-next;

if(p-data==x)

return 1;

else

return 0;

}

void list::Insert (int x,int i)//将x插入到第i个结点(不含头结点)的之后;

{

node *p;//p中放第i个结点

node *q;//q中放i后的结点

node *h;//h中存要插入的结点

h=new node;

h-data =x;

p=head;

if(p-next !=NULL) //链表不是只有一个结点或者空链表时候

{

int n=1;

while(p-next !=NULL)

{

n++;

p=p-next ;

}// 得到链表的结点的个数

p=head;//使p重新等于链首

if(i==n)//i=n时,直接加在最后面就行了

{

while(p-next !=NULL)

p=p-next;

p-next=h;

h-next =NULL;

}

else if(ini1)//先找到第i个结点,用p存第i个结点,用q存i后的结点,用h存要插入的结点

{

for(int j=1;ji;j++)

p=p-next;//找到第i个结点,用p存第i个结点

q=p-next;//q存i后的结点

p-next=h;

h-next=q;

}

else

cout"超出链表结点个数的范围"endl;

}

else

cout"这个链表是空链表或者结点位置在首位"endl;

}

void list::Insertlist(int a,int b)//将b插入到结点为a之前

{

node *p,*q,*s;//p所指向的结点为a,s所指为要插入的数b,q所指向的是a前的结点

s=new node;

s-data=b;

p=head;

if(head==NULL)//空链表的时候

{

head=s;

s-next=NULL;

}

else

if(p-data==a)//a在链首时候

{

s-next=p;

head=s;

}

else

{

while(p-data!=ap-next!=NULL)//使p指向结点a,q指向a之前的结点

{

q=p;

p=p-next;

}

if(p-data==a)//若有结点a时候

{

q-next=s;

s-next=p;

}

else//没有a的时候

{

p-next=s;

s-next=NULL;

}

}

}

int list::Delete(int x)//删除链表中值为x的结点,成功返回1,否则返回0;

{

node *p,*q;

p=head;

if(p==NULL)

return 0;

if(p-data==x)

{

head=p-next;

delete p;

return 1;

}

else

{

while(p-data!=xp-next!=NULL)

{ q=p;

p=p-next;

}

if(p-data==x)

{

q-next =p-next;

delete p;

return 1;

}

else

return 0;

}

}

int list::Remove(int i)

{

node *p,*q;

p=head;

if(p!=NULL)

{ int n=1;

while(p-next !=NULL)

{

n++;

p=p-next ;

}//得到链表结点的个数

p=head;

if(i==n)//i结点在结尾的时候

{

while(p-next!=NULL)

{

q=p;

p=p-next;

}

q-next=NULL;

delete p;

return 1;

}

else if(ini1)//i结点在中间的时候

{

for(int j=1;ji;j++)

{

q=p;//q中放i前的结点

p=p-next ;//p中放第i个结点

}

q-next=p-next;

delete p;

return 1;

}

else if(i==1)//i结点在首位的时候

{

q=p-next;

head=q;

delete p;

return 1;

}

else

return 0;

}

else

return 0;

}

void main()

{

list A;

int data[10]={1,2,3,4,5,6,7,8,9,10};

A.Insertlist(0,data[0]);

for(int i=1;i10;i++)

A.Insertlist(0,data[i]);

A.Display();

menu:cout"1.遍历链表"'\t'"2.查找链表"'\t'"3.插入链表"endl;

cout"4.删除链表"'\t'"5.链表长度"'\t'"6.置空链表"endl;

int m;

do

{

cout"请输入你想要进行的操作(选择对应操作前面的序号):"endl;

cinm;

}while(m1||m6);//当输入的序号不在包括中,让他重新输入

switch(m)

{

case 1:

{

A.Display ();

goto menu;

};break;

case 2:

{

cout"请输入你想要找到的结点:"endl;

int c;

cinc;//输入你想要找到的结点

if(A.Find (c)==1)

{

cout"可以找到"cendl;

A.Display ();//重新显示出链表A

}

else

{

cout"链表中不存在"cendl;

A.Display ();//重新显示出链表A

}

goto menu;

};break;

case 3:

{

cout"请选择你要插入的方式(选择前面的序号进行选择)"endl;

cout"1.将特定的结点加入到特定的结点前"'\t'"2.将特定的结点加到特定的位置后"endl;

int b1;

do

{

cout"请输入你想要插入的方式(选择前面的序号进行选择):"endl;

cinb1;

}while(b11||b12);//当输入的序号不在包括中,让他重新输入

if(b1==1)

{

cout"请输入你想要插入的数和想要插入的结点(为此结点之前插入):"endl;

int a1,a2;

cina1a2;

A.Insertlist (a1,a2);//将a1插入到结点为a2结点之前

cout"此时链表为:"endl;

A.Display ();//重新显示出链表A

}

else

{

cout"请输入你想要插入的数和想要插入的位置(为此结点之后插入):"endl;

int a1,a2;

cina1a2;

A.Insert (a1,a2);//将a1插入到结点位置为a2的结点之后

cout"此时链表为:"endl;

A.Display ();//重新显示出链表A

}

goto menu;

};break;

case 4:

{

cout"请选择你要删除的方式(选择前面的序号进行选择)"endl;

cout"1.删除特定的结点"'\t'"2.删除特定位置的结点"endl;

int b1;

do

{

cout"请输入你想要插入的方式(选择前面的序号进行选择):"endl;

cinb1;

}while(b11||b12);//当输入的序号不在包括中,让他重新输入

if(b1==1)

{

cout"请输入你想要删除的结点:"endl;

int a;

cina;//输入你想要删除的结点

if(A.Delete (a)==1)

{

cout"成功删除"aendl;

cout"删除后的链表为:"endl;

A.Display ();

}

else

{

cout"此链表为:"endl;

A.Display ();//重新显示出链表A

cout"链表中不存在"aendl;

}

}

else

{

cout"请输入你想要删除的结点位置:"endl;

int b;

cinb;//输入你想要删除的结点的位置

if(A.Remove(b)==1)

{

cout"成功删除第"b"个结点"endl;

cout"删除后的链表为:"endl;

A.Display ();//重新显示出链表A

}

else

{

cout"当前链表的结点个数为:"A.Length ()endl;

cout"您输入的结点位置越界"endl;

}

}

goto menu;

};break;

case 5:

{

cout"这个链表的结点数为:"A.Length ()endl;

goto menu;

};break;

case 6:

{

A.MakeEmpty ();

cout"这个链表已经被置空"endl;

goto menu;

};break;

}

}

评论(3)|1

sunnyfulin |六级采纳率46%

擅长:C/C++JAVA相关Windows数据结构及算法百度其它产品

按默认排序|按时间排序

其他1条回答

2012-04-23 17:41121446881|六级

我写了一个C语言的,只给你两个结构体和一个初始化函数:

#include "stdio.h"

#include "malloc.h"

struct adjacentnext//邻接表项结构体

{

int element;

int quanvalue;

struct adjacentnext *next;

};

struct adjacenthead//邻接表头结构体

{

char flag;

int curvalue;

int element;

struct adjacenthead *previous;

struct adjacentnext *son;

};

//初始化图,用邻接表实现

struct adjacenthead *mapinitialnize(int mapsize)

{

struct adjacenthead *ahlists=NULL;

struct adjacentnext *newnode=NULL;

int i;

int x,y,z;

ahlists=malloc(sizeof(struct adjacenthead)*mapsize);

if(ahlists==NULL)

return NULL;

for(i=0;imapsize;i++)

{

ahlists[i].curvalue=0;

ahlists[i].flag=0;

ahlists[i].previous=NULL;

ahlists[i].son=NULL;

ahlists[i].element=i+1;

}

scanf("%d%d%d",x,y,z);//输入源结点,目的结点,以及源结点到目的结点的路权值

while(x!=0y!=0)//x,y至少有一个零就结束

{

newnode=malloc(sizeof(struct adjacentnext));

newnode-element=y;

newnode-quanvalue=z;

newnode-next=ahlists[x-1].son;

ahlists[x-1].son=newnode;

scanf("%d%d%d",x,y,z);

}

return ahlists;//返回邻接表头

}

邻接表 判断有向图是否有环 python

邻接表还是逆邻接表看如果是逆邻接表,每个顶点出发邻接表的链表中的结点个数就是入度

如果是邻接表过程如下:

有一个辅助数组,大小就是顶点数量,所有元素初值都为0

从头到尾遍历每个顶点出发的邻接表的结点,只要当前结点的数据是几(也就是第几个结点被有向弧进入了),这个下标的辅助数组元素加1,等所有的邻接表的小链表遍历完了,这个辅助数组中各个下标的数字就是该顶点的入度

如何用邻接表存储图结构

我看不太懂这个程序,不过我有些过图的邻接表表示,看对你有没有帮助吧。

#include iostream

#include fstream

#include vector

typedef int QElemTyep;

#include "queue.h"

using namespace std;

typedef int Status;

#define MAX_VERTEX_NUM 30 //图的最大顶点数

enum BOOL {False,True};

BOOL visited[MAX_VERTEX_NUM]; //全局变量--访问标志数组

typedef struct ArcNode{

//弧结点

int adjvex; //该弧所指向的顶点的位置

struct ArcNode *nextarc; //指向下一条弧的指针

InfoType *info; //保存边的信息,可以简单的改为 int w;

}ArcNode;

typedef struct VNode{

VertexType data;

ArcNode *firstarc;

}VNode,AdjList[MAX_VERTEX_NUM];

class Graph{

public: AdjList vertices; //记录顶点信息,指向第一条依附该顶点的弧的指针

int vexnum,arcnum; //图的当前顶点和弧数

int GraphKind; //图的种类,0---无向图,1---有向图

Graph(int vexnum,int arcnum,int kind)

{

this-vexnum=vexnum;

this-arcnum=arcnum;

this-GraphKind=kind;

}

};

void CreateGraph(Graph G,VertexType *V,ArcType *VR){

//构造邻接表结构的图G

int i;

ArcNode *s;

for(i=1;i=G.vexnum;i++) //初始化指针数组

{

G.vertices[i].data=V[i];

G.vertices[i].firstarc=NULL;

}

for(i=1;i=G.arcnum;i++)

{

s=(ArcNode *)malloc(sizeof(ArcNode)); //生成一个弧结点

s-nextarc=G.vertices[VR[i].start].firstarc; //插入到邻接表中

s-adjvex=VR[i].end;

G.vertices[VR[i].start].firstarc=s;

if(G.GraphKind==0) {

//若是无向图,再插入到终点的弧链中

s=(ArcNode *)malloc(sizeof(ArcNode));

s-nextarc=G.vertices[VR[i].end].firstarc;

s-adjvex=VR[i].start;

G.vertices[VR[i].end].firstarc=s;

}

}

}